10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – prubin Nov 4 '19 at 18:26
  • $\begingroup$ 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). $\endgroup$ – prubin Nov 4 '19 at 18:54
  • $\begingroup$ @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$! $\endgroup$ – dipak narayanan Nov 5 '19 at 13:40
  • $\begingroup$ @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$. $\endgroup$ – dipak narayanan Nov 5 '19 at 13:55
  • $\begingroup$ For the record: I sent my R script to @dipak narayan offline. $\endgroup$ – prubin Nov 5 '19 at 16:30
9
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I appied your technique to the problem at: or.stackexchange.com/questions/2978/…, but it is not working. $\endgroup$ – dipak narayanan Nov 3 '19 at 12:28
  • $\begingroup$ 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! $\endgroup$ – dipak narayanan Nov 4 '19 at 11:09
  • $\begingroup$ please see my edit with my code. $\endgroup$ – dipak narayanan Nov 4 '19 at 11:56
  • $\begingroup$ Sorry, I'm not a MATLAB user. $\endgroup$ – prubin Nov 4 '19 at 15:31
  • $\begingroup$ the same $x_n$ is being selected all the times! $\endgroup$ – dipak narayanan Nov 4 '19 at 15:35
10
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ is diving heuristix expected to deliver better solution then the relaxation and rouning approach you mentiond? $\endgroup$ – dipak narayanan Nov 1 '19 at 13:21
  • $\begingroup$ 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? $\endgroup$ – dipak narayanan Nov 1 '19 at 13:31
  • $\begingroup$ 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. $\endgroup$ – RobPratt Nov 1 '19 at 14:46
4
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ please note that $x_i$ is not a binary variable, its an integer variable! $\endgroup$ – dipak narayanan Nov 1 '19 at 13:19

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.