2
$\begingroup$

I have a certain convex optimization problem which depends on the order of a set of $N$ objects. Meaning, for every possible ordering, I get a different convex optimization problem. My ultimate goal is to find the best optimal solution given all possible orderings. One way of doing that is by solving all $n!$ possible problems. A better way (I think) is to write the whole thing as one MILP and let MOSEK take care of the hard work. I did that as follows: I created $N$ binary variables for every object for a total of $N^2$ binary variables. Say the objects are $F_1,\ldots,F_N$ and the binary variables are $b_{kj}$ where $k,j\in\{1,\ldots,N\}$.

I let $$b_{kj} = \left\{ \begin{array}{ll} 1 & \text{if object $F_k$ goes into position $j$;} \\ 0 & \text{otherwise}. \end{array} \right.$$

In order to guarantee that every object goes into exactly one position, I force the following constraint for every $k$: $$\sum_{j=1}^N b_{kj} = 1$$ Also, in order to guarantee that every position receives exactly one object, I force the following constraint for every $j$: $$\sum_{k=1}^N b_{kj} = 1$$

This worked for me and I was able to solve the problem using MOSEK.

My first question is: is there a better way of doing this? Possibly with fewer than $N^2$ binary variables?

My second question is: Let's say I want object $p$ to come before object $q$. How do I force that in the constraints? The only idea I was able to come up with is the following. We must have the following implication for every $k \in \{1,\ldots,N-1\}$. $$b_{pk} = 1 \Rightarrow b_{qk} = \ldots = b_{qN} = 0$$ Which we translate into: $$b_{pk} = 0 \vee b_{qk} = \ldots = b_{qN} = 0$$ which would need additional binary variables to deal with due to the "OR". Is there a better idea?

Thank you

$\endgroup$
2
$\begingroup$

Encoding this constraint in a mixed integer linear programming formulation requires $n^{2}$ variables and doesn't work very well in practice for large $n$. An alternative is to go beyond integer linear programming to use a constraint programming system with support for the "alldiff" constraint.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.