Integer programming bi-indexed variables.

asked 2021-02-24 10:41:01 +0200

Cyrille gravatar image

updated 2021-02-24 11:34:26 +0200

Many integer programming programs as the following needed for Kemeny ranking

$$ \begin{array}{c} \text{minimiser} \sum_{i,j \in \mathcal{A}}\omega_{i,j} x_{i,j}+\omega_{j,i} x_{j,i}\\ \text{sous les contraintes} \\ x_{i,j}+ x_{j,i} = 1, \forall i \not=j\\ x_{i,j}+ x_{j,k}+ x_{k,i}\geq 1, \forall i \not=j\not=k\not=i \end{array} $$

I want to construct a function wich takes the vector or the list $\omega$ and return the solution. But to construct such a function iot will be safer for me not to be obliged to assign on variable with a index to all two indexed variables.

Is there a way ? My problem is in the enumeration of the constraints for high indexes.

edit retag flag offensive close merge delete


Why not represent $\omega$ as a dict, where tuples $(i,j)$ are mapped to the corresponding values? Or did I misunderstand your question?

Max Alekseyev gravatar imageMax Alekseyev ( 2021-02-24 16:42:31 +0200 )edit

You probably understand my question better than I. But I do not know how to do. A second possibility would be to create the matrices of zero and one associated with the constraints. But I do not know (even if I have a little idea how to construct them).

Cyrille gravatar imageCyrille ( 2021-02-24 18:24:42 +0200 )edit

Can you give a specific toy example of what you want to achieve?

Max Alekseyev gravatar imageMax Alekseyev ( 2021-02-24 18:35:07 +0200 )edit

Hello, @Cyrille! What I understand that you want to achieve is to create a Sage function that will receive the constants $\omega$ and return the corresponding solution to the MILP you wrote above. Am I correct? What I didn't understand was the final part of your question where you talk about two-index variables. Could you clarify that? Perhaps I can help you with this problem.

dsejas gravatar imagedsejas ( 2021-03-01 13:21:49 +0200 )edit