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**

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger