Reduce optimality gap and get a solution faster

Question

I have a maximization problem that I know that the maximum value of the objective function should be 6000. When solving the problem using Xpress, I end up on something like the following:

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
   73317   912.000000  50028.29999     11  43521     64   98.18%     643    295
   74319   912.000000  50012.88158     11  44186     88   98.18%     262    298
   75325   912.000000  50012.88158     11  44921     94   98.18%     320    301
   76327   912.000000  50012.88158     11  45381     56   98.18%     432    304
   77327   912.000000  50012.88158     11  46218     52   98.18%     331    306
   78330   912.000000  50012.88158     11  46755    104   98.18%     404    308
   79331   912.000000  48985.66896     11  47487     56   98.14%     170    311
   80334   912.000000  48985.66896     11  48161     95   98.14%     185    313
   81334   912.000000  48985.66896     11  49064    114   98.14%     516    316
   82335   912.000000  48985.66896     11  49474     47   98.14%     566    318
   83335   912.000000  48985.66896     11  50223     64   98.14%     462    321
   84336   912.000000  48985.66896     11  50990     62   98.14%     445    323
   85336   912.000000  48616.50212     11  51572     86   98.12%     392    326
   86336   912.000000  48616.50212     11  52306     46   98.12%     717    329
   87341   912.000000  48616.50212     11  52893     56   98.12%     351    331
   88342   912.000000  48616.50212     11  53629     34   98.12%     585    334
   89342   912.000000  48616.50212     11  54287    104   98.12%     246    336
   90342   912.000000  48616.50212     11  54823     35   98.12%     553    338
   91344   912.000000  44334.25280     11  55541     51   97.94%     446    341
   92344   912.000000  44334.25280     11  56097     39   97.94%     672    343

My best solution is stack (it is not optimal) but the best bound is not getting lower. At the same time the number of active nodes it gets bigger and bigger, making me wondering if it will manage to find an optimal solution in reasonable time.

I have tried to add a constraint to the objective function to be less than 6000 but it did not help.

Is there a good way to make the gap getting smaller, and come earlier to the optimal solution? Or do you have any other recommendations? Thanks!

EDIT

Imagine a 1d array which has the required number of different groceries. We have also 20 types of bags and each type contains different groceries. So a bag contains 1 apple, 1 orange, another bag contains 1 croissant and 1 apricot etc. We need to find how many of each bag we should buy to cover as much as we can the requirements, and at the same time respecting the budget we have. We want to cover as much as we can but also not having large gaps in some products. So the only constraint is the budget that we have (among with the others needed for the formulation - binary variables etc).

EDIT 2

I have the required number of each product in a 1d array: $\ N_{j}$

I can buy up to 20 bags of groceries, and I want to cover as better as possible my grocery needs by buying the bags. So I don't want to have a shortage of apples for example. Also, if I should have a shortage, I prefer having 1 less apple, and 1 less apricot than having less 2 apples. Also I would prefer to have 2 apples missing, compared to have 1apple, 1apricot and 1orange missing (total 3 items). I want to have as less shortages as possible. So I need different weights in my objective function.

I have created a 2d array $ a_{k,j} $ which has the groceries for each bag type. So, $ a_0 = [1, 2.. ] $ which is the number of each grocery in the bag type $ 0 $, and $ a_{0,0} = 1 $ means that we have 1 apple in the bag type $ 0 $.

Based on the bag types I will get, I will have the following groceries: $ \sum \limits_{i} n_{i}b_{i,j} = [2,4,3..] $ which means that I will have 2 apples, 4 apricots, 3 croissants etc.

My formulation is the following:
(1) $ \sum \limits_i n_i <= C $ and $ \sum \limits_i n_i >= C $
(2) $ n_i integer $ and (3) $ n_i >= 0 $
(4) $ q_{j,m} binary, m = \{0,1,2\} $
(5) $ \sum \limits_m q_{j,m} = 1 $
(6) $ \sum \limits_i n_i b_{i,j} - N_j >= -Mq_{j,0} + (-2 + \delta)q_{j,1} + (-1 + \delta)q_{j,2} $
(7) $ \sum \limits_i n_i b_{i,j} - N_j <= (-2)q_{j,0} + (-1)q_{j,1} + Mq_{j,2} $
(8) $ z_{j,m} integer $ and $ z_{j,m} >= 0, m = \{0,1,2\} $
(9) $ z_{j,m} <= Mq_{j,m} $
(10) $ z_{j,m} <= \sum \limits_i n_i b_{i,j} $
(11) $ z_{j,m} >= \sum \limits_i n_i b_{i,j} - (1-q_{j,m})M $

Objective: $ \sum \limits_j p(z_{j,0} - N_jq_{j,0}) + \theta (z_{j,1} - N_jq_{j,1}) + s(z_{j,2} - N_jq_{j,2}) $

Some Explanation: (a) total number of bags I can get
(b) $ n_i $ how many of each bag type I get
(c) binary variables - get value 1 if $ \sum \limits_i n_i b_{i,j} - N_j $ is in the range defined by (6) and (7)
(d) $ z_{j,m} $ constraints to define the value of $ z $. So when the binary variable $ q $ is 1 then $ z = \sum \limits_i n_i b_{i,j}$ else $ z = 0 $.
(e) $p, \theta, s $ are the weights assigned depending on the shortage I have in each grocery $ j $.

Answer 1

If my understanding of the problem is correct, the following formulation should be tighter. I am assuming the types of possible bags are predefined.

Let $x_i$ be the number of bags of type $i\in \{1,...,20\}$ that are selected in the solution. In bag $i$, you have $n_{i,k}$ groceries of type $k$.

You need the following requirements:

• at most 20 bags: $$ \sum_i x_i \le 20 \tag{1} $$
• groceries requirements: $$ \sum_{i| k \in i} n_{i,k} x_i \ge r_k \quad \mbox{for every grocery } k \tag{2} $$

Now, if this is not feasible, you want to satisfy your requirements as much as possible. You could introduce a new variable per grocery $y_k$ and replace constraints $(2)$ with $$ \sum_{i| k \in i} n_{i,k} x_i + y_k \ge r_k \quad \mbox{for every grocery } k \tag{3} $$ and minimize $\max_k{y_k}$.