Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

cvxopt.glpk.ilp documentation on Integer & Binary set keys

I have a mixed integer programming problem, (cutting stock with column generation), that I've solved in AMPL and I'm ported to Python using cvxopt. CVXOPT "op" doesn't provide the binary variable option that I need, so I'm extending it with GLPK to use "ILP". I'm getting the ilp status = "LP relaxation is primal infeasible", which I know isn't right because of the prior AMPL solution. So I know I have it configured incorrectly. I'm trying to understand that the use of the integer "I" & the binary "B" keys by playing around with the example in the stackoverflow question The integer linear programming(ILP) function in CVXOPT returns non integers.

My question is, what's the difference between the I&B keys, such that:

stat, sol1 = glpk.ilp(W, G.T, h, I=set([0, 1]))
stat, sol2 = glpk.ilp(W, G.T, h, I={0,1})
stat, sol3 = glpk.ilp(W, G.T, h)

has the 3 different solutions below: (print(soli.T)

  1. [ 0.00e+00 0.00e+00 5.00e-01 5.00e-01 5.00e-01 -0.00e+00 ... ]

  2. [ 0.00e+00 0.00e+00 5.00e-01 5.00e-01 5.00e-01 -0.00e+00 ... ]

  3. [ 5.00e-01 5.00e-01 5.00e-01 5.00e-01 5.00e-01 -0.00e+00 ... ]

I've looked at help(ilp), but it just says that I&B are sets of indicies of the integer and binary variables, (which I understand), but it doesn't describe what happens if you use both (I&B), or they overlap, or one or the other is the empty set, or not defined. I would have thought that sol1=sol2 above, since it is just two different ways to define the set I. I presume sol3 is all integer and no binary variables since B is left undefined, but I don't have any documentation to confirm that.

like image 890
PointOnePA Avatar asked Feb 16 '18 21:02

PointOnePA


1 Answers

I found the answer to my questions, so I'm posting it here in case others have the same question regarding cvxopt.glpk.ilp() and the I & B parameters.

A: (status, x) = ilp(c, G, h, A, b)
x is all floating point

B: (status, x) = ilp(c, G, h, A, b, I)
x is mix of float & integer depending on the indices in set I

C (status, x) = ilp(c, G, h, A, b, I, B) x is a mix of float, integer, and binary depending on the indices in set I and set B.
If the sets I and Boverlap, then B supersedes.

Question #33785396 provided an example that I'll reuse here. It's from: https://en.wikipedia.org/wiki/Integer_programming#Example

For A: the result is                           [1.8,  2.8]  all float
For B: with I={0}, the result is               [2.0,  2.67] int & float
For B: with I={1}, the result is               [2.67, 2.0]  float & int
For B: with I={0,1}, the result is             [2.0,  2.0]  int & int
For C: with I={0,1} and B={0}, the result is   [1.0,  2.0]  binary & int
For C: with I={0,1} and B={0,1}, the result is [0.0,  1.0]  binary & binary
like image 163
PointOnePA Avatar answered Nov 13 '22 18:11

PointOnePA