conda activate
pip install cvxpy
conda install -c conda-forge coin-or-cbc
pip install cylp
(Tested on macOS Monteray and Ubuntu 18.04)
The input is a 2D array(
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0]
[1 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0]
[1 0 1 0 0 1 0 1 0 0 0 1 0 0 0 0]
[1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0]
[1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1]
[0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1]
Define a box as one row of 16 columns.
some rows of
In the above example, row 0 and row 1 can't be put into the same box because both 14th columns of these two rows are 1. It's okay to put row 0, 8 and 9 into the same box.
The object is to find a way to pack these rows so the number of boxes is minimized. The way of packing can be described as a 1D array
Here is an sample packing for the above example:[0, 1, 0, 1, 2, 2, 3, 4, 5, 5].
CVXPY modeling of the problem can be found as the cvx_condense function in vector_packing.py. It's based on the following example: https://stackoverflow.com/questions/48866506/binpacking-multiple-constraints-weightvolume
Current maximum