Does my LP have fractional optima ?

The problem

Here is the situation. You have a combinatorial problem P, and an integer linear programming model M for P. Now you ask the question whether the relaxed model M' has the property that all extreme point optimal solutions are integral. Because if that is the case, you have an algorithm for P.

Our contribution

We provide some tools to verify this property. You will need to adapt it to your specific problem. The ingredients are PORTA, PULP, and some python and shell script. Porta will generate all the extreme point solutions to a given linear program and PUPL permits to call a linear program solver from python.

Installation

To install porta, just download it from its webpage. To install PULP, just launch sudo easy_install -U pulp in a terminal, and if you are not superuser on the machine easy_install -user -U pulp.

How can I use it

The program genLPx.py implements the model M and generates given some problem specific parameters the linear program, in a format readable by porta. The example we provide generates the following model, which you will need to adapt. Two parameters are given $n$ and $p$. There are $n^2p$ variables, named $y_{j,t}$ for $j=1,..,n$ and $t=1,..,np$. The constraints are \[ \forall j: \sum t y_{jt} = 1 \] and \[ \forall a=0,..,n-1, \forall i: \sum_{j\geq i} \sum_{t<(a+1)p+i-1} y_{jt} \geq a. \] Note that there is no objective function at this point. In the .ieq porta format all variables have to be named x1 to xn, for the dimension n.

The program genLPp.py reads from stdin the list of the extreme point solutions, and separates them into integer and fractional solutions. For each fractional solution x it tests if there exist weights in the model, that would make x a solution strictly better than all integral solutions. This test is conducted by solving a simple linear program, where every integral extreme point solution z generates a constraint. Again the weights here are model specific, and you would need to adapt them. In our case we have the objective function \[ \min \sum w_j t y_{jt} \] for some non-negative weights $w_1,\ldots,w_n$. There is a constant strict in this script where you can specify whether you want the fractional solution x to be strictly better than all other integral solutions, or only at least as good. All these linear programs are tested in parallel, you can adapt the constant c in the program according to the number of cores available on your machine. Once a counter-example is found, it is outputted and the program stopped.

How does it work

The script test.sh has to be called with the parameters of the model M. It generates the linear program using the program genLPx mentioned above. Then it calls porta to generate the list of all extreme point solutions to the LP. And finally it calls genLPp.py. We recommend to launch test.sh with the command batch, so you will get an email notification at its completion.

The sources

... are here.

Enjoy it, and please send me a mail for suggestions. Thank you.


Last update 2014.