# Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case

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?
• 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$? Oct 21 at 11:24
• 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. Oct 21 at 11:34
• However, if you have a polynomial solution for the case where $a_i = b_i = c_i$, I would enjoy to read it. Oct 21 at 11:45