![]() | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
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 xbcutex.c /******************************************************** BCL Example Problems ==================== file xbcutex.c `````````````` Simplified version of xbexpl1.c showing how to define cuts with BCL. (c) 2008 Fair Isaac Corporation author: S.Heipcke, 2000, rev. Mar. 2011 ********************************************************/ #include <stdio.h> #include "xprb.h" #include "xprs.h" #define NJ 4 /* Number of jobs */ #define NT 10 /* Time limit */ /**** DATA ****/ double D[] = {3,4,2,2}; /* Durations of jobs */ XPRBvar start[NJ]; /* Start times of jobs */ XPRBvar delta[NJ][NT]; /* Binaries for start times */ XPRBvar z; /* Maximum completion time (makespan) */ /***********************************************************************/ int XPRS_CC usrcme(XPRSprob oprob, void* vd) { XPRBcut ca[2]; int num; int i=0; XPRBprob bprob; /* In terms of an example, we add a few additional constraints (without any relation to the original problem) at the second node of the MIP search tree. These constraints/cuts are applied at this node and all its child nodes. */ bprob = (XPRBprob)vd; XPRBbegincb(bprob, oprob); XPRSgetintattrib(oprob, XPRS_NODES, &num); if(num == 2) { /* ca0: s_1+2 <= s_0 */ ca[0] = XPRBnewcutprec(bprob, start[1], 2, start[0], 2); ca[1] = XPRBnewcut(bprob, XPRB_L, 2); /* ca1: 4*s_2 - 5.3*s_3 <= -17 */ XPRBaddcutterm(ca[1], start[2], 4); XPRBaddcutterm(ca[1], start[3], -5.3); XPRBaddcutterm(ca[1], NULL, -17); printf("Adding constraints:\n"); for(i=0;i<2;i++) XPRBprintcut(ca[i]); if(XPRBaddcuts(bprob, ca, 2)) printf("Problem with adding cuts.\n"); } XPRBendcb(bprob); return 0; } /*************************************************************************/ void cmodel1(XPRBprob prob) { XPRBctr ctr; int j,t; /****VARIABLES****/ /* Create start time variables */ for(j=0;j<NJ;j++) start[j] = XPRBnewvar(prob, XPRB_PL, "start", 0, NT); /* Declare the makespan variable */ z = XPRBnewvar(prob, XPRB_PL, "z", 0, NT); for(j=0;j<NJ;j++) /* Declare binaries for each job */ for(t=0;t<(NT-D[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, "C1", start[j], D[j], z); /* Precedence relation between jobs */ XPRBnewprec(prob, "C2", start[0], D[0], start[2]); for(j=0;j<NJ;j++) /* Linking start times and binaries */ { ctr = XPRBnewctr(prob, XPRBnewname("C3_%d",j+1), XPRB_E); for(t=0;t<(NT-D[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("C4_%d",j+1), XPRB_E); for(t=0;t<(NT-D[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-D[j]+1); /* Upper bounds on start time variables */ } /*************************************************************************/ void csolve(XPRBprob bprob) { int statmip; int j; int t; XPRSprob oprob; oprob = XPRBgetXPRSprob(bprob); XPRSsetintcontrol(oprob, XPRS_HEUREMPHASIS, 0); XPRSsetintcontrol(oprob, XPRS_CUTSTRATEGY, 0); /* Switch heuristics and cut generation off: otherwise this problem is solved in the first node of the MIP search tree */ XPRBsetsense(bprob, XPRB_MINIM); XPRBsetcutmode(bprob, 1); /* Switch presolve off, enable cut manager */ XPRSsetcbcutmgr(oprob, usrcme, bprob); XPRBmipoptimize(bprob, ""); /* Solve the problem as MIP */ statmip = XPRBgetmipstat(bprob); /* 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(bprob)); for(j=0;j<NJ;j++) { /* Print the solution for all start times */ printf("%s: %g\n", XPRBgetvarname(start[j]), XPRBgetsol(start[j])); for(t=0;t<NT-D[j]+1;t++) printf("%s: %g, ", XPRBgetvarname(delta[j][t]), XPRBgetsol(delta[j][t])); printf("\n"); } } } /*************************************************************************/ int main(int argc, char **argv) { XPRBprob prob; prob=XPRBnewprob("Jobs"); /* Initialization */ cmodel1(prob); /* Basic problem definition */ csolve(prob); /* Solve and print solution */ return 0; }
| |||||||||||||||||||||||||
© Copyright 2023 Fair Isaac Corporation. |