Get a solution with just the quantity needed

[GoogleCodeExporter]

Dear  Vijay,
I'm trying to get as output just the quantity needed by the order 
i.e. using this kind of order:

6000
334 20

I would like to get a pattern list like this:

Pattern count =    1:   334 x  3,
Pattern count =    1:   334 x 17

I'm not used to linear problem solution programming but looking at the code
and to the help file of the GLPK library I just tried to change the line to
the add_demand_constraints function in the model.cpp file like this:

glp_set_row_bnds(master_lp, row_index, GLP_FX, rhs, 0.0);

this actually did the job but the solution that I got is something similar to:

Pattern count =    3:   334 x  1,
Pattern count =    1:   334 x 17,

that is not what I'm looking for. 
Could you give me an advice about this? It's possible to get what I'm
looking for?

Thank you very much,
Francesco

Original issue reported on code.google.com by ilpanda@gmail.com on 17 Nov 2009 at 5:11

[GoogleCodeExporter]

Francesco,

Testcase : 
6000
334 20

produces following solution report : 

Best integer obj. func. value = 2
Pattern count =    2:   334 x 17, 

It is true that, solution reports suggestion to cut 2 rolls, that produces 
total 34
(> 20) object of width 334. There is nothing to be concerned about this. We 
should
interpret the above solution as :

+ Optimal (minimum) number of rolls needed = 2.
+ First roll should be cut into 17 objects/parts of width = 334.
+ and Second roll should be cut into just 3 objects/parts of width = 334. The
remaining roll can be kept un-cut, for later use.

In other words, we should not take the solution report literally, but stop the
cutting operations as soon as demand is met.

Changing demand constraints from >= to euality will create problems and will 
make
problem infeasible. We can think of some changes in the integer model, only if 
above
exaplanation is not satisfactory.

Original comment by vijay.pa...@gmail.com on 19 Nov 2009 at 3:07

[GoogleCodeExporter]

Dear  Vijay,
thanks for the explanation.
I want to give you some background:
I'm currently using your code (with just some minor change) to prepare cutting 
lists
for a pipe bending machine. The order passed to your program are usually quite 
big
and with a large number of different sizes.
This makes very difficult to manually check if we are cutting more pieces than 
actual
needed. It's true that we are not throwing away copper (parts not needed will 
be used
for the future orders) but in any case we are wasting time to cut "useless" 
parts.
This bring to me to check if it's possible to force the algorithm to cut just 
the
needed parts.

Thanks,
Francesco 

Original comment by ilpanda@gmail.com on 20 Nov 2009 at 1:48

[GoogleCodeExporter]

Dear Vijay

Patch attached.

consider the data set big-test-data.txt
5950
2949 130
2860 101
2849 101
1710 10
1680 11
1305 11
1230 42
1080 1
480 4
380 30
330 8
129 17
1234 55
665 23
887 12

./cspsol --cgroot --data big-test-data.txt  

produces a solution of:

...
Patterns: Current =  41, New =   0, LP worse than integer incumbent 201.845 >= 
202. Fathom node. 

Branch and bound tree exhausted.

# Total runtime = 12 Secs

 # Solution Report # 

Best integer obj. func. value = 202
Pattern count =   31:  2849 x  2,   129 x  1, 
Pattern count =    1:  1710 x  1,  1680 x  2,   665 x  1,   129 x  1, 
Pattern count =    1:  1234 x  2,  1230 x  2,   887 x  1,   129 x  1, 
Pattern count =    5:  1230 x  4,   887 x  1,   129 x  1, 
Pattern count =    9:  1680 x  1,  1234 x  1,  1230 x  1,   665 x  1,   380 x  
3, 
Pattern count =    3:  2860 x  1,  1305 x  1,   887 x  2, 
Pattern count =    1:  2860 x  1,  1710 x  1,   665 x  2, 
Pattern count =    1:  2860 x  1,  1234 x  1,  1080 x  1,   380 x  2, 
Pattern count =    1:  2949 x  1,  1305 x  2,   380 x  1, 
Pattern count =    6:  2860 x  1,  1710 x  1,  1305 x  1, 
Pattern count =   89:  2949 x  1,  2860 x  1,   129 x  1, 
Pattern count =   39:  2949 x  1,  2849 x  1,   129 x  1, 
Pattern count =    1:  2949 x  1,  1710 x  1,  1234 x  1, 
Pattern count =    1:  2860 x  1,  1710 x  1,  1234 x  1,   129 x  1, 
Pattern count =    2:  1234 x  4,   480 x  2, 
Pattern count =   11:  1234 x  3,  1230 x  1,   665 x  1,   330 x  1, 

This solution exhibits the problem noted in this issue.
Notably that:

demand excess = 3 for   330 x  1,  in Pattern count =   11:  1234 x  3,  1230 x 
 1,   665 x  1,   330 x  1, 
demand excess = 150 for   129 x  1,  in total 7 Pattern counts 

It would seem that the changes in r64, especially
2. Objective function of heuristic (FFD) solution is used as first best integer 
solution & bound,
really improved the quality of the solution.

The issue however remains.
Demand may not be exactly met.
In a production environment this causes problems.

###############################################################

The attached patches provide an initial attempt at solving this issue.
It implements a pattern modification strategy design to minimise the number of 
cuts to match the demand.
ie: scan the solution for each cut width and  when we detect that demand has 
been met then modify the pattern to reflect this.

The strategy sets a requirement that demand must be met exactly.
If this condition is not met then the initial non demand optimised solution is 
output.

