# Why does changing this one thing in the Primal Effective Capacity Heuristic improve the solutions it generates for the MDK problem?

For a long-done project presentation, I implemented the Primal Effective Capacity (PECH) Heuristic to look for initial greedy solutions for the Multidimensional Knapsack (MDK) problem in Python. I looked into this specific heuristic because the class I was presenting to wanted a simple initial algorithm that was easy to understand, but also because my main PC only has 3GB of RAM and I needed in-place solving heuristic due to this limitation - loading large MDK problems into DoCplex always crashed my PC due to Mem Errors. Regardless, the definition of the MDK problem I was using is as follows:

$$\max z = \sum_{i\in N}c_ix_i$$

$$\text{Subject to: }\qquad\qquad\qquad\qquad\qquad\qquad$$ $$\sum_{i\in N}w_{ji}x_i\le b_j,\quad\forall j\in m$$ Where $$N$$ denotes the total number of items $$x_i$$, $$m$$ denotes the total number of bags $$b_j$$, $$c_i$$ denotes the cost of using item $$x_i$$, $$𝑤_{ji}$$ denotes the weight of using item $$x_i$$ in bag $$b_j$$. There are two formulations for $$x_i$$ that I am solving for each problem in which $$x_i$$ can either be binary or an integer.

The original steps of the PECH algorithm is as follows:

• Select a $$\alpha \in [0,1]$$
• Initialize all decision variables, $$x_i=0$$, for all $$i$$
• Initialize all the Effective Capacity, $$E$$, to be the set of all indices of $$x_i$$
• Then do the following while True:
• Compute the effective capacity for all items $$\bar y_i = \min_j \left(\lfloor \frac{\bar b_j}{w_{ji}}\rfloor : w_{ji} > 0 \right)\forall i\in E$$

• If $$\bar y_i = 0\quad\forall i \in E$$, then end the loop.

• Compute the improvement for all items: $$c_i\cdot \bar y_i,\quad\forall i\in E$$, then select the best improvement $$i^* = \arg\max_{i\in E}(c_i\cdot \bar y_i)$$

• Compute the improvement of the best element $$i^*$$: $$y_{i^*}=\min(\bar u_{i^*}, \max(1, \lfloor \alpha\cdot\bar y_{i^*}\rfloor))$$

• Update the improving decision variable: $$x_{i^*} = x_{i^*} + y_{i^*}$$

• Update the remaining capacities of each bag: $$b_j = b_j - w_{ji^*}\cdot y_{i^*},\quad\forall j$$

• Update upper bounds: $$u_{i^*} = u_{i^*}-y_{i^*}$$

• If $$u_{i^*} = 0$$ or $$\alpha = 1$$, then remove $$i^*$$ from $$E$$, and if $$E$$ is empty, then end the loop.

Report the final solution obtained.

Because I did not know at the time how to safely hot-remove indices $$i^*$$ from $$E$$ while not ruining the step involving $$i^*$$: $$y_{i^*}=\min(\bar u_{i^*}, \max(1, \lfloor \alpha\cdot\bar y_{i^*}\rfloor))$$, I changed the algorithm to become the following:

• Select a $$\alpha \in [0,1]$$
• Initialize all decision variables, $$x_i=0$$, for all $$i$$
• Initialize all the Effective Capacity, $$E$$, to be the set of all indices of $$x_i$$
• Initialize a integer counter $$t$$ with $$t=0$$
• Initialize a largest number $$M$$.
• Then do the following while True:
• (all of these steps are the same)

• If $$u_{i^*} = 0$$ or $$\alpha = 1$$, then set $$c_{i^*} = -M$$ and $$t=t+1$$, and if $$t$$ equals the amount of elements in $$E$$, then end the loop.

Report the final solution obtained.

I ended up figuring out later how to delete indexes from arrays, but one thing I noticed is that if I followed their original algorithm, I got a substantially much worse solution than the one I modified (both solutions are feasible). For example, for a binary 100 items and 5 bags knapsack problem, DoCplex reports an objective of $$59822$$, my modified PECH reports an objective of $$58386$$, and their original reports $$37896$$.

My question is this: Why did this simple change derive a better solution? Effectively, they both should be doing the same thing. I've been strongly thinking it was my code/implementation, but even when I had my professor and colleagues look at it and they said they didn't know and didn't see anything wrong or wierd (aside from the objective values).