5

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.

martineau
  • 119,623
  • 25
  • 170
  • 301
PointOnePA
  • 91
  • 6
  • (1) Why are you looking at the definition of bin/int vars? If the relax is infeasible so is any discrete-constrained one (2) cvxopt is open-source. You can check out the code if you need to. (3) Your example is incompletely printed and shows only 2 different results, and those are not surprising.(4) If no variable is discrete (I or B) it's obviously continuous. Why is result 3 surprising? Check out [the code](https://github.com/cvxopt/cvxopt/blob/ddb311a14ac0338cbb9b445c42a8a298f8ea700a/src/C/glpk.c#L432) (5) I somewhat doubt cvxopt is the correct lib to build column-gen models. – sascha Feb 17 '18 at 04:03
  • I'm not looking for the definition of bin/int vars. I'm looking for detail documentation on the ILP function and in particular, the declaration of the "I" and "B" parameters. The example is "incomplete" because I'm using the code from the previously posted question 39384909 as an example. The glpk.c source that you have referenced is useful, in that I should be able to answer my questions about the "I" and "B" arguments from that source, so thanks for that. I didn't know ILP included simplex() and would return float results. I thought it would only return Integer answers. – PointOnePA Feb 18 '18 at 14:17

1 Answers1

4

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
PointOnePA
  • 91
  • 6
  • Thanks a lot! If I e.g. have an inequality like `x0+x1 <= 1`, and both `x0, x1` are binary, do you know from your research if `x0+x1` has the ability to reach 2 if both are "true", or will this be clamped to 1 (or even modulo to 0)? – fr_andres Jun 11 '20 at 22:59
  • In other words, I want to prevent 2 binaries being true by use of the inequality, and a naive implementation using 1-bit registers would fail to allow that. I guess I could do a minimal working example but just in case you knew. Thanks again – fr_andres Jun 11 '20 at 23:01
  • Nevermind, `glpk.ilp` forces me to provide `G, h, A, b` as doubles so no overflow should happen in that range – fr_andres Jun 12 '20 at 00:48