A new command line arg --mincuts activates the functionality.

//  uncomment to enable debugging of output objects
#define DEBUG_OUTPUT_OBJECTS

A number of output_xxx classes have been defined.
It might have been possible to refractor some of the existing classes but
I thought it better to uncouple the cut minimisation strategy from the existing 
solution code.

Regards

Jonathan Mitchell

###############################################################

Once more using the above data set:

./cspsol --cgroot --mincuts --data big-test-data.txt  

produces a solution of:

Patterns: Current =  41, New =   0, LP worse than integer incumbent 201.845 >= 
202. Fathom node. 

Branch and bound tree exhausted.

# Total runtime = 12 Secs

demand excess = 3 for   330 x  1,  in Pattern count =   11:  1234 x  3,  1230 x 
 1,   665 x  1,   330 x  1, 
Existing pattern count modified: Pattern count =    8:  1234 x  3,  1230 x  1,  
 665 x  1,   330 x  1, 
New pattern appended: Pattern count =    3:  1234 x  3,  1230 x  1,   665 x  1, 
Patterns count = 17

demand excess = 14 for   129 x  1,  in Pattern count =   31:  2849 x  2,   129 
x  1, 
Existing pattern count modified: Pattern count =   17:  2849 x  2,   129 x  1, 
New pattern appended: Pattern count =   14:  2849 x  2, 
Patterns count = 18

demand already met so excluding cut   129 x  1,  in Pattern count =    1:  1710 
x  1,  1680 x  2,   665 x  1,   129 x  1, 

demand already met so excluding cut   129 x  1,  in Pattern count =    1:  1234 
x  2,  1230 x  2,   887 x  1,   129 x  1, 

demand already met so excluding cut   129 x  1,  in Pattern count =    5:  1230 
x  4,   887 x  1,   129 x  1, 

demand already met so excluding cut   129 x  1,  in Pattern count =   89:  2949 
x  1,  2860 x  1,   129 x  1, 

demand already met so excluding cut   129 x  1,  in Pattern count =   39:  2949 
x  1,  2849 x  1,   129 x  1, 

demand already met so excluding cut   129 x  1,  in Pattern count =    1:  2860 
x  1,  1710 x  1,  1234 x  1,   129 x  1, 

Minimise sanity check passed

Cuts map : 
width: 129 count: 17
width: 330 count: 8
width: 380 count: 30
width: 480 count: 4
width: 665 count: 23
width: 887 count: 12
width: 1080 count: 1
width: 1230 count: 42
width: 1234 count: 55
width: 1305 count: 11
width: 1680 count: 11
width: 1710 count: 10
width: 2849 count: 101
width: 2860 count: 101
width: 2949 count: 130

Demand map : 
width: 129 count: 17
width: 330 count: 8
width: 380 count: 30
width: 480 count: 4
width: 665 count: 23
width: 887 count: 12
width: 1080 count: 1
width: 1230 count: 42
width: 1234 count: 55
width: 1305 count: 11
width: 1680 count: 11
width: 1710 count: 10
width: 2849 count: 101
width: 2860 count: 101
width: 2949 count: 130

Demand has been satisfied exactly.

 # Output Patterns Report # 

Total pattern count = 202
Pattern count =   17:  2849 x  2,   129 x  1, 
Pattern count =    1:  1710 x  1,  1680 x  2,   665 x  1, 
Pattern count =    1:  1234 x  2,  1230 x  2,   887 x  1, 
Pattern count =    5:  1230 x  4,   887 x  1, 
Pattern count =    9:  1680 x  1,  1234 x  1,  1230 x  1,   665 x  1,   380 x  
3, 
Pattern count =    3:  2860 x  1,  1305 x  1,   887 x  2, 
Pattern count =    1:  2860 x  1,  1710 x  1,   665 x  2, 
Pattern count =    1:  2860 x  1,  1234 x  1,  1080 x  1,   380 x  2, 
Pattern count =    1:  2949 x  1,  1305 x  2,   380 x  1, 
Pattern count =    6:  2860 x  1,  1710 x  1,  1305 x  1, 
Pattern count =   89:  2949 x  1,  2860 x  1, 
Pattern count =   39:  2949 x  1,  2849 x  1, 
Pattern count =    1:  2949 x  1,  1710 x  1,  1234 x  1, 
Pattern count =    1:  2860 x  1,  1710 x  1,  1234 x  1, 
Pattern count =    2:  1234 x  4,   480 x  2, 
Pattern count =    8:  1234 x  3,  1230 x  1,   665 x  1,   330 x  1, 
Pattern count =    3:  1234 x  3,  1230 x  1,   665 x  1, 
Pattern count =   14:  2849 x  2, 

Original comment by muggins...@googlemail.com on 22 Apr 2010 at 9:28

[GoogleCodeExporter]

cspsol-mincuts.zip attached.

Fixes several issues:

1. xml output now correctly generated.
2. adds an exact tag to the xml so the caller can determine if the solution is 
exact or not.

Jonathan Mitchell

Original comment by muggins...@googlemail.com on 23 Apr 2010 at 9:32

Attachments:

• cspsol-mincuts.zip

[GoogleCodeExporter]

Jonathan,

Thank you for sharing your ideas and patches, looks promising. This weekend, I 
hope
to get chance to resolve issue of matching demand quantity exactly. I am also 
willing
to share commit access to speed up the progress.

Original comment by vijay.pa...@gmail.com on 26 Apr 2010 at 5:38