2
$\begingroup$

During my studies I recently met the problem of finding a binary variable $x \in \lbrace 0,1 \rbrace ^n$ that solves

$$Ax=b, \qquad \|x\|_1 \leq \delta$$

I am curious how this system can be solved. One idea I have is to consider it as the feasible region of an integer linear program and apply some of the strategies developed there. Therefore, I am currently searching for papers solving binary integer programs.

Does anyone know some good papers/books that treat this problem? Or different approaches that might work? And does it have a name under which I can search for it?

$\endgroup$
2
$\begingroup$

You are correct that this can be framed as a binary integer program. I do not recognize it as a problem that has its own name or "niche" within the more general area of integer linear programming. It can certainly be solved using any integer programming code, subject to the usual issue that a large enough dimension (referring to both $n$ and the dimension of $b$) may result in the solver running out of time or memory.

Note that the norm constraint $\vert\vert x \vert\vert_1 \le \delta$ can be rewritten as $\sum_{i=1}^n x_i \le \delta$.

There being no specified objective function, you could just minimize 0, or perhaps minimize (or maximize) $\sum_{i=1}^n x_i$.

$\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.