Binary variables in Integer Programs solved with CPLEX have wrong bounds

[Stephen Hartke]

It seems that Integer Programs solved with CPLEX sometimes have the wrong bounds on binary variables.  For instance,

p=MixedIntegerLinearProgram(solver="CPLEX")

x=p.new_variable(dim=1)  #,binary=True)

p.add_constraint(x[0]+x[1]==2)

p.set_objective(None)

p.set_binary(x)

p.show()

p.solve()

print p.get_values(x)

gives the output

Maximization:
 
Constraints:
  2.0 <= x_0 + x_1 <= 2.0
Variables:
  x_0 is a boolean variable (min=0.0, max=+oo)
  x_1 is a boolean variable (min=0.0, max=+oo)
{0: 2.0, 1: 0.0}
Note that x[0] has the solution 2, which shouldn't happen for a binary variable.  In the output, the upper bound of the variable is not printed correctly, but I'm not sure if that's a problem, since an upper bound should not need to be explicitly set for a binary variable.  In other instances when using binary variables with CPLEX, they seem to behave as they should.
This issue is more problematic than it appears, since if CPLEX is installed it becomes the default IP/LP solver, and other things can randomly fail.  For instance,
sage.combinat.integer_vector.gale_ryser_theorem([2]*5,[5]*2)
should give a 5x2 matrix of all 1's but instead gives
[2 0]
[2 0]
[1 1]
[0 2]
[0 2]
I am using Sage 5.12 and IBM ILOG CPLEX 12.5.1.0.  I took a look in cplex_backend.pyx, but nothing immediately jumped out as a problem.
Thanks for any insight that anyone has!
Best wishes,
Stephen

[Nathann Cohen]

Hellooooooooooooo !!!

It seems that Integer Programs solved with CPLEX sometimes have the wrong bounds on binary variables.  For instance,

Well, as you say CPLEX defined a "binary" type. And does not associate bounds with such variables, because it knows it is binary. Anyway :

sage: p=MixedIntegerLinearProgram(solver="cplex");

sage: b=p.new_variable(binary=True)               

sage: p.add_constraint(b[0] == 2)

sage: p.solve()

...

MIPSolverException: 'CPLEX: The primal has no feasible solution'

Soooooo well. No problem.

{0: 2.0, 1: 0.0}
Note that x[0] has the solution 2, which shouldn't happen for a binary variable.  

