Integer programming gives wrong values with duplicate input values

[traversc]

Below gives wrong results:

values = [18, 12, 22, 22]
prtpy.partition(algorithm=prtpy.partitioning.integer_programming, numbins=2, items=values, outputtype=prtpy.out.PartitionAndSums)

Bin #0: [18, 12], sum=30.0
Bin #1: [22, 22], sum=44.0

Using a dictionary works correctly:

vdict = {i:values[i] for i in range(len(values))}
prtpy.partition(algorithm=prtpy.partitioning.integer_programming, numbins=2, items=vdict, outputtype=prtpy.out.PartitionAndSums)

Bin #0: [1, 3], sum=34.0
Bin #1: [0, 2], sum=40.0

Greedy works fine

prtpy.partition(algorithm=prtpy.partitioning.greedy, numbins=2, items=values, outputtype=prtpy.out.PartitionAndSums)
Bin #0: [22, 18], sum=40.0
Bin #1: [22, 12], sum=34.0

Nice package, thanks!

[erelsgl]

I added your example to here and it seems to work fine both on my computer and with GitHub actions. What Python version do you use?

[traversc]

Python version 3.8.3, prtpy version 0.7.0 from pip install prtpy.

[erelsgl]

I have Python 3.8.10. I ran the code in a virtual environment and it works fine:

(.venv38) PS D:\Dropbox\papers\ElectricityDivision__Dinesh\Code\prtpy> pip install prtpy
Collecting prtpy
  Using cached prtpy-0.7.0-py3-none-any.whl (24 kB)
Collecting numpy>=1.21.3
  Downloading numpy-1.23.1-cp38-cp38-win_amd64.whl (14.7 MB)
     |████████████████████████████████| 14.7 MB 3.3 MB/s
Collecting scipy>=1.6.1
  Downloading scipy-1.8.1-cp38-cp38-win_amd64.whl (36.9 MB)
     |████████████████████████████████| 36.9 MB 2.2 MB/s
Collecting mip
  Using cached mip-1.14.0-py3-none-any.whl (15.3 MB)
Collecting cffi
  Downloading cffi-1.15.1-cp38-cp38-win_amd64.whl (178 kB)
     |████████████████████████████████| 178 kB 3.3 MB/s
Collecting pycparser
  Using cached pycparser-2.21-py2.py3-none-any.whl (118 kB)
Installing collected packages: pycparser, numpy, cffi, scipy, mip, prtpy
Successfully installed cffi-1.15.1 mip-1.14.0 numpy-1.23.1 prtpy-0.7.0 pycparser-2.21 scipy-1.8.1      
WARNING: You are using pip version 21.1.1; however, version 22.1.2 is available.
You should consider upgrading via the 'd:\dropbox\papers\electricitydivision__dinesh\code\prtpy\.venv38\scripts\python.exe -m pip\scripts\python.exe -m pip install --upgrade pip' command.

(.venv38) PS D:\Dropbox\papers\ElectricityDivision__Dinesh\Code\prtpy> python
Python 3.8.10 (tags/v3.8.10:3d8993a, May  3 2021, 11:48:03) [MSC v.1928 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import prtpy
>>> values = [18, 12, 22, 22]
>>> prtpy.partition(algorithm=prtpy.partitioning.integer_programming, numbins=2, items=values, outputtype=prtpy.out.PartitionAndSums)
Bin #0: [12, 22], sum=34.0
Bin #1: [18, 22], sum=40.0
>>>

[traversc]

I did this in a fresh env on two different systems (see below).

conda create --name test_env python=3.8
conda activate test_env
pip install prtpy
Collecting prtpy
  Downloading prtpy-0.7.0-py3-none-any.whl (24 kB)
Collecting numpy>=1.21.3
  Downloading numpy-1.23.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (17.1 MB)
     |████████████████████████████████| 17.1 MB 6.5 MB/s
Collecting mip
  Downloading mip-1.14.0-py3-none-any.whl (15.3 MB)
     |████████████████████████████████| 15.3 MB 6.7 MB/s
Collecting scipy>=1.6.1
  Downloading scipy-1.8.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (41.6 MB)
     |████████████████████████████████| 41.6 MB 6.9 MB/s
Collecting cffi
  Downloading cffi-1.15.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (442 kB)
     |████████████████████████████████| 442 kB 10.6 MB/s
Collecting pycparser
  Downloading pycparser-2.21-py2.py3-none-any.whl (118 kB)
     |████████████████████████████████| 118 kB 11.1 MB/s
Installing collected packages: pycparser, numpy, cffi, scipy, mip, prtpy
Successfully installed cffi-1.15.1 mip-1.14.0 numpy-1.23.1 prtpy-0.7.0 pycparser-2.21 scipy-1.8.1

python
Python 3.8.13 (default, Mar 28 2022, 11:38:47)
[GCC 7.5.0] :: Anaconda, Inc. on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import prtpy
>>> values = [18, 12, 22, 22]
>>> prtpy.partition(algorithm=prtpy.partitioning.integer_programming, numbins=2, items=values, outputtype=prtpy.out.PartitionAndSums)
Bin #0: [18, 12], sum=30.0
Bin #1: [22, 22], sum=44.0

Could you try it with pip install prtpy --no-cache-dir? (pip may have cached a the github version)

[erelsgl]

I tried this and got the correct results.

I have now uploaded to pip a brand new version - 0.8.0. This particular example is in the doctests and it passes in GitHub actions. Can you check again with the new version?

[traversc]

Thanks, 0.8.0 works but the output is a plain tuple:

>>> import prtpy
>>> values = [18, 12, 22, 22]
>>> prtpy.partition(algorithm=prtpy.partitioning.integer_programming, numbins=2, items=values, outputtype=prtpy.out.Part
itionAndSums)
(array([34., 40.]), [[12, 22], [18, 22]])

[erelsgl]

Right. I brought back the previous behavior.