ADMM Heuristic or rather stick to Branch and Bound?

by M.Zhobro   Last Updated May 28, 2018 10:20 AM

I'm intending on giving a solution to this MIQP, which should be faster than the one of solving the exact problem with GUROBI or CPLEX.(It muss not give always the global solution!)

The main problem is about optimization of a localization problem with a grid map, where $dx_m$, $dy_m$ and $dp_m$ are the displacement for the next iteration.

The constraint (2) guarantees that transmit power stays in the admissible range [$\overline{P}$, $\underline{P}$], while the constraints (2) and (3) assure that the update points stay in the range [$-w$,$w$], i.e in the observation area ($q_m$ and $r_m$ are respectively $dx_m$ and $dy_m$ from the previous iteration). The constraints (4) and (6) allow an update of maximal $\delta_i$

\begin{align} &\quad\min_{s_m,dx_m,dy_m,dp_m} \ \sum_{k=1..K} (f_k+\sum_{m=1..M}a_{km}dx_m+b_{km}dy_m+c_{km}dp_m)^2 \\ &\quad \text{s.t} \ dx_m,dy_m,dp_m \in \mathbb{R} \ (1)\\ &\quad s_m\underline{P} \leq dp_m \leq s_m \overline{P} \ (2)\\ &\quad -s_m(w+q_m) \leq dx_m \leq-s_m(w-q_m) \ (3)\\ &\quad -s_m(w+r_m) \leq dy_m \leq-s_m(w-r_m) \ (4)\\ &\quad -s_m \delta_i \leq dx_m \leq s_m \delta_i (5)\\ &\quad -s_m \delta_i \leq dy_m \leq s_m \delta_i \ (6)\\ &\quad s_m \in \text{{0,1}} \ \ \ \ \ (7)\\ &\quad \sum_{m=1..M} s_m = N \ (8) \end{align}

I tried the ADMM heuristic presented in the paper below. Since i couldn' transform the problem in the exact form presented there, I simpliefied the problem to a BIQP and tryed out the algorithm, which unfortunately gave very often no solution(or a very bad one).

Should I keep trying to find an ADMM heuristic which possibly offers a faster solution given a big number of grid points(equations) or stick to the branch and bound algorithms?

1.Reza Takapoui, Nicholas Moehle, Stephen Boyd and Alberto Bemporad : A simple effective heuristic for embedded mixed-integer quadratic programming



Related Questions


How to optimize for following cost function?

Updated March 13, 2018 00:20 AM

Mixed Integer Program for cash flow problem

Updated March 04, 2017 03:20 AM


MILP constraints with truth table

Updated February 10, 2018 05:20 AM