MixedIntegerLinearProgram should provide a way to get the variables in the order they are provided to the polyhedron method

[sagetrac-tmonteil]

When creating a MixedIntegerLinearProgram, we may have no control on the order in which the (one-dimensional) variables are defined (because of complicated loops).

When we use the polyhedron method, the basis of the underlying vector space is ordered according to some order on the variables, which basically follows the order in which they are defined.

However, there is no simple way to get this order for the user. We need a method to get this order if we want to be able to connect information provided by the polytope (e.g. its set of integral points) to the original linear problem.

To provide a concrete example of the issue, see my answer of this as question.

CC: @jplab @mkoeppe @mo271 @videlec @yuan-zhou

Component: linear programming

Author: Matthias Koeppe

Branch/Commit: u/mkoeppe/mixedintegerlinearprogram_should_provide_a_way_to_get_the_variables_in_the_order_they_are_provided_to_the_polyhedron_method @ db6571e

Issue created by migration from https://trac.sagemath.org/ticket/26302

[dcoudert]

comment:2

I'm not aware of all the ways to use MixedIntegerLinearProgram, create variables, use vectors of variables, etc.

At least, in class MIPVariable, we can add a list to record the order in which variables of of that class are created. It suffices to add the key to that list inside method __getitem__.

[mkoeppe]

comment:3

A trick to control the order is to touch all MIP variables in the desired order (before adding constraints to the system).

[mkoeppe]

comment:4

Replying to @mkoeppe:

A trick to control the order is to touch all MIP variables in the desired order (before adding constraints to the system).

In your answer to that ask.sagemath question,
you can simplify

 for edge in G.edges(labels=False):
        p.add_constraint(e[edge] >= 0)

to

[ e[edge] for edge in G.edges(labels=False) ]

[mkoeppe]

comment:5

Instead of trying to produce a mapping from backend variables to frontend variables, I would propose to:

• Add an optional argument backend_values (a vector of length self.number_of_variables()) to the MixedIntegerLinearProgram.get_values method. If provided, it will take values from this vector instead of from the backend via backend.get_variable_value.

[dcoudert]

comment:6

[ e[edge] for edge in G.edges(labels=False) ]

MIP variables are stored in a dictionary. So even if you touch them in a certain order, you rely on the ordering of the keys of the dictionary, which might be different.
Storing keys in a list in the order of creation ensures that we get the same order.

Nonetheless, why is the order of the keys of the dictionary not sufficient ? We have an ordering of instances of class MIPVariable inside MixedIntegerLinearProgram (it's a list), and then we have the order of the keys.

[mkoeppe]

comment:7

No, the mapping to backend indices is created in MIPVariable.__getitem__, which calls backend.add_variable.
This is why just referencing e[edge] creates the order.

[mkoeppe]

comment:8

Also see:
#20773 - MixedIntegerLinearProgram.new_variable could optionally take a "static" list of component indices

This could be a nice idiomatic way to ensure consecutive backend indices of a MIPVariable's component variables.

[mkoeppe]

comment:9

Also see the proposed new method MixedIntegerLinearProgram._linear_variable_index in
sagemath/sagetrac-mirror@ca1298b
on the branch of #20656 - MixedIntegerLinearProgram: Remove _variables dictionary,
which obtains the mapping from MIPVariable components to backend indices.

[mkoeppe]

comment:10

#20773 now has an implementation, please review.

[sagetrac-tmonteil]

comment:11

Thanks for the pointers, the _linear_variable_index proposed in #20656 is somehow what i want (actually, i have a raw e[edge].dict().keys()[0] in my own code, but how to explain such a construction while promoting Sage to a newcomer !). However, i do not understand why you made it a hidden method, since the end user will use it to go back-and-forth between the milp and the polyhedron. Perhaps, on the MixedIntegerLinearProgram side, one could also have a p.get_variable_index()(e) method so that it can be easily discovered (not sure about that though).

[mkoeppe]

comment:12

It's fine with me to make it a public method. If you want, go ahead and put this code from #20656 on some separate ticket.

[mkoeppe]

comment:13

Replying to @sagetrac-tmonteil:

Perhaps, on the MixedIntegerLinearProgram side, one could also have a p.get_variable_index()(e) method so that it can be easily discovered (not sure about that though).

I'd say let's first go for the linear_variable_index (or whatever more suitable name we could find...) and #20773 and see the combination leads to convenient user code.

[mkoeppe]

Branch: u/mkoeppe/mixedintegerlinearprogram_should_provide_a_way_to_get_the_variables_in_the_order_they_are_provided_to_the_polyhedron_method

[mkoeppe]

New commits:

db6571e

MixedIntegerLinearProgram.polyhedron: Store backend variable names as _names attribute

[mkoeppe]

Commit: db6571e

[mkoeppe]

Author: Matthias Koeppe