Cutting Stock Problem Bug

[jay31415986]

1225.55  - Master Roll Width
0 - Waste
57 3 - Cutwidth Demand
65 9 - Cutwidth Demand
67 7 - Cutwidth Demand

This should require one master roll
Integer solution for LP SOVLE returns 2

See detail below:

1 cut starting model
pat_1: 57:21
pat_2: 65:18
pat_3: 67:18

suboptimal solution: 1.03175, time: 0
knapsack solving time: 0

pat_4: 57:2 65:17                    
suboptimal solution: 1.01074, time: 0
knapsack solving time: 0

pat_5: 57:18 65:1 67:2                
suboptimal solution: 1.00841, time: 0
knapsack solving time: 0

pat_6: 57:4 65:4 67:11                
suboptimal solution: 1.00278, time: 0
knapsack solving time: 0

pat_7: 57:2 65:14 67:3                
suboptimal solution: 1, time: 0
knapsack solving time: 0

optimal relaxed solution = 1. marginal cost = 1.25011e-013
Solving for integer...
time: 0
optimal solution: 2 rolls, 7 patterns, 2 used, 4 passes
This may not be the most optimal solution
Rolls per used pattern:
pat_6: 1
pat_7: 1

Press Enter to continue
Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2.
 

Relaxed solution                   1 found as B&B basis.
 
Optimal solution with dual simplex at iteration          1
Feasible solution                  3 found at iteration        6,       6 nodes explored (gap 100.0%)
Improved solution                  2 found at iteration       32,      22 nodes explored (gap 50.0%)
 
Final solution                     2 at iteration       34 and      24 nodes (gap 50.0%).

Excellent numeric accuracy ||*|| = 0

 Memo: Largest [etaPFI v1.0] inv(B) had 10 NZ entries, 0.9x largest basis.
      In the total iteration count 34, 5 (14.7%) were minor/bound swaps.
      There were 25 refactorizations, 0 triggered by time and 0 by density.
             ... on average 1.2 major pivots per refactorization.
      The maximum B&B level was 7, 0.5x MIP order with 0 compressions/node.
      The B&B level was 5 at the optimal solution.
      Total solver time was 0.000 seconds.

[Peter Notebaert-2]

lp_solve itself has no cutting stock handling build in. So how do you get to this? What program did you use for that and where did you get it from?

And From the output I see that etaPFI is used. That is not the default. LUSOL is. So you are using a very old lp_solve version or you changed a default also here.

Peter

--- In lp_solve@..., "jay31415986" <jay31415986@...> wrote:

>
> 1225.55  - Master Roll Width
> 0 - Waste
> 57 3 - Cutwidth Demand
> 65 9 - Cutwidth Demand
> 67 7 - Cutwidth Demand
>
> This should require one master roll
> Integer solution for LP SOVLE returns 2
>
> See detail below:
>
> 1 cut starting model
> pat_1: 57:21
> pat_2: 65:18
> pat_3: 67:18
>
> suboptimal solution: 1.03175, time: 0
> knapsack solving time: 0
>
> pat_4: 57:2 65:17                    
> suboptimal solution: 1.01074, time: 0
> knapsack solving time: 0
>
> pat_5: 57:18 65:1 67:2                
> suboptimal solution: 1.00841, time: 0
> knapsack solving time: 0
>
> pat_6: 57:4 65:4 67:11                
> suboptimal solution: 1.00278, time: 0
> knapsack solving time: 0
>
> pat_7: 57:2 65:14 67:3                
> suboptimal solution: 1, time: 0
> knapsack solving time: 0
>
> optimal relaxed solution = 1. marginal cost = 1.25011e-013
> Solving for integer...
> time: 0
> optimal solution: 2 rolls, 7 patterns, 2 used, 4 passes
> This may not be the most optimal solution
> Rolls per used pattern:
> pat_6: 1
> pat_7: 1
>
> Press Enter to continue
> Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2.
>  
>
> Relaxed solution                   1 found as B&B basis.
>  
> Optimal solution with dual simplex at iteration          1
> Feasible solution                  3 found at iteration        6,       6 nodes explored (gap 100.0%)
> Improved solution                  2 found at iteration       32,      22 nodes explored (gap 50.0%)
>  
> Final solution                     2 at iteration       34 and      24 nodes (gap 50.0%).
>
> Excellent numeric accuracy ||*|| = 0
>
>  Memo: Largest [etaPFI v1.0] inv(B) had 10 NZ entries, 0.9x largest basis.
>       In the total iteration count 34, 5 (14.7%) were minor/bound swaps.
>       There were 25 refactorizations, 0 triggered by time and 0 by density.
>              ... on average 1.2 major pivots per refactorization.
>       The maximum B&B level was 7, 0.5x MIP order with 0 compressions/node.
>       The B&B level was 5 at the optimal solution.
>       Total solver time was 0.000 seconds.
>