Integer programming formulation: which algorithms

Question

I have a complex problem that I have simplified coming to a simple integer linear programming formulation.

Given the scalar $K > 0$, the vectors $v(t) \in R^n$ and $b_i \in R^n, \forall i=1,\ldots,K$ are known. In particular $v(t)$ is the measured value (ex: every 10 minutes) while the $b_i$ are fixed (computed ones, previously). Consider that I have: $$K >> n,$$ i.e., I have to identify the presence of $K$ (ex: $K=20$) elements, each one of dimension $n$ (ex: $n=2$).

So, for every fixed $t$, the problem that I have to solve has the following formulation:

$$ \newcommand\norm[1]{\left\lVert#1\right\rVert} \begin{equation*}\begin{aligned} & \underset{x_i}{\text{minimize}} & & \norm{v - \sum_{i=1}^{K} b_i x_i}_{2} \\ & \text{subject to} & & x_i \in \{0,1\},\ \forall i = 1, \ldots, K. \end{aligned} \end{equation*}$$

Do you know which algorithms solve that formulation? In particular I am looking for an algorithm implemented in Python.

Answer 1

Contrary to what you wrote in the first sentence of the question, your problem is not an instance of integer linear programming (ILP) and cannot be formulated as an ILP problem.

If you used the $L_1$ norm (instead of the $L_2$ norm), it could be formulated as an ILP problem. You'd introduce additional variables $t_1,\dots,t_n$, add the linear inequalities

$$-t_j \le \left(v - \sum_{i=1}^K b_ix_i \right)_j \le t_j$$

where $(\cdots)_j$ denotes the $j$th coefficient of the vector, and then minimize the objective function $t_1+\dots+t_n$.

With the $L_2$ norm, this is no longer an ILP problem. It is an instance of integer quadratic programming. You could try applying an off-the-shelf solver for mixed-integer quadratic programming (MIQP). However, MIQP is pretty tough in general, so I don't know whether this will be effective.

As another alternative, you could relax your MIQP instance to an instance of quadratic programming or semidefinitive programming, solve for a solution in the reals, and then round each real number to the nearest integer (or use randomized rounding), and hope that the resulting solution is "pretty good". This might be more computationally feasible (as quadratic programming / semidefinitive programming over the reals is easier than MIQP) but there are no guarantees on the quality of the resulting solution; it might be arbitrarily bad.

Your problem seems related to the Closest Vector Problem (CVP) in lattices, which is believed to be hard. Here you have the additional constraint that the coefficients be 0 or 1 (instead of them being arbitrary integers). If $n$ is not too large, you might be able to use existing algorithms, like LLL basis reduction. I don't know whether this will work or not.

Answer 2

You may reparameterize $x_i$ as $x_i = sigmoid(\alpha \cdot z_i), z_i \in \mathbb{R}$, with $\alpha$ being a constant such that $\alpha \gg 1$, and then proceed with your favorite optimization method for finding $z_i$, and from there $x_i$.

This, of course, may present problems, as $x_i$ are no longer bounded in $\{0, 1\}$, but may suffice your use case.

Answer 3

Another option could be to model your problem as a bayesian linear regression where $x_i$ are random variables that follow a Bernoulli distribution with probability $p_i$, that is, $x_i \sim Bernoulli (p_i)$, and $v \sim \mathcal{N}(x^T b, \sigma^2)$.

The posterior distribution of $p_i$ would enable you to tell the values of $x_i$ that most likely fit with the observed data. These posterior distributions may be inferred via MCMC or variational inference.

The three main frameworks to implement bayesian models in Python are pymc3 (example), edward (example) and pystan (example). The three of them allow straighforward implementation of bayesian linear regression as formulated above.