0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Professor Bemporad's codes can be downloaded from cse.lab.imtlucca.it/~bemporad/hybrid/toolbox $\endgroup$ Jul 31 '20 at 15:13
  • $\begingroup$ It's matlab, I'd need C++. I guess it might be easy enough to convert though. It doesn't change the nature of my question anyway, which is how it works. $\endgroup$ Jul 31 '20 at 15:20
  • $\begingroup$ Are all your variables binary? $\endgroup$
    – RobPratt
    Jul 31 '20 at 15:34
  • $\begingroup$ Yes, they're. (By the way I just realized that "Outside strategy" is probably what I'm missing, to sure what data structure I would need to achieve that exploration.) $\endgroup$ Jul 31 '20 at 16:07
  • $\begingroup$ Links can become broken. Please include the full reference. $\endgroup$ Jul 31 '20 at 16:27
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.