10

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.

KGM
  • 2,265
  • 7
  • 23
  • Addressing the question of tie-breaking, I would break ties randomly. That would allow me to restart after getting a solution (assuming there was at least one tie when producing that solution) and possibly get a different, maybe better, solution. – prubin Nov 04 '19 at 18:26
  • Using my heuristic below (with random tie breaking) and just the 6 rows you showed (so $N$ = 6), on one pass I got a solution $x=[12, 13, 10, 4, 5, 6], t=18$. With a restart, I got $x=[18, 12, 5, 2, 9, 4], t=18$. Another restart yielded $x=[12, 17, 11, 1, 7, 2], t=18$. Note that this does not guarantee 18 is the minimum for the truncated problem (although it well could be). – prubin Nov 04 '19 at 18:54
  • @prubin. Thanks for your clarification. I am somewhere stuck. I am not getting what you are getting as solutions. So, I have elaborated on my post. Please clarify me why and how I can bump one of the variables by 1 at each iteration. I am getting non-zero values only for $x_1$ and $x_2$! – KGM Nov 05 '19 at 13:40
  • @prubin, at each iteration, I define an empty vector $V$. I store the maximum values of left side vectors. Then I find a minimum of them. Example, after the first iteration, the vector $V$ is $V=[31\hspace{1mm} 31\hspace{1mm} 32\hspace{1mm} 32\hspace{1mm} 32\hspace{1mm} 32]$ and then min[V] is either the first element or second element in V. With random tie, it chooses , so I bump $x_1$ by one. The second iteration starts with $x$ initialized as $x=[1\hspace{1mm} 0\hspace{1mm} 0\hspace{1mm} 0\hspace{1mm} 0\hspace{1mm} 0]$. The first test under iteration 2 start with $x_1=2$, $x_n=0,n\neq 1$. – KGM Nov 05 '19 at 13:55
  • For the record: I sent my R script to @dipak narayan offline. – prubin Nov 05 '19 at 16:30

3 Answers3

10

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.

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • is diving heuristix expected to deliver better solution then the relaxation and rouning approach you mentiond? – KGM Nov 01 '19 at 13:21
  • Thank you for your answer. Can you provide a bit more details on diving heuristic for this particular problem. I do not mind solving multiple LPs. So, this is an iterative approach? How to choose the variable for rounding at each step, with least rounding gap? – KGM Nov 01 '19 at 13:31
  • Yes, I would expect diving to do better than rounding everything based on one LP solve. For diving, you are free to choose which variable to round (and fix) at each step. Least fractional (closest to integer) is the one recommended in Wolsey's Integer Programming (1998), Section 12.5. – RobPratt Nov 01 '19 at 14:46
9

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • I appied your technique to the problem at: https://or.stackexchange.com/questions/2978/is-there-a-greedy-heuristic-approach-to-the-milp-problem, but it is not working. – KGM Nov 03 '19 at 12:28
  • what do you mean by "selecting the $x_n$ that most improves $t$"? Do we need to update the $d_c$ after each iteration? For me, it is selecting the same $x_n$ for all the iterations! – KGM Nov 04 '19 at 11:09
  • please see my edit with my code. – KGM Nov 04 '19 at 11:56
  • Sorry, I'm not a MATLAB user. – prubin Nov 04 '19 at 15:31
  • the same $x_n$ is being selected all the times! – KGM Nov 04 '19 at 15:35
  • I edited my answer just now. Depending on the $d_c$ values, it's possible that at some iteration there is no $n$ where an increase in $x_n$ improves $t$. In fact, bumping any $x_n$ may increase $t$, but due to the equality constraint you still need to do so. In that case, bump the $x_n$ that causes the least increase in $t$. – prubin Nov 04 '19 at 15:37
  • thanks for your clarification. I have edited (added an example) my post. Would you please comment on this. – KGM Nov 04 '19 at 17:10
4

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

denis
  • 141
  • 2