A cutting stock problem

[nerin...@gmail.com]

Hi there,

I'm trying to solve on AMPL the following problem: I have 16 files of dimensions 851 kb, 461 kb, 432 kb, 406 kb, 388 kb, 372 kb, 364 kb, 253 kb, 164 kb, 137 kb, 114 kb, 108 kb, 87 kb, 62 kb, 55 kb and 46 kb. I have to put these file into floppies of dimension 1440 kb, without mutiplying them. So, I implemented on AMPL an algorithm based on the cutting stock problem and I generated binary patters of width 16, such as (1001001100011011)j, where the first component shows if the file of 851 kb is in the j-th floppy and so on.

According to the theory, the ceiling of the optimal solution of the relaxation of my problem (that is has been solved by my algorithm) should be an admissible solution for my initial problem (that is a PLI problem), but it is not. In fact, I obtain as optimal relaxation solution a vector of 15 non-zero components, which correspond to 15 patterns that are not admissible for my initial problem, because some files are in more than one, despite of the constraint that each file should be in only one floppy.

I do not understand why it happens, I controlled my algorithm, but I can not fix this problem.

Any Idea?

Here it is the AMPL files .mod and .run:

#-----------------------------------------------------------------------------------------------------------------------------------file mod

# ----------------------------------------

# RELAXATION OF MY PROBLEM

# ----------------------------------------

param dimension_floppy > 0;         

 

set WIDTHS;                                         # the width is the dimension 

param orders {WIDTHS} > 0;               # of each file.

param nPAT integer >  0;                                  # number of patterns

set PATTERNS := 1..nPAT;                               # set of patterns

param nbr {WIDTHS,PATTERNS};

 

var Cut {PATTERNS};                                  # the vector Cut shows which patterns are useful

minimize Number:                                         # mimize the number of patterns

   sum {j in PATTERNS} Cut[j];   

subj to Fill {i in WIDTHS}:

   sum {j in PATTERNS} nbr[i,j] * Cut[j] = 1;                # no same file in more than one pattern 

                                                                                                               

subj to vin3 {j in PATTERNS}: Cut[j] >= 0;                 # relaxation 

# ----------------------------------------

# DUAL OF THE RELAXATION PROBLEM

# ----------------------------------------

var Cut_u{WIDTHS};

maximize valore_duale: sum {i in WIDTHS} Cut_u[i];

subj to vin1{j in PATTERNS}: sum{i in WIDTHS} nbr[i,j] * Cut_u[i] <= 1;

# ----------------------------------------

# KNAPSACK SUBPROBLEM FOR STOP COLUMN GENERATION

# ----------------------------------------

var Use {WIDTHS} binary;

maximize Reduced_Cost:  

   sum {i in WIDTHS} Cut_u[i] * Use[i];

subj to Width_Limit:  

   sum {i in WIDTHS} i * Use[i] <= dimension_floppy;

#----------------------------------------------------------------------------------------------------------------------------

#-----------------------------------------------------------------------------------------------------------------------------file run

option solver cplex;

option solution_round 6;

model cut1.mod;

data cut1.dat;

problem Cutting_Opt: Cut, Number, Fill, vin3;

 

   option presolve 0;

problem Duale: Cut_u, valore_duale, vin1;

problem Pattern_Gen: Use, Reduced_Cost, Width_Limit;

  

   option presolve 1;

let nPAT := 0;

for {i in WIDTHS} {                                                          # I generate an admissible   

                                                                                       # solution that put each 

   let nPAT := nPAT + 1;                                                   # file in one floppy

   let nbr[i,nPAT] := 1;                                      

   let {i2 in WIDTHS: i2 <> i} nbr[i2,nPAT] := 0;

   };

repeat {

   solve Cutting_Opt;

   solve Duale;

   solve Pattern_Gen;

   if Reduced_Cost > 1.000002 then {

      let nPAT := nPAT + 1;

      let {i in WIDTHS} nbr[i,nPAT] := Use[i];       # column generation

      }

   else break;

   };

display nbr; 

display Cut;

#-------------------------------------------------------------------------------------------------------------------------------------------------------

So, if i run this program, I obtain two (of 15) patterns such these:

(0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0)

(0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0),

