Opened 2 years 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 2 years ago by tmonteil

• Cc jipilab mkoeppe moritz vdelecroix added

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

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

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

to

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

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

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

#20773 now has an implementation, please review.

### comment:11 follow-up: ↓ 13 Changed 2 years 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 2 years 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 2 years 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.