/* # Program: Simple cutting stock problem to demonstrate column generation technique. # Version: 0.1 # Problem Definition: Minimize total number of patterns, required to statisfy demand for strips of different sizes. # Dependancy: Using GLPK 4.18 API. # Date: June 2007 # Author: Vijay C Patil. */ #include #include #include #include"glpk.h" #define STR_LEN 64 #define STRIP_COUNT 5 #define PENALTY 1000 /* Strip */ typedef struct Strip { double size; /* Strip width */ int amount; /* Demand for the strip of size = size. */ int row_no; /* row number in GLPK model */ double row_dual; /* Dual value used in sub-problem. */ char row_name[STR_LEN]; /* Variable name. */ char art_var_name[STR_LEN]; /* Artificial variable name. */ }Strip; typedef struct Pattern { char pattern_name[STR_LEN]; /* strip_count[i] = Number of strips in the pattern of size strips[i]. Solution of sub-problem is stored in this array. */ int strip_count[STRIP_COUNT]; int col_no; /* Column number in GLPK model */ int solution; /* Optimal number of this pattern. */ }Pattern; double get_roll_width(void) { double roll_width; /* Total roll width. */ printf("Enter total width of a roll = "); scanf("%lf", &roll_width); printf("Roll Width = %5.2f\n", roll_width); return roll_width; } void get_demand_data(Strip * strips, double roll_width) { int i = 0; printf("Enter width size and demand.\n"); for(i = 0; i < STRIP_COUNT; i++) { scanf("%lf %d", &(strips[i].size), &(strips[i].amount)); sprintf(strips[i].row_name, "DemandConstraintStrip%d", i+1); sprintf(strips[i].art_var_name, "ArtVarStrip%d", i+1); assert(strips[i].size <= roll_width); assert(strips[i].size > 0); } } Pattern * generate_pattern(Strip * strips, double roll_width); /* Program Entry Point */ int main() { glp_prob * lp; int i = 0, row_count = 0, col_count = 0; int iteration = 1; Strip strips[STRIP_COUNT]; double roll_width; /* Total roll width. */ double duals[STRIP_COUNT]; char model_filename[STR_LEN]; roll_width = get_roll_width(); get_demand_data(strips, roll_width); /* Create cutting stock master problem. */ lp = glp_create_prob(); glp_set_prob_name(lp, "GlpkCuttingStock"); /* Minimize total number of roles used. */ glp_set_obj_dir(lp, GLP_MIN); /* Add rows. */ glp_add_rows(lp, STRIP_COUNT); for(i = 0; i < STRIP_COUNT; i++) { glp_set_row_bnds(lp, i+1, GLP_LO, strips[i].amount, 0); glp_set_row_name(lp, i+1, strips[i].row_name); strips[i].row_no = i+1; } /* Since we do not have any patterns/variables, add artificial variables in each row. Put high objective function value. */ glp_add_cols(lp, STRIP_COUNT); for(i = 0; i < STRIP_COUNT; i++) { int ind[2]; double val[2]; glp_set_col_bnds(lp, i+1, GLP_LO, 0, 0); glp_set_col_name(lp, i+1, strips[i].art_var_name); glp_set_obj_coef(lp, i+1, PENALTY); ind[1] = strips[i].row_no; val[1] = 1.0; glp_set_mat_col(lp, i+1, 1, ind, val); } /* Column Generation Loop */ while(1) { int ind[STRIP_COUNT]; double val[STRIP_COUNT]; Pattern * new_pattern = NULL; int j = 0; int nz = 0; /* Solve master problem and obtain dual values. */ sprintf(model_filename, "model.lp.%d", iteration); lpx_write_cpxlp(lp, model_filename); glp_simplex(lp, NULL); printf("Obj function value = %5.2f.\n", glp_get_obj_val(lp)); /* Print solution. */ col_count = glp_get_num_cols(lp); //for(i = 0; i < col_count; i++) { // printf("%7.4f\n", glp_get_col_prim(lp, i+1)); //} /* Reset dual values. */ row_count = glp_get_num_rows(lp); for(i = 0; i < row_count; i++) { strips[i].row_dual = glp_get_row_dual(lp, i+1); } /* Generate a new column. */ new_pattern = generate_pattern(strips, roll_width, iteration); nz = 0; for(j = 1, i = 0; i < STRIP_COUNT; i++) { if(new_pattern->strip_count[i] != 0) { ind[j] = strips[i].row_no; val[j] = new_pattern->strip_count[i]; nz++; } } if(nz == 0) break; /* Add new pattern to the model. */ glp_add_cols(lp, 1); col_count = glp_get_num_cols(lp); glp_set_col_bnds(lp, col_count, GLP_LO, 0, 0); glp_set_col_name(lp, col_count, new_pattern->pattern_name); glp_set_obj_coef(lp, col_count, 1.0); glp_set_mat_col(lp, col_count, nz, ind, val); iteration++; if(iteration >= 200) break; } return 0; } Pattern * generate_pattern(Strip * strips, double roll_width, int iter_no) { glp_prob * lp; Pattern * new_pattern = NULL; static int pattern_count = 1; int i = 0; char filename[STR_LEN]; /* Create subproblem problem to generate best pattern. Minimize : (1 - sum of dual values); Maximize : Sum of dual values. */ lp = glp_create_prob(); glp_set_obj_dir(lp, GLP_MAX); glp_set_prob_name(lp, "Subproblem"); /* Add row. */ glp_add_rows(lp, 1); glp_set_row_bnds(lp, 1, GLP_UP, 0, roll_width); glp_set_row_name(lp, 1, "WidthConstraint"); /* Add columns. Variable Yi = number of strips of size strips[i].size, in the pattern to be generated. These optimal values of the variables define the best pattern. */ glp_add_cols(lp, STRIP_COUNT); for(i = 0; i < STRIP_COUNT; i++) { int ind[2]; double val[2]; glp_set_col_bnds(lp, i+1, GLP_LO, 0.0, 0.0); glp_set_obj_coef(lp, i+1, strips[i].row_dual); ind[1] = 1; val[1] = strips[i].size; glp_set_mat_col(lp, i+1, 1, ind, val); } /* Solve sub-problem. */ sprintf(filename, "subproblem.lp.%d", iter_no); lpx_write_cpxlp(lp, filename); glp_simplex(lp, NULL); /* New pattern */ new_pattern = (Pattern*)malloc(sizeof(Pattern)); sprintf(new_pattern->pattern_name, "P%d", pattern_count); pattern_count++; printf("Subproblem Obj function value = %5.2f.\n", glp_get_obj_val(lp)); printf("New Pattern : \n"); for(i = 0; i < STRIP_COUNT; i++) { new_pattern->strip_count[i] = lpx_get_col_prim(lp, i+1); printf("size = %5.2f, count = %d\n", strips[i].size, new_pattern->strip_count[i]); } printf("--------------------------------------------\n"); return new_pattern; }