# A heuristic approach to solve a MILP problem?

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.

• 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.
– prubin
Nov 6, 2019 at 22:52

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}
• For once, $M$ is actually the right value to use for big-M. :) Nov 6, 2019 at 13:14
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.