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
