Pre-processing a MILP - Githubissues

sagemath / sage

Main repository of SageMath. Now open for Issues and Pull Requests.

https://www.sagemath.org

Other

1.2k stars 413 forks source link

Pre-processing a MILP #23786

Open jdemeyer opened 6 years ago

jdemeyer commented 6 years ago

When formulating a problem as a MILP in practice, I often end up with a problem which is stupid in different ways. I suggest that we could pre-process a MILP to fix the following:

constant contraints (1 >= 0).
redundant constraints (f(x) >= a and f(x) >= b).
equalities (f(x) = 0) which should be eliminated by linear algebra.
using linear algebra to change some constraints to variable bounds.

I haven't thought about the user interface of this, whether this is something that should be done by default or not...

First I want to see to what extent the various solvers (in particular, PPL which I personally care about most) are affected by these issues.

Component: linear programming

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

jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -2,7 +2,7 @@

 - constant contraints (`1 >= 0`).

-- redundant constraints (same contraint appearing more than once).
+- redundant constraints (`f(x) >= a` and `f(x) >= b`).

 - equalities (`f(x) = 0`) which should be eliminated by linear algebra.

jdemeyer commented 6 years ago

Description changed:

--- 
+++ 
@@ -10,4 +10,4 @@

 I haven't thought about the user interface of this, whether this is something that should be done by default or not...

-First I want to see to what extent the various solvers are affected by these issues.
+First I want to see to what extent the various solvers (in particular, PPL which I personally care about most) are affected by these issues.

dcoudert commented 6 years ago

comment:3

I see several drawbacks with your proposal

solvers are very efficient in eliminating redundant or useless constraints, and also propagating obvious values. You can compare the time to write and solve a MILP when adding multiple times the same constraints with check_redundant turn to True and False. It's usually faster with False (at least with Cplex and Gurobi that I'm using frequently)
We currently don't have access to dual variables in our framework and so it is not possible to do column generation. If you eliminate constraints, it might be even harder since the user might ask for the dual of a constraint that has been eliminated
The elimination of constraints might become much more complex for the user if the number of added constraints is different from the number of stored constraints If you want to do that, please make it optional and not default.

jdemeyer commented 6 years ago

comment:4

Replying to @dcoudert:

solvers are very efficient in eliminating redundant or useless constraints, and also propagating obvious values.

Part of this proposal is also to check which kinds of elimination do and do not make sense. This may be different for different solvers. I mainly use PPL, because the problems that I work with tend to be too numerically unstable for non-exact solvers.

If you want to do that, please make it optional and not default.

I never said to make it default. It would be some explicit method call doing this.