Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Onedimensional - occassional errors in calculation - Windows build #5

Closed
lafar6502 opened this issue Aug 1, 2023 · 6 comments
Closed

Onedimensional - occassional errors in calculation - Windows build #5

lafar6502 opened this issue Aug 1, 2023 · 6 comments

Comments

@lafar6502
Copy link

lafar6502 commented Aug 1, 2023 •
edited
Loading

Hi, here is a problematic test case that i don't understand.
The problem is that calculation is not consistent. Sometimes a correct solution is found, and sometimes the results are wrong - some random bin is introduced that wasn't there in the inputs, or nonsensical results are printed.
This happens on Windows build from recent master branch. I didnt test on Linux.

my command line used for testing (always the same, im running this repeatedly):

onedim.exe --verbosity-level 2 --objective variable-sized-bin-packing --items items_ea6574d4ab0d40dfa23bc04e5b686dd9.csv --bins bins_ea6574d4ab0d40dfa23bc04e5b686dd9.csv -c solution_ea6574d4ab0d40dfa23bc04e5b686dd9.csv -t 3
copy solution_ea6574d4ab0d40dfa23bc04e5b686dd9.csv CON

The results are different on every run. In the attached case it seems totally wrong, like some data corruption:

TYPE,ID,COPIES,BIN,X,LX
BIN,1,1,0,0,7000
ITEM,0,1,0,0,290
ITEM,0,1,0,295,290
ITEM,0,1,0,590,290
ITEM,3,1,0,885,3351
ITEM,2,1,0,4241,2751
BIN,0,1,1,0,3000
ITEM,2,1,1,0,2751
BIN,0,1,2,0,3000
ITEM,1,1,2,0,1496
ITEM,1,1,2,1501,1496
BIN,5,1,3,0,4613937818241073152
ITEM,3,1,3,0,3351

sometimes it gets the result right:

TYPE,ID,COPIES,BIN,X,LX
BIN,1,1,0,0,7000
ITEM,0,1,0,0,290
ITEM,0,1,0,295,290
ITEM,0,1,0,590,290
ITEM,3,1,0,885,3351
ITEM,2,1,0,4241,2751
BIN,0,1,1,0,3000
ITEM,1,1,1,0,1496
ITEM,1,1,1,1501,1496
BIN,1,1,2,0,7000
ITEM,3,1,2,0,3351
ITEM,2,1,2,3356,2751

And sometimes result seems right, but it packs an item exceeding bin size to the last bin:

TYPE,ID,COPIES,BIN,X,LX
BIN,1,1,0,0,7000
ITEM,3,1,0,0,3351
ITEM,2,1,0,3356,2751
ITEM,0,1,0,6112,290
ITEM,0,1,0,6407,290
ITEM,0,1,0,6702,290
BIN,0,1,1,0,3000
ITEM,2,1,1,0,2751
BIN,0,1,2,0,3000
ITEM,1,1,2,0,1496
ITEM,1,1,2,1501,1496
BIN,0,1,3,0,3000
ITEM,3,1,3,0,3351

If the results are wrong, the command output shows (sometimes) that some extra bin type has been introduced, that's not present in the input bins file (like the bin no#5 in the first example above), or the 'Final statistics' section is missing entirely. Sometimes the results are wrong but there's no extra bin type, just the wrong bin size is used like above.

D:\devs\optimizer>onedim.exe --verbosity-level 99  --objective variable-sized-bin-packing --items items_ea6574d4ab0d40dfa23bc04e5b686dd9.csv --bins bins_ea6574d4ab0d40dfa23bc04e5b686dd9.csv -c solution_ea6574d4ab0d40dfa23bc04e5b686dd9.csv -t 3
===================================
           PackingSolver
===================================

Problem type
------------
onedimensional

Instance
--------
Objective:                VariableSizedBinPacking
Number of item types:     4
Number of items:          9
Number of bin types:      2
Number of bins:           8

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0        3000         inf        3000           3           0
           1        7000         inf        7000           5           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0         290           0         inf       32767         290           3
           1        1496           0         inf       32767        1496           2
           2        2751           0         inf       32767        2751           2
           3        3351           0         inf       32767        3351           2

Algorithm
---------
Column generation

        Time          Cost  # bins  Full waste (%)                         Comment
        ----          ----  ------  --------------                         -------
       0.057         23000       5            0.00                        vbpp2bpp
       0.065         13000       4            0.00                   discrepancy 0

Final statistics
----------------
Cost:              13000
Number of bins:    4
Full waste (%):    0
Time:              0.106359

         BIN        TYPE      COPIES      LENGTH      WEIGHT     # ITEMS
         ---        ----      ------      ------      ------     -------
           0           1           1        6992           0           5
           1           0           1        2751           0           1
           2           0           1        2997           0           2
           3       16705           1        3351           0           1

D:\devs\optimizer>copy solution_ea6574d4ab0d40dfa23bc04e5b686dd9.csv CON
TYPE,ID,COPIES,BIN,X,LX
BIN,1,1,0,0,7000
ITEM,0,1,0,0,290
ITEM,0,1,0,295,290
ITEM,0,1,0,590,290
ITEM,3,1,0,885,3351
ITEM,2,1,0,4241,2751
BIN,0,1,1,0,3000
ITEM,2,1,1,0,2751
BIN,0,1,2,0,3000
ITEM,1,1,2,0,1496
ITEM,1,1,2,1501,1496
BIN,16705,1,3,0,22591874077707
ITEM,3,1,3,0,3351
        1 file(s) copied.

correct run output:

===================================
           PackingSolver
===================================

Problem type
------------
onedimensional

