CODEWITHSUNDEEP
linear-programmingcplexinteger-programming
Mengfan Ma
Mengfan Ma

Reputation: 351

Why does CPLEX set unrelated variables as 1?

I have been working on a combinatorial optimization problem which can be modeled as an integer linear programming. I implemented it as a c++ project in visual studio 2017 and CPLEX1271. Since there are exponentially many constraints, I implemented lazy constraints by IloCplex::LazyConstraintCallbackI. In my mind the following procedure is how an optimal soution is produced: everytime an integer solution is identified, LazyConstraintCallbackI will check it and add some violated constraints to the model untill an optimal integer solution is obtained.

However, the objective values given by my implementation for different inputs are not always correct. After almost one year's intermittent debug and test, I finally figured out the reason, which is very problem related but can be explained(hopefully) by the following tiny example:  an integer linear programming involving four bool variables x1, x2, x3 and x4

minimize x1
subject to: 
x1  ≥  x2
x1  ≥  x3
x1  ≥  x4
x2  + x3  ≥ 1
x1, x2, x3 and x4  ∈ {0, 1}​

The result given by cplex is:

Solution status = Optimal
Objective value = 1
x1 = 1
x2 = 1
x3 = 1
x4 = 1​

Undoubtedly, the objective value is correct .The weird thing is that cplex sets  x4 = 1. Although whether x4 equals 1 or 0 has no impact on the objective value in this programming. But, when lazy constraint callback is used, this could lead to a problem by adding some incorrect contraint and integer programming is solved by iteratively adding violated constraints. I'd like to know:

  1. why cplex set "unrelated" variable  x4  as 1, instead of 0?
  2. What should I do to tell CPLEX that I want to leave such "unrelated" variable as 0?

Upvotes: 0

Views: 282

Answers (1)

Daniel Junglas
Daniel Junglas

Reputation: 5930

Since there is nothing that forces x4=0 in an optimal solution, there is no guarantee that CPLEX will set x4=0? Why would it? Why is 0 preferred over 1? The model has two optimal solutions, one with x4=0 and one with x4=1. Both have objective value 1. CPLEX is completely free to choose one of them.

Like sascha said in his comments, the only way to force x4=0 in an optimal solution is to add this constraint to the model, for example by setting the objective coefficient to a small positive value.

However, it seems strange that your lazy constraint callback would generate invalid constraints from integer feasible solutions. This looks like a bug: Either the callback makes invalid assumptions about the model (namely that x4=0 in any optimal solution) or there is a bug somewhere in the logic of the callback. Note that in the model at hand it would actually be fine for the callback to cut off the solution with x4=1 since that still leaves the equivalent optimal solution with x4=0 and CPLEX would eventually find that.

Upvotes: 5

Related Questions