Ask Your Question
0

Indexes in Linear programming

asked 2023-11-26 21:13:32 +0100

Cyrille gravatar image

updated 2023-11-27 00:23:40 +0100

Max Alekseyev gravatar image

If you look at the output of this linear program

bomb = MixedIntegerLinearProgram(maximization=True, solver = "GLPK");
x = bomb.new_variable(integer=True, nonnegative=True);
bomb.add_constraint(0.9*x[1]>=200);
bomb.add_constraint(0.9*x[0]+0.27*x[6]>= 0.9*x[1])
bomb.add_constraint(0.8*x[3]+0.24*x[8]>= 0.9*x[1])
bomb.add_constraint(0.135*x[4] + 0.9*x[10]>= 0.9*x[1])
bomb.add_constraint(0.25*x[5] + 0.9*x[11]>= 0.9*x[1])
bomb.add_constraint(x[0]+x[1]+x[2]+x[3]+x[4]+x[5]<=800);
bomb.add_constraint(x[6]+0*x[7]+x[8]+x[9]+x[10]+x[11]<=500);
bomb.set_objective(0.9*x[1])
bomb.show()

you will see that Sagemath doesn't respect the index of the $x[i]$. It enumerate the variables in the order of encounter. This is terribly perturbating. Is there a way to impose the respect of the indexes ?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2023-11-27 05:59:30 +0100

dsejas gravatar image

Hello, @Cyrille! At first, I also found this feature from Sage quite annoying. However, I should point out that there is a reason for things to be like this, and I have come to actually appreciate this feature. Let me explain...

In order for the following explanation to be clear, let us revise dictionaries in Python. A dictionary is a data structure that associates what we call keys with values. For example, here is a dictionary that list grades from students:

scores = {'John': 100, 'Mary': 20, 'Paul': 100}

As you can see, there are three students John, Mary, and Paul (the keys), each of which has a final score of 100, 20, and 100 (the values), respectively. Moreover, you can easily access the score of any of the (e.g., Mary) by doing something like score['Mary'], which will return the value 20.

How can a dictionary like this can be created? One of the possible ways if to write directly as one single instruction the way I did above. But it is also possible to create it step-by-step like this:

scores = {}
scores['John'] = 100
scores['Mary'] = 20
scores['Paul'] = 100

With each line, you append a new key-value pair, preserving the order in which were added. And now, back to MILPs...

When you create a new MILP variable in Sage, e.g.,

bomb = MixedIntegerLinearProgram(maximization=True, solver = "GLPK")
x = bomb.new_variable(integer=True, nonnegative=True)

you are actually creating a data structure that internally stores the mathematical variables of your model in a dictionary. (In order to simplify the explanation, I am going to refer to x as "the dictionary" instead of "the data structure that has the dictionary"). Now, how are the key-value pairs created in this context? When you write

bomb.add_constraint(0.9*x[1] >= 200)

Sage finds the x[1] and recognizes that it has to create a new variable. Since this is the first variable corresponding to this model, it will be called x_0 (remember that Python indices start from zero). But that variable has been associated with the key 1, so x[1] equals x_0. (You should remember that, for Python dictionaries, having an x[1] does NOT guarantee that there is an x[0] in the same way as having a scores['Mary'] does NOT guarantee that there is a scores['Caesar'].) In your next line

bomb.add_constraint(0.9*x[0] + 0.27*x[6] >=  0.9*x[1])

Sage first finds the x[0], which has not been used/assigned before, so it creates a new mathematical variable x_1 and associates it with the key 0, so x[0] equals x_1. Then, in the same line of code it finds x[6] which has not been used until now, so it creates a new math variable x_2 and then x[6] is x_2. You can easily check any of these facts by writing print(x[1], x[0], x[6]) right after your code, that will show you x_0 x_1 x_2.

This behaviour is pretty useful when you want your variables to be associated with more descriptive names. For example, x['USA-EU'] could represent the quantity of product being shipped from USA to the EU. It is definitely more descriptive than just calling it x[0]. However, in cases like the one in your code it can lead to confusion, because the key is just a name and not necessarily is the same as the index, which is something important to remember.

There are a couple of ways to solve this problem. The first is to use the name parameter from the new new_variable() method. For example, your second line of code would become

x = bomb.new_variable(integer=True, nonnegative=True, name='x')

then, when you call bomb.show() in your last line of code, it should print this:

Maximization:
  0.9 x[1] 

Constraints:
  -0.9 x[1] <= -200.0
  0.9 x[1] - 0.9 x[0] - 0.27 x[6] <= 0.0
  [...]
Variables:
  x[1] = x_0 is an integer variable (min=0.0, max=+oo)
  x[0] = x_1 is an integer variable (min=0.0, max=+oo)
  [...]

which shows you the model as you wrote it, but also clarifies that x[1] = x_0 (the dictionary x associates the variable x_0 with the key 1), and so on. Of course you can use some other name for the dictionary. For example,

x = bomb.new_variable(integer=True, nonnegative=True, name='var')

which will produce your output to have lines like 0.9 var[1] (your objective function) and var[1] = x_0 is an integer variable (min=0.0, max=+oo).

The other solution (which I believe you will prefer) is to use the indices parameter from new_variable(). It accepts an iterable (list, tuple, range, etc.) that will determine what will be the accepted indices and, most important for your case, in what order. If you change your second line with

x = bomb.new_variable(integer=True, nonnegative=True, indices=range(0,12))

you will notice that x[0] == x_0, x[1] == x_1, x[2] == x_2, ..., x[11] == x_11, giving you the correspondence you expected. Once again, this is because the dictionary is pre-filled with the variables in the order dictated by the indices parameter, making in this case to coincide the dictionary key and the index of the associated mathematical variable.

Hope this helps!

edit flag offensive delete link more

Comments

1

See also #53887

David Coudert gravatar imageDavid Coudert ( 2023-11-27 07:05:27 +0100 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-11-26 21:13:32 +0100

Seen: 38 times

Last updated: Nov 27 '23