search

sagemath / sage

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

Determine equalities implied by a MILP #23770

Open jdemeyer opened 7 years ago

jdemeyer commented 7 years ago

For a research problem I'm working on, I need to know the set of equalities implied by a LP problem.

Component: numerical

Author: Jeroen Demeyer

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

mkoeppe commented 7 years ago
comment:1

LP or MILP?

jdemeyer commented 7 years ago
comment:2

For the research problem LP, but it can work the same way for a MILP.

mkoeppe commented 7 years ago
comment:3

For LP, try redund from lrslib. I don't remember if it guarantees to find all equations. If it doesn't, then there's no way around computing the double description (in sage, setting up the polyhedron already computes that).

For MIP, in general no way around computing the integral hull. We have some methods for that in sage; the best implementation is using normaliz, which also supports the unbounded case. However, there is an interesting software, IPO by Matthias Walter (https://polyhedra-oracles.bitbucket.io/) for cases when computing things like this when computing the full integral hull is out of reach.

jdemeyer commented 7 years ago
comment:4

Right. My idea was essentially to use this strategy mentioned on the IPO website:

On the other hand, maximizing linear objective functions over these polyhedra (though most often NP-hard) can be done very efficiently for moderate sizes (say n=100), e.g., by mixed-integer programming solvers

mkoeppe commented 7 years ago
comment:5

His thesis is quite informative: http://matthiaswalter.org/downloads/Dissertation.pdf

mkoeppe commented 7 years ago
comment:6

Looks like IPO now has a cython interface too. We should get this package into sage.

jdemeyer commented 7 years ago
comment:7

Unfortunately, IPO depends on SCIP which is not open source.

mkoeppe commented 7 years ago
comment:8

Replying to @jdemeyer:

Unfortunately, IPO depends on SCIP which is not open source.

SCIP is just one implementation that it can use. There's also a way to just hook in a Python callback as the oracle implementation. (Haven't tested this myself.)