Opened 12 months ago
Last modified 12 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 12 months ago by
- Cc jipilab mkoeppe moritz vdelecroix added
comment:2 follow-up: ↓ 8 Changed 12 months ago by
comment:3 follow-up: ↓ 4 Changed 12 months ago by
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: ↓ 6 Changed 12 months ago by
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) ]
comment:5 Changed 12 months ago by
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 lengthself.number_of_variables()
) to theMixedIntegerLinearProgram.get_values
method. If provided, it will take values from this vector instead of from the backend viabackend.get_variable_value
.
comment:6 in reply to: ↑ 4 Changed 12 months ago by
[ 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 12 months ago by
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.
comment:8 in reply to: ↑ 2 Changed 12 months ago by
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 12 months ago by
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 12 months ago by
#20773 now has an implementation, please review.
comment:11 follow-up: ↓ 13 Changed 12 months ago by
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 12 months ago by
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 12 months ago by
Replying to tmonteil:
Perhaps, on the
MixedIntegerLinearProgram
side, one could also have ap.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.
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__
.