Is there a heuristic approach to the MILP problem?

Question

I have the following optimization problem which is a MILP. I can solve it with a MILP solver.

\begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,\quad\forall c\in\{1,2,\cdots,C\}\\&\quad\sum_{n=1}^{N} x_n = M\end{align}

where

• $B$ is a binary matrix of size $N\times C$

• $d$ is a known vector of the positive numbers of size $1\times C$

• $M$ is a known parameter

• $x_n$ is an optimization variable (integer variable, $x_n\ge 0$, $x_n\in\{0,1,2,3,\cdots,M\}$)

• $t$ is also an optimization variable (integer/continuous)

Therefore, I am looking for a heuristic solution to the problem above.

$"EDIT"$

I have $C=10$, $N=6$, and $M=50$. Each row of $B$ has 3 ones. $d=\begin{bmatrix} 32 & 14 & 18 & 20 & 10 & 15 & 10 & 12 & 16 & 18 \end{bmatrix}$

With @prubin's approach:

Lets say, the first 5 rows of B looks like this

$\begin{bmatrix} 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ \end{bmatrix}$

With the approach, we will have $M$ iterations. In each iteration, we increase one of the variables $x_n,n=1,2,\cdots,N$ by 1.

Answer 1

There are a variety of heuristics and metaheuristics (not necessarily using LP) that you could employ. If we set $S_c = \{n : B_{n,c}=1\}$, we can rewrite the problem as $$\begin{align*} \min_{t} & \quad t\\ \text{s.t.} & \quad\left|\sum_{n\in S_{c}}x_{n}-d_{c}\right|\le t,\quad\forall c\in\{1,2,\cdots,C\}\\ & \quad\sum_{n=1}^{N}x_{n}=M. \end{align*}$$A simple greedy heuristic is to start with $x_n=0\,\forall n$ and, in each iteration, bump one of the $x$ variables up by 1, selecting the $x_n$ that most improves (or least degrades) $t$, until the equality constraint is satisfied. The problem would be amenable to any of the "usual" suspects among metaheuristics (simulated annealing, tabu search, genetic algorithms) with proper adjustments to handle the equality constraint.

Answer 2

You can solve the LP relaxation and round the resulting solution $x^*$, being careful to preserve the equality constraint. Then take $t=\max_c |\sum_n B_{n,c} x_n - d_c|$. There are lots of choices for rounding methods, but two natural choices are:

1. Let $x = \lfloor x^* \rfloor$ and $R=M-\sum_n x_n$. In descending order of $x^*_n$, let $x_n = x_n+1$ for the top $R$ values.
2. Let $x = \lfloor x^* \rfloor$. In descending order of $x^*_n - \lfloor x^*_n \rfloor$, let $x_n = x_n+1$ for the top $R$ values.

If you don't mind solving multiple LPs, you can round only one variable at a time, permanently fixing it to that value. This is sometimes called a diving heuristic.

Answer 3

Add penalty terms to nudge variables toward integers. For example, for binary variables, add piecewise-linear penalties $$ 100 \times \text{min}( x_i, 1 - x_i ), \ 0 \leq x_i \leq 1 . $$ In the general case, you could run two passes:

1. plain LP $\to$ some variables that you want to be ints (not too many)
2. penalize those as above.

Rounding, @Rob Pratt's answer, is certainly simpler.

(By the way, GLPK does MILP, and is 100 % opensource.)