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).
