Opened 5 months ago

Last modified 5 months ago

#26302 new enhancement

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

Reported by: tmonteil Owned by:
Priority: major Milestone: sage-8.4
Component: linear programming Keywords:
Cc: jipilab, mkoeppe, moritz, vdelecroix Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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.

Change History (13)

comment:1 Changed 5 months ago by tmonteil

  • Cc jipilab mkoeppe moritz vdelecroix added

comment:2 follow-up: Changed 5 months ago by dcoudert

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__.

Last edited 5 months ago by dcoudert (previous) (diff)

comment:3 follow-up: Changed 5 months ago by mkoeppe

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

comment:4 in reply to: ↑ 3 ; follow-up: Changed 5 months ago by mkoeppe

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) ]
Last edited 5 months ago by mkoeppe (previous) (diff)

comment:5 Changed 5 months ago by mkoeppe

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.

comment:6 in reply to: ↑ 4 Changed 5 months ago by dcoudert

[ 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.

comment:7 Changed 5 months ago by mkoeppe

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.

Last edited 5 months ago by mkoeppe (previous) (diff)

comment:8 in reply to: ↑ 2 Changed 5 months ago by mkoeppe

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.

comment:9 Changed 5 months ago by mkoeppe

Also see the proposed new method MixedIntegerLinearProgram._linear_variable_index in https://git.sagemath.org/sage.git/commit/?h=b7906ffd31c2007d81cb556d23b8b814d2faaebb&id=ca1298b4ec78844b4f5488978ef6e09e76af8ad1 on the branch of #20656 - MixedIntegerLinearProgram?: Remove _variables dictionary, which obtains the mapping from MIPVariable components to backend indices.

comment:10 Changed 5 months ago by mkoeppe

#20773 now has an implementation, please review.

comment:11 follow-up: Changed 5 months ago by tmonteil

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).

comment:12 Changed 5 months ago by mkoeppe

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.

comment:13 in reply to: ↑ 11 Changed 5 months ago by mkoeppe

Replying to 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.

Note: See TracTickets for help on using tickets.