An Optimization Problem With Permutation Function [closed]

Question

When I tried to solve an one-to-one assignment problem, I constructed it as the following optimization problem, which is a min-max optimization problem with the optimization objective being functions.

Define a permutation mapping $\sigma(\cdot):\mathcal{V}\longmapsto\mathcal{V}$ with $\mathcal{V}=\{1,2,\dots,N\}$, which can transform an integer in $\mathcal{V}$ consisting of $1,2,\dots,N$ into another integer. For instance, given a identity mapping $\sigma_0(\cdot)$, one has that $\sigma_0(i)=i$ for $i\in\mathcal{V}$. Given a constant matrix $T$ and its element can be denoted as $T_{i,j}$.

Now, I want to solve the optimization problem $\min_{\sigma}\max_{i\in\mathcal{V}}T_{\sigma(i),i}$, and what method should I use to solve it?

Answer 1

Let $S_m$ be the $0$-$1$ matrix with $S_{i,j} = 1$ if and only if $T_{i,j} \leq m$. Then $\min_\sigma \max_i T_{\sigma(i),i} \leq m$ if and only if the bipartite graph whose bipartite adjacency matrix is $S_m$ has a perfect matching. To find $\min_\sigma \max_i T_{\sigma(i),i}$, simply try as $m$ every $T_{i,j}$ in order and use your favorite efficient algorithm for bipartite perfect matching.

Answer 2

You can solve the problem via mixed integer linear programming as follows. For $i,j\in \mathcal{V}$, let binary decision variable $x_{ij}$ indicate whether $\sigma(i)=j$. Let decision variable $z$ represent $\max_{i\in \mathcal{V}} T_{\sigma(i),i}$. The problem is to minimize $z$ subject to \begin{align} \sum_{j\in \mathcal{V}} x_{ij} &=1 &&\text{for $i\in \mathcal{V}$} \tag1\label1 \\ \sum_{i\in \mathcal{V}} x_{ij} &=1 &&\text{for $j\in \mathcal{V}$} \tag2\label2 \\ \sum_{j\in \mathcal{V}} T_{ji} x_{ij} &\le z &&\text{for $i\in \mathcal{V}$} \tag3\label3 \end{align} Constraints \eqref{1} and \eqref{2} enforce that $\sigma$ is a permutation. Constraint \eqref{3} enforces the minimax objective.

Answer 3

Thanks to the idea of Bob Krueger, it seems that I have found an algorithm: Given a $m=\min_{i,j}T_{i,j}$, let $S_m$ be the 0-1 matrix with $S_{i,j}=1$ if and only if $T_{i,j}\leq m$. Then, look for a perfect matching of $S_m$. If the matching cannot be found, then let $m$ be the second-smallest $T_{i,j}$ (If it cannot be found, then third, fourth...); Else, find all of the matchings and pick the minimal matching with maximal $T_{i,j}$ from it.