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$
5
  • $\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, 2019 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, 2019 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$
    – KGM
    Nov 5, 2019 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$
    – KGM
    Nov 5, 2019 at 13:55
  • $\begingroup$ For the record: I sent my R script to @dipak narayan offline. $\endgroup$
    – prubin
    Nov 5, 2019 at 16:30

3 Answers 3

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.

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

$\endgroup$
3
  • $\begingroup$ is diving heuristix expected to deliver better solution then the relaxation and rouning approach you mentiond? $\endgroup$
    – KGM
    Nov 1, 2019 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$
    – KGM
    Nov 1, 2019 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, 2019 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.)

$\endgroup$
1
  • 1
    $\begingroup$ please note that $x_i$ is not a binary variable, its an integer variable! $\endgroup$
    – KGM
    Nov 1, 2019 at 13:19

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.