| |||||||||||||||||||||||||
| |||||||||||||||||||||||||
UG - Examples from 'BCL Reference Manual' Description The following examples are discussed in detail in the 'BCL User Guide and Reference Manual':
Source Files By clicking on a file name, a preview is opened at the bottom of this page.
Data Files xbexpl1.c
/********************************************************
BCL Example Problems
====================
file xbexpl1.c
``````````````
BCL user guide example.
Definition of variables and constraints,
variable arrays and SOS, followed by file output,
solving and printing of solutions.
(c) 2008-2024 Fair Isaac Corporation
author: S.Heipcke, Jan. 2000, rev. Mar. 2011
********************************************************/
#include <stdio.h>
#include "xprb.h"
/**************************************************************************/
/* Define *one* of the following options to try out different problem */
/* formulations: */
/**************************************************************************/
#define BASIC
#undef ARRAYC
#undef SOS
#undef ARRAY
/**************************************************************************/
#define NJ 4 /* Number of jobs */
#define NT 10 /* Time limit */
/**** DATA ****/
double DUR[] = {3,4,2,2}; /* Durations of jobs */
/*{4,2,3,4};
{5,1,1,6};
{5,5,4,4}; */
#ifdef ARRAY
XPRBarrvar start; /* Start times of jobs */
XPRBarrvar delta[NJ]; /* Sets of binaries for start times */
#else
XPRBvar start[NJ]; /* Start times of jobs */
XPRBvar delta[NJ][NT]; /* Binaries for start times */
#endif
XPRBsos set[NJ]; /* Sets regrouping start times for jobs */
XPRBvar z; /* Maximum completion time (makespan) */
XPRBprob prob; /* BCL problem */
void jobs_model(void); /* Basic model formulation */
void jobs_modela(void); /* Model using arrays of variables for some
constraints */
void jobs_modelb(void); /* Model using SOS */
void jobs_modelc(void); /* Model using arrays of variables for
all variables */
void jobs_solve(void); /* Solving and solution printing */
/*************************************************************************/
void jobs_model(void)
{
XPRBctr ctr;
int j,t;
prob=XPRBnewprob("Jobs"); /* Initialization */
/****VARIABLES****/
/* Create start time variables */
for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT);
z = XPRBnewvar(prob,XPRB_PL,"z",0,NT); /* Declare the makespan variable */
for(j=0;j<NJ;j++) /* Declare binaries for each job */
for(t=0;t<(NT-DUR[j]+1);t++)
delta[j][t] = XPRBnewvar(prob,XPRB_BV,XPRBnewname("delta%d%d",j+1,t+1),0,1);
/****CONSTRAINTS****/
for(j=0;j<NJ;j++) /* Calculate maximal completion time */
XPRBnewprec(prob,"Makespan",start[j],DUR[j],z);
XPRBnewprec(prob,"Prec",start[0],DUR[0],start[2]);
/* Precedence relation between jobs */
for(j=0;j<NJ;j++) /* Linking start times and binaries */
{
ctr = XPRBnewctr(prob,XPRBnewname("Link_%d",j+1),XPRB_E);
for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],t+1);
XPRBaddterm(ctr,start[j],-1);
}
for(j=0;j<NJ;j++) /* One unique start time for each job */
{
ctr = XPRBnewctr(prob,XPRBnewname("One_%d",j+1),XPRB_E);
for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],1);
XPRBaddterm(ctr,NULL,1);
}
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
XPRBaddterm(ctr,z,1);
XPRBsetobj(prob,ctr); /* Set objective function */
/****BOUNDS****/
for(j=0;j<NJ;j++) XPRBsetub(start[j],NT-DUR[j]+1);
/* upper bounds on start time variables */
/****OUTPUT****/
XPRBprintprob(prob); /* Print out the problem definition */
XPRBexportprob(prob,XPRB_MPS,"expl1"); /* Output matrix to MPS file */
}
/*************************************************************************/
void jobs_solve(void)
{
int statmip;
int j;
int t;
#ifndef SOS
for(j=0;j<NJ;j++)
for(t=0;t<NT-DUR[j]+1;t++)
XPRBsetvardir(delta[j][t],XPRB_PR,10*(t+1));
/* Give highest priority to variables for earlier start times */
#else
for(j=0;j<NJ;j++)
XPRBsetsosdir(set[j],XPRB_DN,0);
/* First branch downwards on sets */
#endif
XPRBsetsense(prob,XPRB_MINIM);
XPRBmipoptimize(prob,""); /* Solve the problem as MIP */
statmip = XPRBgetmipstat(prob); /* Get the MIP problem status */
if((statmip == XPRB_MIP_SOLUTION) || (statmip == XPRB_MIP_OPTIMAL))
/* An integer solution has been found */
{
printf("Objective: %g\n",XPRBgetobjval(prob));
for(j=0;j<NJ;j++)
{ /* Print the solution for all start times */
printf("%s: %g\n",XPRBgetvarname(start[j]), XPRBgetsol(start[j]));
#ifdef ARRAY
XPRBprintarrvar(delta[j]);
#else
for(t=0;t<NT-DUR[j]+1;t++)
printf("%s: %g, ", XPRBgetvarname(delta[j][t]), XPRBgetsol(delta[j][t]));
printf("\n");
#endif
}
}
}
/*************************************************************************/
int main(int argc, char **argv)
{
#ifdef BASIC
jobs_model(); /* Basic problem definition */
#endif
#ifdef ARRAYC
jobs_modela(); /* Formulation using arrays for some
constraints */
#endif
#ifdef SOS
jobs_modelb(); /* Formulation using SOS */
#endif
#ifdef ARRAY
jobs_modelc(); /* Formulation using arrays of variables */
#endif
jobs_solve(); /* Solve and print solution */
return 0;
}
/*************************************************************************/
/**** Formulation using arrays in constraint definition ****/
void jobs_modela(void)
{
XPRBctr ctr;
XPRBarrvar v;
int j,t;
prob=XPRBnewprob("Jobs"); /* Initialization */
/****VARIABLES****/
/* Create start time variables */
for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT);
z = XPRBnewvar(prob,XPRB_PL,"z",0,NT); /* Declare the makespan variable */
for(j=0;j<NJ;j++) /* Declare binaries for each job */
for(t=0;t<(NT-DUR[j]+1);t++)
delta[j][t] = XPRBnewvar(prob,XPRB_BV,XPRBnewname("delta%d%d",j+1,t+1),0,1);
/****CONSTRAINTS****/
for(j=0;j<NJ;j++) /* Calculate maximal completion time */
XPRBnewprec(prob,"Makespan",start[j],DUR[j],z);
XPRBnewprec(prob,"Prec",start[0],DUR[0],start[2]);
/* Precedence relation between jobs */
for(j=0;j<NJ;j++)
{
double ind[NT];
v = XPRBstartarrvar(prob,NT-(int)(DUR[j])+2,"v1"); /* Define an array of size
NT-DUR[j]+2 */
for(t=0;t<(NT-(int)(DUR[j])+1);t++)
{
XPRBapparrvarel(v,delta[j][t]); /* Add a binary variable to the array */
ind[t]=t+1; /* Add a coefficient */
}
XPRBapparrvarel(v,start[j]); /* Add a continuous var. to the array */
XPRBendarrvar(v); /* Terminate definition of the array */
ind[NT-(int)DUR[j]+1]=-1; /* Add another coefficient */
XPRBnewarrsum(prob,XPRBnewname("Link_%d",j+1),v,ind,XPRB_E,0);
/* Establish sum constraint using array v */
XPRBdelarrvar(v); /* Free the memory allocated to the array */
} /* ... and the table of coefficients */
for(j=0;j<NJ;j++) /* One unique start time for each job */
{
ctr = XPRBnewctr(prob,XPRBnewname("One_%d",j+1),XPRB_E);
for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],1);
XPRBaddterm(ctr,NULL,1);
}
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
XPRBaddterm(ctr,z,1);
XPRBsetobj(prob,ctr); /* Select objective function */
/****BOUNDS****/
for(j=0;j<NJ;j++) XPRBsetub(start[j],NT-DUR[j]+1);
/* Upper bounds on start time variables */
/****OUTPUT****/
XPRBprintprob(prob); /* Print out the problem definition */
XPRBexportprob(prob,XPRB_MPS,"expl1"); /* Output matrix to MPS file */
}
/*************************************************************************/
/**** SOS-formulation ****/
void jobs_modelb(void)
{
XPRBctr ctr;
int j,t;
prob=XPRBnewprob("Jobs"); /* Initialization */
/****VARIABLES****/
/* Create start time variables */
for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob,XPRB_PL,"start",0,NT);
z = XPRBnewvar(prob,XPRB_PL,"z",0,NT); /* Declare the makespan variable */
for(j=0;j<NJ;j++) /* Declare binaries for each job */
for(t=0;t<(NT-DUR[j]+1);t++)
delta[j][t] = XPRBnewvar(prob,XPRB_PL,XPRBnewname("delta%d%d",j+1,t+1),0,1);
/****CONSTRAINTS****/
for(j=0;j<NJ;j++) /* Calculate maximal completion time */
XPRBnewprec(prob,"Makespan",start[j],DUR[j],z);
XPRBnewprec(prob,"Prec",start[0],DUR[0],start[2]);
/* Precedence relation between jobs */
for(j=0;j<NJ;j++) /* Linking start times and binaries */
{
ctr = XPRBnewctr(prob,XPRBnewname("Link_%d",j+1),XPRB_E);
for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],t+1);
XPRBaddterm(ctr,start[j],-1);
}
for(j=0;j<NJ;j++) /* One unique start time for each job */
{
ctr = XPRBnewctr(prob,XPRBnewname("One_%d",j+1),XPRB_E);
for(t=0;t<(NT-DUR[j]+1);t++) XPRBaddterm(ctr,delta[j][t],1);
XPRBaddterm(ctr,NULL,1);
}
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
XPRBaddterm(ctr,z,1);
XPRBsetobj(prob,ctr); /* Select objective function */
/****BOUNDS****/
for(j=0;j<NJ;j++) XPRBsetub(start[j],NT-DUR[j]+1);
/* Upper bounds on start time variables */
/****SETS****/
for(j=0;j<NJ;j++)
{
set[j] = XPRBnewsos(prob,"sosj",XPRB_S1);
for(t=0;t<(NT-DUR[j]+1);t++)
XPRBaddsosel(set[j],delta[j][t],t+1);
}
/****OUTPUT****/
XPRBprintprob(prob); /* Print out the problem definition */
XPRBexportprob(prob,XPRB_MPS,"expl1"); /* Output matrix to MPS file */
}
/*************************************************************************/
#ifdef ARRAY
void jobs_modelc(void)
{
XPRBctr ctr;
int j;
prob=XPRBnewprob("Jobs"); /* Initialization */
/****VARIABLES****/
/* Create a table of start time variables */
start = XPRBnewarrvar(prob,NJ,XPRB_PL,"start",0,NT);
z = XPRBnewvar(prob,XPRB_PL,"z",0,NT); /* Declare the makespan variable */
for(j=0;j<NJ;j++) /* Declare a set of binaries for each job */
delta[j] = XPRBnewarrvar(prob,(NT-(int)(DUR[j])+1),XPRB_BV,XPRBnewname("delta%d",j+1),0,1);
/****CONSTRAINTS****/
for(j=0;j<NJ;j++) /* Calculate maximal completion time */
XPRBnewprec(prob,"Makespan",start[j],DUR[j],z);
XPRBnewprec(prob,"Prec",start[0],DUR[0],start[2]);
/* Precedence relation between jobs */
/* Alternative constraint formulation: (linking start times and binaries) */
/*
for(j=0;j<NJ;j++)
{
int t;
double c[NT];
ctr = XPRBnewctr(prob,XPRBnewname("Link_%d",j+1),XPRB_E);
for(t=0;t<(NT-DUR[j]+1);t++) c[t]=t+1;
XPRBaddarrterm(ctr,delta[j],c);
XPRBaddterm(ctr,start[j],-1);
}
*/
for(j=0;j<NJ;j++) /* Linking start times and binaries */
{
ctr = XPRBnewsumc(prob,XPRBnewname("Link%d",j+1),delta[j],1,XPRB_E,0);
XPRBaddterm(ctr,start[j],-1);
}
for(j=0;j<NJ;j++) /* One unique start time for each job */
XPRBnewsum(prob,"One",delta[j],XPRB_E,1);
/****OBJECTIVE****/
ctr = XPRBnewctr(prob,"OBJ",XPRB_N);
XPRBaddterm(ctr,z,1);
XPRBsetobj(prob,ctr); /* Select objective function */
/****BOUNDS****/
for(j=0;j<NJ;j++) XPRBsetub(start[j],NT-DUR[j]+1);
/* Upper bounds on start time variables */
/****SETS****/
/* Alternative SOS formulation: define delta as continuous variables! */
/*
for(j=0;j<NJ;j++)
XPRBnewsosrc(prob,"sosj",XPRB_S1,delta[j],
XPRBgetbyname(prob,XPRBnewname("Link_%d",j+1),XPRB_PL)); */
/* Create an SOS-1 for each job with a reference row from ctr.s Link */
/****OUTPUT****/
XPRBprintprob(prob); /* Print out the problem definition */
XPRBexportprob(prob,XPRB_MPS,"expl1"); /* Output matrix to MPS file */
}
#endif
| |||||||||||||||||||||||||
| © Copyright 2024 Fair Isaac Corporation. |
