A heuristic approach to solve a MILP problem?

Question

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.

Answer 1

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}

Answer 2

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.