Implementing Bemporad optimization algorithm

Question

I need to reproduce the results of a relatively old paper of a paper and one of the steps is to solve an IQP problem, the algorithm suggested is this one. Which I don't know it's the best way to do it since it's quite old (I have understanding of continuous optimization, but when it comes to discrete I know bits and pieces). Also I can't really find a C/C++ implementation of any IQP solver, but this one to me doesn't look particularly difficult to implement.

Section 3.2. Reports the algorithm which I'll write down here for reference:

1. Take the original MIQP, relax all integrality constraints, mark the relaxed QP with its number of guaranteed switches, i.e.−1. Set $f_{opt}=1$,$k_c=−1$,$x_{opt}=[1;...;1]$ and initialize with the relaxed QPthe list of problems to be solved.

2. If the list of problems is empty, terminate and output $f_{opt},x_{opt}$.

3. If there are problems on the list marked by $k_c$, select one of them, remove it from the list, and solve it.If the QP is feasible, denote its cost by $f*$ and its solution by $x*$. Go to step 5. If the QP is infeasible go to 2.

4. If there are no problems on the list marked by $k_c$,increase $k_c$ by 1 and go to 2.

5. Fathoming by worse cost: If $f*\geq f_{opt}$,then go to 2

6. Integer feasibility : If $f* < f_{opt}$ and $x*$ satisfies the integrality constraints, then set $f_{opt}=f*$ and $x_{opt}=x*$ .Go to 2

7. Feasibility but not integer feasibility Separate the problem. Mark the sub problems by the number of guaranteed switches in the fixed integer variables. Add the subproblems to the list of problems. Goto 3.

It's not 100% clear to me how I form a subproblem to be solved however (I guess this is step 7). Can you help?

From what I see in figure 2. I think the exploration is exhaustive (with the Outside first strategy). But a subtree isn't explored if it is not feasable.

I think this is the essence of the algorithm, unless I'm missing something.

Answer 1

Because all your variables are binary, you can linearize the problem by introducing, for $i<j$, variables $y_{i,j} \ge 0$ to represent the product $x_i x_j$, together with linear constraints \begin{align} y_{i,j} &\le x_i\\ y_{i,j} &\le x_j\\ y_{i,j} &\ge x_i+x_j−1 \end{align}

A derivation via conjunctive normal form is given here.

Now use an ILP solver.