Bin Packing Problem (dcmpe06)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: dcmpe06 */
/* TITLE: Bin Packing Problem (dcmpe06) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: OPTMODEL */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 6 from the Decomposition Algorithm */
/* chapter of Mathematical Programming. */
/* */
/***************************************************************/
/* game, size (in GBs) */
data dvr;
input opponent $ size;
datalines;
Clemson 1.36
Clemson2 1.97
Duke 2.76
Duke2 2.52
FSU 2.56
FSU2 2.34
GT 1.49
GT2 1.12
IN 1.45
KY 1.42
Loyola 1.42
MD 1.33
MD2 2.71
Miami 1.22
NCSU 2.52
NCSU2 2.54
UConn 1.25
VA 2.33
VA2 2.48
VT 1.41
Vermont 1.28
WM 1.25
WM2 1.23
Wake 1.61
;
proc optmodel;
/* read the product and size data */
set <str> PRODUCTS;
num size {PRODUCTS};
read data dvr into PRODUCTS=[opponent] size;
/* 4.38 GBs per DVD */
num binsize = 4.38;
/* the number of products is a trivial upper bound on the
maximum number of bins needed */
num upperbound init card(PRODUCTS);
set BINS = 1..upperbound;
/* Assign[p,b] = 1, if product p is assigned to bin b */
var Assign {PRODUCTS, BINS} binary;
/* UseBin[b] = 1, if bin b is used */
var UseBin {BINS} binary;
/* minimize number of bins used */
min Objective = sum {b in BINS} UseBin[b];
/* assign each product to exactly one bin */
con Assignment {p in PRODUCTS}:
sum {b in BINS} Assign[p,b] = 1;
/* capacity constraint on each bin (and definition of UseBin) */
con Capacity {b in BINS}:
sum {p in PRODUCTS} size[p] * Assign[p,b] <= binsize * UseBin[b];
/* decompose by bin (subproblem is a knapsack problem) */
for {b in BINS} Capacity[b].block = b;
/* solve using decomp (aggregate formulation) */
solve with milp / decomp;
/* create a map from arbitrary bin number to sequential bin number */
num binId init 1;
num binMap {BINS};
for {b in BINS: UseBin[b].sol > 0.5} do;
binMap[b] = binId;
binId = binId + 1;
end;
/* create map of product to bin from solution */
num bin {PRODUCTS};
for {p in PRODUCTS} do;
for {b in BINS: Assign[p,b].sol > 0.5} do;
bin[p] = binMap[b];
leave;
end;
end;
/* create solution data */
create data dvd from [product] bin size;
quit;
proc sort data=dvd;
by bin;
run;
proc print data=dvd noobs label;
sum size; by bin;
run;