Marc,
I assume you want to use dual values of master LP problem/model, to generate
new "best" column which can be added to the model.
Please search on Internet for "cutting stock problem". It will explain need
of column generation and how to use dual values to generate columns.
I just tried to write simple program (using GLPK 4.18) which uses column
generation technique, to solve cutting stock problem. Please see attached
code. Its not complete (final solution is not integer). I have NOT tested
it much, so there might be many bugs. Hope it gives you some idea of column
generation. Later I might write improved versions.
Thanks
On 6/27/07, Marc Goetschalckx <[EMAIL PROTECTED]> wrote:
I solving a problem with column generation. I have solved the root
problem and now need to add columns to this existing problem and using
the current basis. Is there an example that illustrates the mechanics
of column generation? Thanks
Marc Goetschalckx
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
--
Vijay Patil
/*
# 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<stdio.h>
#include<stdlib.h>
#include<assert.h>
#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;
}
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
