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.
Questions:
- 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?
