2
$\begingroup$

Consider the mixed integer program $$Ax\leq b$$ $$By\leq c$$ $$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer variables of dimension $n$ and $y$ are real variables.

Because of the quadratic conditions this problems is in general $NP$ hard.

Is it possible convert this into exponentially larger mixed linear integer program by blowing up the number of integer variables only to a polynomial in $n$?

The remaining problem will be exponential time solvable as original one and would still be np hard.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Mixed integer Linear Program (MILP), i.e., with no quadratic constraints, is already in general NP hard, even without quadratic constraints.

If the problem had only continuous variables, it could be converted to a MILP via the Karush Kuhn Tucker conditions, which requires introduction of binary variables to handle the complementarity constraints occurring in the KKT conditions.

If the problem had only some mixture of binary and general integer variables, then with introduction of a large number of variables and constraints, it could be converted to a MILP.

However, quadratic terms in which both variables in the term are continuous can not be "linearized" via introduction of binary variables and additional constraints. The presence also of binary or general integer variables in the problem renders the KKT conditions inapplicable. Therefore, there is no MILP formulation, with any number of variables or constraints, into which the mixed quadratic problem can be transformed.

If you want to effectively solve this problem, don't aspire to convert it into a MILP, rather, solve it with a branch and bound mixed integer solver which can natively handle quadratic constraints. If the objective is linear or convex quadratic, and C is symmetric positive semidefinite, then you can solve with MIQCQP (Mixed Integer Quadraticaly Constrained Quadratic Program) or MISOCP (Mixed Integer Second Order Cone Problem) solvers, such as CPLEX, GUROBI, or MOSEK

Improve this answer
$\endgroup$
3
  • $\begingroup$ A bit confusing since you also say "convert this into exponentially larger mixed linear integer program". Anyhow, I believe my approach can be handled in the worst case with O(log(Upper bound - lower bound on x)^2 * n^2) added binary variables and constraints, where n is problem dimension. If we consider the lower and upper bounds of the integer variables to be fixed, then it is O(n^2), so not O(n) if that is what you are seeking. I don't see how you would do O(n) unless there were additional structure in the problem. This binary expansion is probably a terrible way to solve the problem. $\endgroup$
    – Mark L. Stone
    Commented Jun 14, 2018 at 23:12
  • $\begingroup$ So you're willing to have a large number of constraints, but not variables? $\endgroup$
    – Mark L. Stone
    Commented Jun 15, 2018 at 1:12
  • 1
    $\begingroup$ If you want to effectively solve this problem, don;t try to convert it into a MILP, rather, solve it with a branch and bound mixed integer solver which can natively handle quadratic constraints. If objective is linear or convex quadratic, and C is positive semidefinite then you can solve with MIQCQP or MISOCP. solvers, such as CPLEX, GUROBI, MOSEK. $\endgroup$
    – Mark L. Stone
    Commented Jun 15, 2018 at 1:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .