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.

Improve this question
2
  • (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 (5) I somewhat doubt cvxopt is the correct lib to build column-gen models. Commented Feb 17, 2018 at 4: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. Commented Feb 18, 2018 at 14:17

1 Answer 1

Reset to default
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
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

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)?
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
Nevermind, glpk.ilp forces me to provide G, h, A, b as doubles so no overflow should happen in that range

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.