# Is there a greedy heuristic approach to the MILP problem?

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.

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.

• @dipaknarayanan I'd suggest that you add this additional information to your question as it can help others in providing better answers. – EhsanK Nov 3 '19 at 16:32
• @prubin, how do I measure the change? lets say $t=0.60$. we start with $n=1$. with $x_1=x_1+1$, $\delta_n=t-t_{\rm new}$ or $\delta_n=t_{\rm new}-t$? Same for $\gamma_n$, how to measure the change? – dipak narayanan Nov 15 '19 at 17:51
• Use $t_{new} - t$. – prubin Nov 16 '19 at 17:57

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

• Yes, I could solve it with your approach in the linked post. But I need some solution even without LP. – dipak narayanan Nov 3 '19 at 15:00