Weird behaviour of MixedIntegerLinearProgram

LinearProgram

asked 2020-10-12 18:03:01 +0200

Cyrille
1413 ●24 ●70 ●129

updated 2020-10-12 20:57:00 +0200

slelievre
17654 ●22 ●160 ●348 http://carva.org/samue...

Not really a question, more of an observation, perhaps a bug, I do not know.

p = MixedIntegerLinearProgram(maximization=False, solver="GLPK")
x = p.new_variable(real=True, nonnegative=True)
p.set_integer(x[2])
p.add_constraint(2*x[0] + 2*x[1] + 3*x[2] - 10*x[3] <= 0)
p.add_constraint(6*x[1] + 4*x[2] - 11*x[3] >= 0)
p.add_constraint(2*x[2] - 6*x[3] <= 0)
p.add_constraint(x[0] - x[1] - x[2] >= 0)
p.add_constraint(x[3] >= 1)
p.set_objective(3*x[1] + 6*x[2] - 3*x[3])
p.show()

This code sets x[0] integer when it should be x[2].

The following code works:

p = MixedIntegerLinearProgram(maximization=False, solver="GLPK")
x = p.new_variable(real=True, nonnegative=True)
p.set_real(x[0])
p.set_real(x[1])
p.set_integer(x[2])
p.add_constraint(2*x[0] + 2*x[1] + 3*x[2] - 10*x[3] <= 0)
p.add_constraint(6*x[1] + 4*x[2] - 11*x[3] >= 0)
p.add_constraint(2*x[2] - 6*x[3] <= 0)
p.add_constraint(x[0] - x[1] - x[2] >= 0)
p.add_constraint(x[3] >= 1)
p.set_objective(3*x[1] + 6*x[2] - 3*x[3])
p.show()

I find this weird. If I code p.set_integer(x[2]), I expect x[2] to be integer. (If I do not add p.set_real(x[1]), x[1] is set to integer). Certainly one more time, somebody will say I did not read the documentation correctly.

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2020-10-13 10:02:29 +0200

David Coudert
726 ●11 ●18 http://www-sop.inria.f...

updated 2020-10-13 10:05:17 +0200

The names x_i indicate the order in which the variables x[i] are accessed first. You can see it if you set parameter name of method new_variable. So variable x[2] is correctly sets to integer, although it's internal name is x_0.

sage: p = MixedIntegerLinearProgram(maximization=False, solver="GLPK") 
....: x = p.new_variable(real=True, nonnegative=True, name="x") 
....: p.set_integer(x[2]) 
....: p.add_constraint(2*x[0] + 2*x[1] + 3*x[2] - 10*x[3] <= 0) 
....: p.add_constraint(6*x[1] + 4*x[2] - 11*x[3] >= 0) 
....: p.add_constraint(2*x[2] - 6*x[3] <= 0) 
....: p.add_constraint(x[0] - x[1] - x[2] >= 0) 
....: p.add_constraint(x[3] >= 1) 
....: p.set_objective(3*x[1] + 6*x[2] - 3*x[3]) 
....: p.show()                                                                                                                      
Minimization:
  6.0 x[2] + 3.0 x[1] -3.0 x[3] 

Constraints:
  3.0 x[2] + 2.0 x[0] + 2.0 x[1] - 10.0 x[3] <= 0.0
  -4.0 x[2] - 6.0 x[1] + 11.0 x[3] <= 0.0
  2.0 x[2] - 6.0 x[3] <= 0.0
  x[2] - x[0] + x[1] <= 0.0
  - x[3] <= -1.0
Variables:
  x[2] = x_0 is an integer variable (min=0.0, max=+oo)
  x[0] = x_1 is a continuous variable (min=0.0, max=+oo)
  x[1] = x_2 is a continuous variable (min=0.0, max=+oo)
  x[3] = x_3 is a continuous variable (min=0.0, max=+oo)

edit flag offensive delete link

Comments

Thanks a lot David, I was not able to imagine such a vicious comportment of the package. I say vicious, because now that I know that I can cope with it, but how can I explain this to economist students who discover Linear programming, Python and Sagemath in the same time. If I want to keep the order I must write its nature for each variable in order it is certainly not the simplest things to do if I have a huge lot of variables.

Cyrille ( 2020-10-13 15:14:13 +0200 )edit

Trick your students by explaining them that it's easier to read the program if the variables have meaningful names like "price", "benefit", "cost". And so that it's important to define parameter name. Also, use different variables for each type.

David Coudert ( 2020-10-13 23:30:39 +0200 )edit

add a comment

answered 2020-10-14 10:54:14 +0200

Sébastien
3153 ●5 ●39 ●85 http://www.slabbe.org/

If you read the documentation of p.new_variable method, you can see that there is an option indices:

"indices" -- (optional) an iterable of keys; components corresponding to these keys are created in order, and access to components with other keys will raise an error; otherwise components of this variable can be indexed by arbitrary keys and are created dynamically on access

Using this option:

p = MixedIntegerLinearProgram(maximization=False, solver="GLPK")
x = p.new_variable(real=True, nonnegative=True, name='x', indices=[0,1,2,3])
p.set_integer(x[2])
p.add_constraint(2*x[0] + 2*x[1] + 3*x[2] - 10*x[3] <= 0)
p.add_constraint(6*x[1] + 4*x[2] - 11*x[3] >= 0)
p.add_constraint(2*x[2] - 6*x[3] <= 0)
p.add_constraint(x[0] - x[1] - x[2] >= 0)
p.add_constraint(x[3] >= 1)
p.set_objective(3*x[1] + 6*x[2] - 3*x[3])

gives the desirable behavior:

sage: p.show()                                                                  
Minimization:
  3.0 x[1] + 6.0 x[2] -3.0 x[3] 

Constraints:
  2.0 x[0] + 2.0 x[1] + 3.0 x[2] - 10.0 x[3] <= 0.0
  -6.0 x[1] - 4.0 x[2] + 11.0 x[3] <= 0.0
  2.0 x[2] - 6.0 x[3] <= 0.0
  - x[0] + x[1] + x[2] <= 0.0
  - x[3] <= -1.0
Variables:
  x[0] = x_0 is a continuous variable (min=0.0, max=+oo)
  x[1] = x_1 is a continuous variable (min=0.0, max=+oo)
  x[2] = x_2 is an integer variable (min=0.0, max=+oo)
  x[3] = x_3 is a continuous variable (min=0.0, max=+oo)

edit flag offensive delete link

Comments

Thanks a lot sebastien. I miss this.

Cyrille ( 2020-10-15 07:09:35 +0200 )edit

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Weird behaviour of MixedIntegerLinearProgram

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Weird behaviour of MixedIntegerLinearProgram edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Weird behaviour of MixedIntegerLinearProgram