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}


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


2 Answers 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.

  • 1
    $\begingroup$ @dipaknarayanan I'd suggest that you add this additional information to your question as it can help others in providing better answers. $\endgroup$
    – EhsanK
    Nov 3, 2019 at 16:32
  • $\begingroup$ @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? $\endgroup$
    – KGM
    Nov 15, 2019 at 17:51
  • $\begingroup$ Use $t_{new} - t$. $\endgroup$
    – prubin
    Nov 16, 2019 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$.

  • $\begingroup$ Yes, I could solve it with your approach in the linked post. But I need some solution even without LP. $\endgroup$
    – KGM
    Nov 3, 2019 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.