6
$\begingroup$

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. This one I posted here Is there a heuristic approach to the MILP problem?

Since I have an additional but very important constraint, I am putting it as a new post. I am looking for a heuristic approach to solve this problem. Any Hint?

\begin{alignat}{2}\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\\ &\quad x_n\le M y_n, \quad\forall n\\ &\quad\sum_{n=1}^N y_n \le 3 \end{alignat}

VERY IMPORTANT

As this a part of another problem, I found that this is not serving what I actually needed. I want to put one more constraint. There can be only a given number of non-zero $x_n$, for example, for the previous example, let say, we can have a maximum $3$ non-zero $x_n$s.

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\}$)

  • $y_n$ is a binary variable

  • $t$ is also an optimization variable (integer/continuous)

@prubin has suggested a reformulation of the problem as

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.

$\endgroup$
  • $\begingroup$ The heuristic I previously suggested could be adapted here, by adding a restriction that once three different x variables have been bumped, you are limited to using just those three (or however many the limit on nonzeroes is). I don't know that it would be a very good heuristic, though. $\endgroup$ – prubin Nov 6 '19 at 22:52
5
$\begingroup$

Introduce binary variables $y_n$ and constraints \begin{align} x_n &\le M y_n &&\text{for all $n$}\\ \sum_n y_n &\le 3 \end{align}

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ For once, $M$ is actually the right value to use for big-M. :) $\endgroup$ – RobPratt Nov 6 '19 at 13:14
1
$\begingroup$

Here is a modification of the bumping heuristic, assuming that you are limited to using $K$ of the $x$ variables (so $K=3$ in your example):

  1. Select $K$ distinct values of the index $n$ randomly.
  2. Apply the bumping heuristic, but limit it to bumping those $K$ variables. Note that the heuristic may not bump all of them.
  3. Record the new solution if it beats the previous incumbent.
  4. Repeat ad nauseum.
| improve this answer | |
$\endgroup$

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.