Consider the following mixed-integer linear programming (MILP):

\begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & 1 & \\ \text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\ & y_{i} \geq 0, &i=1 ,\dots, m\\ & z_{i} \geq 0, &i=1 ,\dots, m\\ & x_{i}+y_{i}+z_{i} = 1, &i=1 ,\dots, m\\ & \sum_{i=1}^m a_{i}x_{i} = \frac{\sum_{i=1}^m a_i}{3}\\ & \sum_{i=1}^m b_{i}y_{i} = \frac{\sum_{i=1}^m b_i}{3}\\ & \sum_{i=1}^m c_{i}z_{i} = \frac{\sum_{i=1}^m c_i}{3}\\ & \text{$x_{i}, y_{i}, z_{i}$ are integers for all $i \in \{1, ..., m\}$,} \\ & \text{except one $i \in \{1, ..., m\}$ for which $x_{i}, y_{i}, z_{i}$ are reals} \\ \end{array} \end{equation*}

It is already proved that if $a_{i} = b_{i} = c_{i}$, then the problem has a polynomial time solution.


  • Is this specific case of MILP can be resolved in polynomial time?
  • If not, how can I prove that this special case is NP-hard?
  • In general, are there some generic ways to prove that a specific MILP is NP-hard or has a polynomial-time solution?
  • $\begingroup$ It's not clear to me what you mean by your first question. Are you asking whether this problem can be solved in polynomial time? Are you referring to the case where $a_i = b_i = c_i$? $\endgroup$ Oct 21, 2021 at 11:24
  • $\begingroup$ If $a_i = b_i = c_i$, a polynomial time solution exists. My question is referring to the general case, where $a_i$, $b_i$ and $c_i$ can be equals or not. $\endgroup$ Oct 21, 2021 at 11:34
  • $\begingroup$ However, if you have a polynomial solution for the case where $a_i = b_i = c_i$, I would enjoy to read it. $\endgroup$ Oct 21, 2021 at 11:45


Your Answer

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

Browse other questions tagged or ask your own question.