binary programming with non-convex objective function

Question

I have a non-convex binary programming problem: \begin{align} \min_{x,y,z}~& A^\top z + x^\top H y \\ \text{s.t} &\quad z\in \mathbb{Z}^+,\\ &\quad 0\leq z\leq 1, \\ &\quad y_{min}z \leq y \leq y_{max}z,\\ &\quad Cy-Dx=0, \\ \end{align} where $x\in\Re^{n}$, $y\in\Re^{n}$, $C$ and $D$ are given full rank square matrices. Does anyone know how to deal non-convex term $x^\top H y$ in the objective function?

Linearize? or Change of variable? And how to do it?

Many Thanks!

Answer 1

It depends on the data. If $x$ is given uniquely by solving the system of equations, $x = Gy$, you can simply check if $G^TH+HG$ is positive semidefinite. If it is, you are done as you have a convex mixed-integer QP. If it is indefinite/negative definite, or your equation is underdetermined in $x$, you will not arrive at a convex MIQP, and you have to take another approach.

One possibility is to look at the problem as a bilevel program, where you look at the problem w.r.t $x$ and $y$ as an inner nonconvex QP with $z$ as a parameter, and then on the outer stage you optimize for $z$. When doing so, you can replace optimality of $x$ and $y$ with kkt conditions (a nonconvex QP can be solved by writing KKT conditions using binary variables, and then using the fact that the quadratic indefinite objective can be written as a linear function of the duals, and the "right-and-side" of the inequalities. The only remaining problem then is that the right-hand-side in the inner program involves $z$, so the normally linear objective will actually be bilinear in $z$ and the duals. However, as $z$ is binary, this expression can be linearized.)

Pretty involved perhaps, but here is an example using the MATLAB toolbox YALMIP just as a proof-of-concept.

% Generate random problem
n = 3;
m = 2;
H = randn(m,n);
A = randn(n,1);
ymin = -rand(n,1);
ymax = rand(n,1);

x = sdpvar(m,1);
y = sdpvar(n,1);
z = binvar(n,1);

Model = [ymin.*z <= y <= ymax.*z, x == randn(m,n)*y];

% Inner problem
Objective = x'*H*y;
% Derive KT conditions
[KKTModel,details] = kkt(Model,Objective,z);
% Express the indefinite quadratic using duals
newObjective = (details.c'*details.primal-details.b'*details.dual)/2;
% Big-M linearize since details.b involves binary parameters z
[LinearObjective, cut] = binmodel(newObjective, [0 <= details.dual <= 1e4]);
% Solve outer problem
optimize([Model, KKTModel, cut], A'*z+LinearObjective)
value([x;y;z])

% Compare with simply calling a global solver
optimize(Model,A'*z + x'*H*y,sdpsettings('solver','bmibnb'))
value([x;y;z])