/home/coin/SVN-release/OS-2.4.0/Couenne/src/heuristics/cons_rowcuts.cpp

Go to the documentation of this file.
00001 /* $Id: cons_rowcuts.cpp 690 2011-06-18 12:23:00Z stefan $
00002  *
00003  * @file   cons_rowcuts.c
00004  * @brief  constraint handler for rowcuts constraints
00005  *         enables separation of convexification cuts during SCIP solution procedure
00006  * @author Pietro Belotti
00007  * @author Timo Berthold
00008  * @license This file is licensed under the Eclipse Public License (EPL)
00009  * 
00010  * This file is licensed under the Eclipse Public License (EPL)
00011  */
00012 
00020 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
00021 
00022 #include <assert.h>
00023 
00024 #include "CouenneConfig.h"
00025 #ifdef COIN_HAS_SCIP
00026 
00027 #include "cons_rowcuts.h"
00028 #include "scip/cons_linear.h"
00029 #include "scip/scip.h"
00030 
00031 #include "CouenneProblem.hpp"
00032 
00033 /* constraint handler properties */
00034 #define CONSHDLR_NAME          "rowcuts"
00035 #define CONSHDLR_DESC          "adds row cuts generated by Couenne in a Branch-and-Check fashion"
00036 #define CONSHDLR_SEPAPRIORITY         0 
00037 #define CONSHDLR_ENFOPRIORITY  -9999999 
00038 #define CONSHDLR_CHECKPRIORITY -9999999 
00039 #define CONSHDLR_SEPAFREQ            -1 
00040 #define CONSHDLR_PROPFREQ            -1 
00041 #define CONSHDLR_EAGERFREQ          100 
00043 #define CONSHDLR_MAXPREROUNDS         0 
00044 #define CONSHDLR_DELAYSEPA        FALSE 
00045 #define CONSHDLR_DELAYPROP        FALSE 
00046 #define CONSHDLR_DELAYPRESOL      FALSE 
00047 #define CONSHDLR_NEEDSCONS        FALSE 
00049 #define DEFAULT_MAXCUTTINGROUNDS     5 
00051 using namespace Couenne;
00052 
00053 /*
00054  * Data structures
00055  */
00056 
00058 struct SCIP_ConshdlrData
00059 {
00060    CouenneCutGenerator*  cutgenerator;       /* CouenneCutGenerator for linearization cuts */
00061    OsiSolverInterface*   milp;               /* Couenne's MILP relaxation of Couenne's MINLP */
00062    int                   maxcuttingrounds;   /* how many rounds of cuts should be applied at most */
00063    int                   ncuttingrounds;     /* how many rounds of cuts have been applied already */
00064 };
00065 
00066 
00067 /*
00068  * Local methods
00069  */
00070 
00071 /* tries to find violated linearization cuts and adds them to SCIP */
00072 static
00073 SCIP_RETCODE checkRowcuts(
00074    SCIP*                 scip,               
00075    SCIP_CONSHDLR*        conshdlr,           
00076    SCIP_RESULT*          result,             
00077    SCIP_Bool             addcons             
00078    )
00079 {
00080    SCIP_CONSHDLRDATA* conshdlrdata;
00081    CouenneProblem* problem;
00082    OsiCuts cs;
00083    SCIP_Real* sol;
00084    SCIP_VAR** vars;
00085    int nvars;
00086    int i;
00087 
00088    assert(scip != NULL);
00089    assert(conshdlr != NULL);
00090    assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
00091    assert(result != NULL);
00092 
00093    /* get constraint handler data */
00094    conshdlrdata = SCIPconshdlrGetData(conshdlr);
00095    assert(conshdlrdata != NULL);
00096 
00097    /* get Couenne problem data */
00098    problem = conshdlrdata->cutgenerator-> Problem ();
00099 
00100    /* get variable data, create sol */
00101    nvars = SCIPgetNVars(scip);
00102    vars = SCIPgetVars(scip);
00103    sol = new SCIP_Real [nvars];
00104    SCIP_CALL( SCIPgetSolVals(scip, NULL, nvars, vars, sol) );
00105 
00106    /* store solution into MILP data structure */
00107    conshdlrdata -> milp -> setColSolution(sol);
00108 
00109    /* let Couenne generate linearization cuts */
00110    problem -> domain () -> push (problem -> nVars (), sol, NULL, NULL);
00111    conshdlrdata->cutgenerator->genRowCuts(*(conshdlrdata->milp), cs, 0, NULL);
00112    problem -> domain () -> pop  ();
00113 
00114    if( !addcons )
00115    {
00116       *result = (cs.sizeRowCuts() == 0) ? SCIP_FEASIBLE : SCIP_INFEASIBLE;
00117       return SCIP_OKAY;
00118    }
00119    
00120    for( i = 0; i < cs.sizeRowCuts(); i++ ) 
00121    {
00122       CoinPackedVector row;
00123 
00124       SCIP_CONS* cons;
00125       SCIP_VAR** vars;
00126 
00127       char consname[SCIP_MAXSTRLEN];  
00128       SCIP_Real* vals;
00129       int* idxs;
00130 
00131       SCIP_Real lhs;
00132       SCIP_Real rhs;
00133 
00134       int nvals;
00135       int j;
00136 
00137       /* get the row corresponding to the cut */
00138       lhs = cs.rowCut(i).lb();
00139       rhs = cs.rowCut(i).ub();      
00140       row = cs.rowCut(i).row();
00141 
00142       /* get row data */
00143       nvals = row.getNumElements();
00144       idxs = row.getIndices();
00145       vals = row.getElements(); 
00146       
00147       (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "rowcut", i);
00148 
00149       /* create an empty linear constraint */
00150       SCIP_CALL_ABORT( SCIPcreateConsLinear(scip, &cons, consname, 0, NULL, NULL, lhs, rhs, 
00151             TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
00152 
00153       /* get SCIP variable array */
00154       vars = SCIPgetVars(scip);      
00155 
00156       /* add variables to constraint */
00157       for( j = 0; j < nvals; j++ )
00158       {
00159          SCIP_CALL( SCIPaddCoefLinear(scip, cons, vars[idxs[j]], vals[j]) );
00160       }
00161       
00162       /* add constraint to SCIP */
00163       SCIP_CALL( SCIPaddCons(scip, cons) );
00164 #if 0
00165        SCIP_CALL( SCIPprintCons(scip,cons,NULL) );
00166 #endif
00167       SCIP_CALL( SCIPreleaseCons(scip, &cons) );        
00168 
00169       *result = SCIP_CONSADDED;
00170    }
00171    
00172    /* store cuts to MILP data structure */
00173    if (cs.sizeRowCuts ()) {
00174       conshdlrdata -> milp -> applyCuts (cs);
00175    }
00176 
00177    return SCIP_OKAY;
00178 }
00179 
00180 /*
00181  * Callback methods of constraint handler
00182  */
00183 
00185 #define conshdlrCopyRowcuts NULL
00186 
00188 static
00189 SCIP_DECL_CONSFREE(consFreeRowcuts)
00190 {  /*lint --e{715}*/
00191    SCIP_CONSHDLRDATA* conshdlrdata;
00192 
00193    assert(conshdlr != NULL);
00194    assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
00195    assert(scip != NULL);
00196 
00197    /* get constraint handler data */
00198    conshdlrdata = SCIPconshdlrGetData(conshdlr);
00199    assert(conshdlrdata != NULL);
00200    
00201    /* free constraint handler data */
00202    SCIPfreeMemory(scip, &conshdlrdata);
00203    SCIPconshdlrSetData(conshdlr, NULL);
00204 
00205    return SCIP_OKAY;
00206 }
00207 
00209 #define consInitRowcuts NULL
00210 
00212 #define consExitRowcuts NULL
00213 
00215 #define consInitpreRowcuts NULL
00216 
00218 #define consExitpreRowcuts NULL
00219 
00221 #define consInitsolRowcuts NULL
00222 
00224 #define consExitsolRowcuts NULL
00225 
00227 #define consDeleteRowcuts NULL
00228 
00230 #define consTransRowcuts NULL
00231 
00233 #define consInitlpRowcuts NULL
00234 
00236 #define consSepalpRowcuts NULL
00237 
00239 #define consSepasolRowcuts NULL
00240 
00242 static
00243 SCIP_DECL_CONSENFOLP(consEnfolpRowcuts)
00244 {  /*lint --e{715}*/
00245    SCIP_CONSHDLRDATA* conshdlrdata;
00246 
00247    assert(scip != NULL);
00248    assert(conshdlr != NULL);
00249    assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
00250    assert(nconss == 0 && conss == NULL); /* there should be no constraints */
00251    assert(result != NULL);
00252 
00253 
00254    conshdlrdata = SCIPconshdlrGetData(conshdlr);
00255    assert(conshdlrdata != NULL);
00256    if( conshdlrdata->ncuttingrounds < conshdlrdata->maxcuttingrounds )
00257    {
00258       SCIP_CALL( checkRowcuts(scip, conshdlr, result, TRUE) );
00259       conshdlrdata->ncuttingrounds++;
00260    }
00261 
00262    /* we want to accept all solutions, even if we added a constraint that cuts them off */
00263    *result = SCIP_FEASIBLE;
00264 
00265    return SCIP_OKAY;
00266 }
00267 
00269 static
00270 SCIP_DECL_CONSENFOPS(consEnfopsRowcuts)
00271 {  /*lint --e{715}*/
00272    SCIP_CONSHDLRDATA* conshdlrdata;
00273 
00274    assert(scip != NULL);
00275    assert(conshdlr != NULL);
00276    assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
00277    assert(nconss == 0 && conss == NULL); /* there should be no constraints */
00278    assert(result != NULL);
00279 
00280 
00281    conshdlrdata = SCIPconshdlrGetData(conshdlr);
00282    assert(conshdlrdata != NULL);
00283 
00284    if( conshdlrdata->ncuttingrounds < conshdlrdata->maxcuttingrounds )
00285    {
00286       SCIP_CALL( checkRowcuts(scip, conshdlr, result, TRUE) );
00287       conshdlrdata->ncuttingrounds++;
00288    }
00289 
00290    /* we want to accept all solutions, even if we added a constraint that cuts them off */
00291    *result = SCIP_FEASIBLE;
00292 
00293    return SCIP_OKAY;
00294 }
00295 
00297 static
00298 SCIP_DECL_CONSCHECK(consCheckRowcuts)
00299 {  /*lint --e{715}*/
00300    SCIP_CONSHDLRDATA* conshdlrdata;
00301 
00302    assert(scip != NULL);
00303    assert(conshdlr != NULL);
00304    assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
00305    assert(nconss == 0 && conss == NULL); /* there should be no constraints */
00306    assert(result != NULL);
00307 
00308 
00309    conshdlrdata = SCIPconshdlrGetData(conshdlr);
00310    assert(conshdlrdata != NULL);
00311    if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && conshdlrdata->ncuttingrounds < conshdlrdata->maxcuttingrounds )
00312    {
00313       SCIP_CALL( checkRowcuts(scip, conshdlr, result, TRUE) );
00314       conshdlrdata->ncuttingrounds++;
00315    }
00316 
00317    *result = SCIP_FEASIBLE;
00318 
00319    return SCIP_OKAY;
00320 }
00321 
00323 #define consPropRowcuts NULL
00324 
00326 #define consPresolRowcuts NULL
00327 
00329 #define consRespropRowcuts NULL
00330 
00332 static
00333 SCIP_DECL_CONSLOCK(consLockRowcuts)
00334 {  /*lint --e{715}*/
00335    assert(cons == NULL);
00336 
00337    return SCIP_OKAY;
00338 }
00339 
00341 #define consActiveRowcuts NULL
00342 
00344 #define consDeactiveRowcuts NULL
00345 
00347 #define consEnableRowcuts NULL
00348 
00350 #define consDisableRowcuts NULL
00351 
00353 #define consPrintRowcuts NULL
00354 
00356 #define consCopyRowcuts NULL
00357 
00359 #define consParseRowcuts NULL
00360 
00361 /*
00362  * constraint specific interface methods
00363  */
00364 
00366 SCIP_RETCODE SCIPincludeConshdlrRowcuts(
00367    SCIP*                 scip,               
00368    CouenneCutGenerator*  cutgenerator,       
00369    OsiSolverInterface*   milp                
00370    )
00371 {
00372    SCIP_CONSHDLRDATA* conshdlrdata;
00373 
00374    /* create rowcuts constraint handler data */
00375    SCIP_CALL( SCIPallocMemory(scip, &conshdlrdata) );
00376    conshdlrdata->cutgenerator = cutgenerator;
00377    conshdlrdata->milp = milp;
00378    conshdlrdata->ncuttingrounds = 0;
00379 
00380    /* include constraint handler */
00381    SCIP_CALL( SCIPincludeConshdlr(scip, CONSHDLR_NAME, CONSHDLR_DESC,
00382          CONSHDLR_SEPAPRIORITY, CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
00383          CONSHDLR_SEPAFREQ, CONSHDLR_PROPFREQ, CONSHDLR_EAGERFREQ, CONSHDLR_MAXPREROUNDS, 
00384          CONSHDLR_DELAYSEPA, CONSHDLR_DELAYPROP, CONSHDLR_DELAYPRESOL, CONSHDLR_NEEDSCONS,
00385          conshdlrCopyRowcuts,
00386          consFreeRowcuts, consInitRowcuts, consExitRowcuts, 
00387          consInitpreRowcuts, consExitpreRowcuts, consInitsolRowcuts, consExitsolRowcuts,
00388          consDeleteRowcuts, consTransRowcuts, consInitlpRowcuts,
00389          consSepalpRowcuts, consSepasolRowcuts, consEnfolpRowcuts, consEnfopsRowcuts, consCheckRowcuts, 
00390          consPropRowcuts, consPresolRowcuts, consRespropRowcuts, consLockRowcuts,
00391          consActiveRowcuts, consDeactiveRowcuts, 
00392          consEnableRowcuts, consDisableRowcuts,
00393          consPrintRowcuts, consCopyRowcuts, consParseRowcuts,
00394          conshdlrdata) );
00395 
00396    /* add rowcuts constraint handler parameters */
00397    SCIP_CALL( SCIPaddIntParam(scip,
00398          "constraints/"CONSHDLR_NAME"/maxcuttingrounds",
00399          "how many rounds of cuts should be applied at most?",
00400          &conshdlrdata->maxcuttingrounds, FALSE, DEFAULT_MAXCUTTINGROUNDS, -1, INT_MAX, NULL, NULL) );
00401 
00402    return SCIP_OKAY;
00403 }
00404 
00405 #endif

Generated on Thu Sep 22 03:05:58 2011 by  doxygen 1.4.7