# Capturing the order of certain objects in an MILP

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

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.