8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 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 '19 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$ – dipak narayanan Nov 15 '19 at 17:51
  • $\begingroup$ Use $t_{new} - t$. $\endgroup$ – prubin Nov 16 '19 at 17:57
6
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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