that show that the 10-th file is in two floppies, despite of sum {j in PATTERNS} nbr[i,j] * Cut[j] = 1. 

So, why?

Thanks for any possible answer. 

[Robert Fourer]

It is entirely possible that a procedure like this will generate two patterns such as

1: (0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0)
2: (0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0)

When you solve Cutting_Opt, in the optimal solution either Cut[1] will be zero, or Cut[2] will be zero, or Cut[1] and Cut[2] will both be positive but will have fractional values less than one. In any of these cases, the Fill constraints will be satisfied when you solve the Cutting_Opt relaxation.

As a consequence, it is not true that "the ceiling of the optimal solution of the relaxation of my problem (that is has been solved by my algorithm) should be an admissible solution for my initial problem." In the case that Cut[1] and Cut[2] are both positive and fractional, the rounded solution will have sum {j in PATTERNS} nbr[i,j] * Cut[j] = 2 (or greater). Your assertion only holds if the Fill constraints are "... >= 1", which is not appropriate in this situation (though it is reasonable for actual cutting problems).

For this kind of problem where every item has a different size, it may be preferable to use a formulation with binary variables Cut[i,j] that are 1 if and only if file i is placed on disk j. See the attached example, where OBJECTS would be the set of files, weight would be the vector of sizes of the files, and capacity would be the capacity of the disks.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of nerin...@gmail.com
Sent: Thursday, August 31, 2017 9:34 AM
To: AMPL Modeling Language
Subject: [AMPL 14677] A cutting stock problem

I'm trying to solve on AMPL the following problem: I have 16 files of dimensions 851 kb, 461 kb, 432 kb, 406 kb, 388 kb, 372 kb, 364 kb, 253 kb, 164 kb, 137 kb, 114 kb, 108 kb, 87 kb, 62 kb, 55 kb and 46 kb. I have to put these file into floppies of dimension 1440 kb, without mutiplying them. So, I implemented on AMPL an algorithm based on the cutting stock problem and I generated binary patters of width 16, such as (1001001100011011)j, where the first component shows if the file of 851 kb is in the j-th floppy and so on.

According to the theory, the ceiling of the optimal solution of the relaxation of my problem (that is has been solved by my algorithm) should be an admissible solution for my initial problem (that is a PLI problem), but it is not. In fact, I obtain as optimal relaxation solution a vector of 15 non-zero components, which correspond to 15 patterns that are not admissible for my initial problem, because some files are in more than one, despite of the constraint that each file should be in only one floppy.

I do not understand why it happens, I controlled my algorithm, but I can not fix this problem.
Any Idea?

# ----------------------------------------
# RELAXATION OF MY PROBLEM
# ----------------------------------------

param dimension_floppy > 0;

set WIDTHS; # the width is the dimension
param orders {WIDTHS} > 0; # of each file.

param nPAT integer > 0; # number of patterns
set PATTERNS := 1..nPAT; # set of patterns

param nbr {WIDTHS,PATTERNS};

var Cut {PATTERNS}; # the vector Cut shows which patterns are useful

minimize Number: # mimize the number of patterns
sum {j in PATTERNS} Cut[j];

subj to Fill {i in WIDTHS}:
sum {j in PATTERNS} nbr[i,j] * Cut[j] = 1; # no same file in more than one pattern

subj to vin3 {j in PATTERNS}: Cut[j] >= 0; # relaxation

...

[nerin...@gmail.com]

Dear Bob Fourer,

Thank you so much for your assistance. I really appreciate your help in resolving this problem. In fact I solved it in the same way that you have shown to me, but actually my assignment is to solve the relaxation of this little problem by a column generation method. So, once I wrote and solved the IP on ampl, I tried to write a model for the relaxation associated to it is such a way as to use column generation. So, is there no chance to use column generation for this problem? 

Marina.

[Robert Fourer]

If you want to use column generation then you need to use your original formulation, in which the variables correspond to patterns. It will work, but at the end you will have only a solution to the continuous relaxation, and if you have some = constraints then the rounded solution may not be feasible.

One way to get an integer-feasible solution is to solve one more optimization problem at the end, using all of the patterns that were generated in solving the relaxation, but with the corresponding variables required to be integer. This is usually a good solution, though it may not be optimal.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of nerin...@gmail.com