search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.41k stars 475 forks source link

MixedIntegerLinearProgram should support tableau-query methods getBInvARow, getBInvRow, getBInvACol, getBInvCol #18733

Open mkoeppe opened 9 years ago

mkoeppe commented 9 years ago

If one uses Sage's MixedIntegerLinearProgram class for solving an LP, it is useful to access dictionary (tableau) data corresponding to the current (often optimal) basis. For example, one needs this to compute tableau cutting planes such as Gomory's fractional cut.

The Sage interface should, of course, be designed to work consistently across all solvers. There are some subtleties here. Best to be compatible with a library that has already sorted most of it out: In the COIN open solver interface, there are the functions getBInvARow, getBInvRow, getBInvACol, getBInvCol. Unfortunately these functions do not seem to be implemented in Osi's GLPK backend; so one needs to use one of Osi more complete backends such as CPLEX or CLP to find the precise definition.

18732 adds the necessary backend functions for the GLPK backend.

18763 adds the necessary backend functions for the COIN (CBC/CLP) backend.

This kind of information is available in every solver.

See also #18688, and also #18804 (LPBackendDictionary).

Depends on #18732

CC: @nathanncohen @yuan-zhou

Component: numerical

Issue created by migration from https://trac.sagemath.org/ticket/18733

dimpase commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-If one uses Sage's MixedIntegerLinearProgram class for solving an LP, it is useful to access dictionary (tableau) data corresponding to the current (often optimal) basis. For example, one needs this to compute tableau cutting planes such as Gomory's fractional cut. 
+If one uses Sage's `MixedIntegerLinearProgram` class for solving an LP, it is useful to access dictionary (tableau) data corresponding to the current (often optimal) basis. For example, one needs this to compute tableau cutting planes such as Gomory's fractional cut. 

 The Sage interface should, of course, be designed to work consistently across all solvers. There are some subtleties here. Best to be compatible with a library that has already sorted most of it out: In the COIN open solver interface, there are the functions [getBInvARow](https://projects.coin-or.org/Osi/browser/trunk/Osi/src/Osi/OsiSolverInterface.hpp#L1860), getBInvRow, getBInvACol, getBInvCol.
 Unfortunately these functions do not seem to be implemented in Osi's GLPK backend; so one needs to use one of Osi more complete backends such as CPLEX to find the precise definition.
dimpase commented 9 years ago
comment:2

Note that not all Sage's LP solvers use a simplex method. E.g. cvxopt does not. In this case is makes no sense talking about tableaux...

mkoeppe commented 9 years ago
comment:3

The methods would raise NotImplementedError or other errors when no tableau is available. Even if the backend uses the simplex method, these methods may raise an error when solve has not been called yet.

mkoeppe commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,8 +1,12 @@
 If one uses Sage's `MixedIntegerLinearProgram` class for solving an LP, it is useful to access dictionary (tableau) data corresponding to the current (often optimal) basis. For example, one needs this to compute tableau cutting planes such as Gomory's fractional cut. 

 The Sage interface should, of course, be designed to work consistently across all solvers. There are some subtleties here. Best to be compatible with a library that has already sorted most of it out: In the COIN open solver interface, there are the functions [getBInvARow](https://projects.coin-or.org/Osi/browser/trunk/Osi/src/Osi/OsiSolverInterface.hpp#L1860), getBInvRow, getBInvACol, getBInvCol.
-Unfortunately these functions do not seem to be implemented in Osi's GLPK backend; so one needs to use one of Osi more complete backends such as CPLEX to find the precise definition.
+Unfortunately these functions do not seem to be implemented in Osi's GLPK backend; so one needs to use one of Osi more complete backends such as CPLEX or CLP to find the precise definition.

-#18732 adds the necessary backend functions for the GLPK backend. This kind of information is available in every solver.
+#18732 adds the necessary backend functions for the GLPK backend. 
+#18763 adds the necessary backend functions for the COIN (CBC/CLP) backend.
+
+This kind of information is available in every solver.

 See also #18688.
+
mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -8,5 +8,5 @@

 This kind of information is available in every solver.

-See also #18688.
+See also #18688, and also #18804 (LPBackendDictionary).