Opened 15 months ago

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

Reported by: Owned by: tmonteil major sage-8.4 linear programming jipilab, mkoeppe, moritz, vdelecroix N/A

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

### comment:1 Changed 15 months ago by tmonteil

• Cc jipilab mkoeppe moritz vdelecroix added

### comment:2 follow-up: ↓ 8 Changed 15 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 15 months ago by dcoudert (previous) (diff)

### comment:3 follow-up: ↓ 4 Changed 15 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: ↓ 6 Changed 15 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).

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

``` for edge in G.edges(labels=False):
```

to

```[ e[edge] for edge in G.edges(labels=False) ]
```
Last edited 15 months ago by mkoeppe (previous) (diff)

### comment:5 Changed 15 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 15 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 15 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 15 months ago by mkoeppe (previous) (diff)

### comment:8 in reply to: ↑ 2 Changed 15 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 15 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 15 months ago by mkoeppe

#20773 now has an implementation, please review.

### comment:11 follow-up: ↓ 13 Changed 15 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 15 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 15 months ago by mkoeppe

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.