Instance
--------
Objective:                VariableSizedBinPacking
Number of item types:     4
Number of items:          9
Number of bin types:      2
Number of bins:           8

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0        3000         inf        3000           3           0
           1        7000         inf        7000           5           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0         290           0         inf       32767         290           3
           1        1496           0         inf       32767        1496           2
           2        2751           0         inf       32767        2751           2
           3        3351           0         inf       32767        3351           2

Algorithm
---------
Column generation

        Time          Cost  # bins  Full waste (%)                         Comment
        ----          ----  ------  --------------                         -------
       0.192         23000       5            0.00                        vbpp2bpp
       0.238         20000       4            0.00                   discrepancy 0
       0.272         17000       3            0.00                   discrepancy 1

Final statistics
----------------
Cost:              17000
Number of bins:    3
Full waste (%):    0
Time:              0.391031

         BIN        TYPE      COPIES      LENGTH      WEIGHT     # ITEMS
         ---        ----      ------      ------      ------     -------
           0           1           1        6992           0           5
           1           0           1        2997           0           2
           2           1           1        6107           0           2

BTW with --vbpp-algorithm sequential-value-correction option the problem doesn't seem to appear.

[
bins_ea6574d4ab0d40dfa23bc04e5b686dd9.csv
items_ea6574d4ab0d40dfa23bc04e5b686dd9.csv
solution_ea6574d4ab0d40dfa23bc04e5b686dd9.csv
](url)
@lafar6502
Copy link
Author

t1.zip
zipped program and test files

fontanf added a commit that referenced this issue Aug 5, 2023
@fontanf
Fix column generation algorithm with multiple bin sizes (#5)
e27c4fd
@fontanf
Copy link
Owner

fontanf commented Aug 5, 2023

Hi,

Thank you for reporting the issue. I pushed a fix in the dev branch. Could you try it and let me know if it fixes the issue for you too?

@lafar6502
Copy link
Author

Hi Florian,
Thanks for looking into this. I re-compiled the code but it appears the problem is still there (as described, happens randomly)
It looks like some data/memory corruption with output like below.
I tried debugging (with Windows/Visual Studio) but my debug build doesnt seem to work same way as 'normal' build, and this suggests there's some data structure corruption during program run.
As you see below, in the debug build we have '-515' bin type added, which wasn't there in tests before.
Unfortunately, i don't trust my debug environment, and my c++ skills are quite outdated so i can't tell what could be going on here. Will try to build and repeat the test on Linux when i have more time.

D:\devs\optimizer>main.exe --verbosity-level 99  --objective variable-sized-bin-packing --items items_ea6574d4ab0d40dfa23bc04e5b686dd9.csv --bins bins_ea6574d4ab0d40dfa23bc04e5b686dd9.csv -c solution_ea6574d4ab0d40dfa23bc04e5b686dd9.csv -t 3
===================================
           PackingSolver
===================================

Problem type
------------
onedimensional

Instance
--------
Objective:                VariableSizedBinPacking
Number of item types:     4
Number of items:          9
Number of bin types:      2
Number of bins:           8

    Bin type      Length    Max wght        Cost      Copies  Copies min
    --------      ------    --------        ----      ------  ----------
           0        3000         inf        3000           3           0
           1        7000         inf        7000           5           0

   Item type      Length      Weight   MaxWgtAft     MaxStck      Profit      Copies
   ---------      ------      ------   ---------     -------      ------      ------
           0         290           0         inf       32767         290           3
           1        1496           0         inf       32767        1496           2
           2        2751           0         inf       32767        2751           2
           3        3351           0         inf       32767        3351           2

Algorithm
---------
Column generation

        Time          Cost  # bins  Full waste (%)                         Comment
        ----          ----  ------  --------------                         -------
       0.046         23000       5            0.00                        vbpp2bpp
       0.066         13000       4            0.00                   discrepancy 0

Final statistics
----------------
Cost:              13000
Number of bins:    4
Full waste (%):    0
Time:              0.155712

         BIN        TYPE      COPIES      LENGTH      WEIGHT     # ITEMS
         ---        ----      ------      ------      ------     -------
           0           1           1        6992           0           5
           1           0           1        2751           0           1
           2           0           1        2997           0           2
           3        -515           1        3351           0           1

D:\devs\optimizer>copy solution_ea6574d4ab0d40dfa23bc04e5b686dd9.csv CON
TYPE,ID,COPIES,BIN,X,LX
BIN,1,1,0,0,7000
ITEM,0,1,0,0,290
ITEM,0,1,0,295,290
ITEM,0,1,0,590,290
ITEM,3,1,0,885,3351
ITEM,2,1,0,4241,2751
BIN,0,1,1,0,3000
ITEM,2,1,1,0,2751
BIN,0,1,2,0,3000
ITEM,1,1,2,0,1496
ITEM,1,1,2,1501,1496
BIN,-515,1,3,0,0
ITEM,3,1,3,0,3351
        1 file(s) copied.

@fontanf
Copy link
Owner

fontanf commented Aug 7, 2023

That's strange. Are you sure you compiled the dev branch?

@lafar6502
Copy link
Author

No, i'm stupid, i looked at the history too quick and thought dev has been merged to master already.
Now have compiled dev and yeah, the problem seems to be solved. Every run gives the same result and it's correct.
Thanks again!
In the meantime i verified if the problem occurred also on Linux, and it did :) and now works both for Windows and Linux build.
R

@fontanf
Copy link
Owner

fontanf commented Aug 7, 2023

Great, I close the issue and will merge the dev branch in a few days

@fontanf fontanf closed this as completed Aug 7, 2023
fontanf added a commit that referenced this issue Jul 27, 2024
@fontanf
Fix column generation algorithm with multiple bin sizes (#5)
ff51e02
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@lafar6502 @fontanf