Binary Optimization Problem With Quadratic Functional

binary-programminglinear algebralinear programmingoptimizationquadratic programming

So, I'm trying to solve this,
given $\Omega \in \mathbb{R}^{p \times n}$ and $c>0$:

$$
\min_{x\in \mathbb{R}^n} \{|| \Omega \cdot x ||\}
$$
Sustained to:
$$
\sum_{k=1}^{n} x_{k} = c
$$
$$
x\in \{0,1\}^n
$$

Basically, the problem consists of finding the appropiate configuration of vector $x$ (that has a fixed number of non-zero elements) such that the module of the matrix product with $\Omega$ minimizes. I've never solved an optimization problem with binary variables so I been trying to think different ways of approaching it but I'm not sure which path should I take (or if there's a better way of thinking this problem). Here are some of the things I came up with

  • Approach this problem as a Quadratic Optimization Problem. The thing is that I'm not sure how to include the fact that the variables are binary. For example, Matlab includes the function quadprog that solves this kind of problems but it only works with continuous variables.
  • Find a way to linearize the functional to minimize (though I don't think this is possible) in order to take advantage of linear programming methods. For example, Maltab includes a function intlinprog which can deal with linear integer optimization problems.
  • Use a genetic algorithm: I've already tried this using (again) Matlab's function ga but didn't give good results. Maybe I'm not translating well the problem to the function or maybe (for some reason) it's not the best way to approach this particular problem.
  • I also came up with the idea that there may exist some kind of Ising-inspired algorithm in which you flip randomly two elements $x(i)=1\rightarrow x(i)=0$, $x(j)=0\rightarrow x(j)=1$ and if the functional becomes smaller, you stay with that change, and if not, you got a probability for that flip to actually happen, related to the difference between the original and the new value of the functional.

So far, I've been trying to solve this problem computationally. However, if there exists an analitical approach, that will also be useful.
Does anyone have any suggiestion?

Best Answer

There are three approaches:

  1. Linearize the quadratic terms and use intlinprog.

  2. Use a mixed integer quadratic optimization solver such as cplex or gurobi.

  3. If $c$ is small you can list all feasible points.

Related Question