When I ran the example of code you gave (removing the comment before binary=True, I get the solution 0:1, 1:1, which is good. If you really get a variable equal to 2 on this example, something is dead wrong indeed. 

 

In the output, the upper bound of the variable is not printed correctly, but I'm not sure if that's a problem, since an upper bound should not need to be explicitly set for a binary variable.

Hmmmm... The trick is that Sage stores no information on the LP. Everything is stored in the backend. So if CPLEX does not store as "variable bounds" 0 and 1, then Sage does not know it and displays the bounds that are stored in CPLEX's data structure. Though it remembers that the variable is binary of course.

 

  In other instances when using binary variables with CPLEX, they seem to behave as they should.
This issue is more problematic than it appears, since if CPLEX is installed it becomes the default IP/LP solver, and other things can randomly fail.  For instance,
sage.combinat.integer_vector.gale_ryser_theorem([2]*5,[5]*2)
should give a 5x2 matrix of all 1's but instead gives
[2 0]
[2 0]
[1 1]
[0 2]
[0 2]
I am using Sage 5.12 and IBM ILOG CPLEX 12.5.1.0.  I took a look in cplex_backend.pyx, but nothing immediately jumped out as a problem.

Well...Really, when I run this what I get is :

sage: sage.combinat.integer_vector.gale_ryser_theorem([2]*5,[5]*2)

[1 1]

[1 1]

[1 1]

[1 1]

[1 1]

 

Thanks for any insight that anyone has!

Well, I would be glad to help but I would need to be able to reproduce one of the bugs for a start :-P

Nathann 

[Stephen Hartke]

Sorry for the delay in responding, but I was traveling over the holidays.  Happy New Year!

On Sun, Dec 15, 2013 at 5:18 AM, Nathann Cohen <nathan...@gmail.com> wrote:

{0: 2.0, 1: 0.0}

Note that x[0] has the solution 2, which shouldn't happen for a binary variable.  

When I ran the example of code you gave (removing the comment before binary=True, I get the solution 0:1, 1:1, which is good. If you really get a variable equal to 2 on this example, something is dead wrong indeed.

Something is indeed wrong, and I have experienced similar problems in the past.  What version of CPLEX and which version of Sage are you using? I am using IBM ILOG CPLEX 12.5.1.0, and Sage 5.12 on Fedora Linux 19 and Sage 5.10 on Fedora 13. 

 

Well, I would be glad to help but I would need to be able to reproduce one of the bugs for a start :-P

What other information can I give to help track this down?

Thanks,

Stephen

[Nathann Cohen]

Hellooooooooooo !!!

> Something is indeed wrong, and I have experienced similar problems in the past.  What version of CPLEX and which version of Sage are you using? I am using IBM ILOG CPLEX 12.5.1.0, and Sage 5.12 on Fedora Linux 19 and Sage 5.10 on Fedora 13.
>  

> What other information can I give to help track this down?

HMmmmm... Well, to be honest I don't know. The truth is : I don't remember having met a nasty bug like that with Sage at any point, though it is possible that it may have been fixed since since you do not use the latest version of Sage.. Coud you try it with a more recent version of Sage, like the 6.0 ?

Actually, there is a trac ticket waiting for review related to how LP solvers handle bounds, but I do not think it is related to this bug
http://trac.sagemath.org/ticket/15622

(it does *not only* fix GLPK code)

It would be cool to know if the bug still exists.. Which would be a good way out, for I do not really know how to debug this from a distance ^^;

Nathann

[Stephen Hartke]

On Tue, Jan 7, 2014 at 1:58 AM, Nathann Cohen <nathan...@gmail.com> wrote:

> Something is indeed wrong, and I have experienced similar problems in the past.  What version of CPLEX and which version of Sage are you using? I am using IBM ILOG CPLEX 12.5.1.0, and Sage 5.12 on Fedora Linux 19 and Sage 5.10 on Fedora 13.

HMmmmm... Well, to be honest I don't know. The truth is : I don't remember having met a nasty bug like that with Sage at any point, though it is possible that it may have been fixed since since you do not use the latest version of Sage.. Coud you try it with a more recent version of Sage, like the 6.0 ?

I upgraded to Sage 6.0, and the output is still wrong.  I then checked IBM, and a new version of CPLEX was released in early December 2013.  With CPLEX 12.6.0 and Sage 6.0, I now get the correct answers.

So it seems that CPLEX 12.5.10 was the culprit.  Though it is surprising to me that there would be such a basic bug.  I am somewhat worried that there is something wrong with the CPLEX interface code in Sage, but it seems very straightforward.

I recall having weird problems using CPLEX in Sage in the past; one specific instance from summer 2012 jumps to mind.  I'll see if I can't dig up one of those instances and see if they have been fixed with new versions of Sage and CPLEX.

 

Actually, there is a trac ticket waiting for review related to how LP solvers handle bounds, but I do not think it is related to this bug
http://trac.sagemath.org/ticket/15622

(it does *not only* fix GLPK code)

Do you mean http://trac.sagemath.org/ticket/14581 ?

Best wishes,

Stephen

[Nathann Cohen]

Yooooooooooooo !!!

> I upgraded to Sage 6.0, and the output is still wrong. I then checked IBM, and a new version of CPLEX was released in early December 2013. With CPLEX 12.6.0 and Sage 6.0, I now get the correct answers.

HMmmmmmmm O_o

> So it seems that CPLEX 12.5.10 was the culprit. Though it is surprising to me that there would be such a basic bug. I am somewhat worried that there is something wrong with the CPLEX interface code in Sage, but it seems very straightforward.

Well, at first we stored all the LP data, but now we really just
forward every Sage command to the solver-specific backend. But if
there was a bug like that in Cplex, it is highly unlikely that all
tests passed in the graph/ folder. It is stuffed with binary problems.

> I recall having weird problems using CPLEX in Sage in the past; one specific instance from summer 2012 jumps to mind. I'll see if I can't dig up one of those instances and see if they have been fixed with new versions of Sage and CPLEX.

Okay !

> Do you mean http://trac.sagemath.org/ticket/14581 ?

Yep sorry >_<

Nathann