Quadratic cost having mixed integer linear constraints

95 Views Asked by At

I have a problem of the following form:

$$\min_{\textbf{x},\textbf{y}} \qquad \textbf{x}^{\top} \mathbf{D}_1 \textbf{x} + \textbf{y}^{\top} \mathbf{D}_2 \textbf{y}+\textbf{c}_1^{\top} \textbf{x} +\textbf{c}_2^{\top} \textbf{y}$$ $$\text{st,} \quad \mathbf{A} \textbf{x} + \mathbf{B} \textbf{y}\geq \textbf{b},$$ $$\qquad \mathbf{F} \textbf{x} = \textbf{a},$$ $$\qquad \mathbf{C} \textbf{y}=\textbf{d},$$ $$ \textbf{x} \in \mathbb{R}^n, \ \textbf{y} \in \{ 0,1 \}^m,$$

where $\mathbf{D}_1, \mathbf{D}_2$ are diagonal matrices.

Can we use CPLEX to solve it? Is there any other solver which can provide a good solution to this problem? At least, I need a good "feasible" solution, if not the optimal.

1

There are 1 best solutions below

3
On BEST ANSWER

If the diagonal entries of the $D$ matrices are nonnegative, then yes, CPLEX can solve this. So can most other MIP solvers, including Xpress MP, Gurobi (I'm pretty sure) and the open source CBC solver.

Actually, you only need $D_1$ to be nonnegative, since $y^T D_2 y$ can be linearized.