Is there a greedy heuristic approach to the MILP problem?

Question

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

\begin{alignat}{1}\max_{x_n,t}\,&\quad t\quad\\\text{s.t.}&\quad\sum_{n=1}^{N} x_n \,&= M\\&\quad\qquad\!s_c&\ge t d_c\end{alignat}

where

• $s_c=\sum\limits_{n=1}^{N} B_{n,c}x_{n}$

• $B$ is a given matrix of size $N\times C$ with elements $\ge 0$

• $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)

I want to transform this into an LP, not MILP. Let us say I do not have a MILP solver.

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

I have tried to use the solution suggested by @prubin for the problem at: Is there a heuristic approach to the MILP problem?, but this is not working. It is choosing the same row of $B$ at every iteration.

Answer 1

Unlike the problem from the linked post, the objective here is “flat” at the initial solution in the sense that increasing some $x_n$ by 1 unit will not change the objective value, which is initially 0. The LP rounding approaches still apply if you linearize the $\min_c$, which you can do by introducing $t$ with $t\le s_c/d_c$.

Answer 2

Here is a somewhat greedy heuristic. First, to simplify notation a bit, let $$f_{c}(x)=\frac{1}{d_c}\sum_{n=1}^N B_{n,c}x_n\, \forall c.$$ So we want to maximize $$t=\min_c f_c(x)$$ subject to $$\sum_n x_n = M.\quad (1)$$

Now start with some arbitrary (let's say randomly generated) $x$ satisfying (1). Calculate all the $f_c(x)$, and for each $n$ calculate two values: the change $\delta_n$ in $t$ if $x_n$ increases by 1, and the change $\gamma_n$ in $t$ if $x_n$ decreases by 1. (If $x_n=0$, set $\gamma_n=-\infty$, since $x_n$ cannot go below zero.) Choose $n$ that maximizes $\delta_n$ and $m$ that maximizes $\gamma_m$. If the net change $\delta_n + \gamma_m$ is positive, increase $x_n$ by 1 and decrease $x_m$ by 1, preserving satisfaction of (1), and repeat.

If the net change is less than or equal to zero, compare the current $t$ to the best solution so far. If it is better, record $x$ as the new best solution. At this point, you can either stop or generate a new random $x$ and continue from there.