find a minimum IIS cover
Definition in file miniisc.c.
#include <string.h>
#include <scip/scipdefplugins.h>
#include <lpi/lpi.h>
#include "benders.h"
#include "readargs.h"
Go to the source code of this file.
Data Structures | |
struct | BENDERS_Data |
Macros | |
#define | DEFAULT_SOLVEMASTERAPPROX FALSE |
#define | DEFAULT_MASTERGAPLIMIT 0.1 |
#define | DEFAULT_REOPTIMIZATION TRUE |
#define | DEFAULT_MASTERSTALLNODES 5000L |
#define | SCIP_CALL_PARAM(x) |
Functions | |
static SCIP_RETCODE | fixAltLPVariable (SCIP_LPI *lp, int ind) |
static SCIP_RETCODE | fixAltLPVariables (SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp) |
static SCIP_RETCODE | unfixAltLPVariables (SCIP *masterscip, int nmastervars, SCIP_Bool *S, SCIP_LPI *lp) |
static SCIP_RETCODE | checkAltLPInfeasible (SCIP *masterscip, SCIP_LPI *lp, SCIP_Bool primal, SCIP_Bool *infeasible, SCIP_Bool *error) |
static | BENDERS_CUTORACLE (cutoracle) |
static SCIP_RETCODE | createAltLPColumn (SCIP *origscip, SCIP_LPI *lp, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhscoef, SCIP_Real sign) |
static SCIP_RETCODE | createAltLP (SCIP *origscip, SCIP_LPI *lp) |
static SCIP_RETCODE | solveMinIISC (const char *filename, const char *settingsname, SCIP_Real timelimit, SCIP_Real memlimit, int dispfreq) |
int | main (int argc, char **argv) |
#define DEFAULT_SOLVEMASTERAPPROX FALSE |
#define DEFAULT_MASTERGAPLIMIT 0.1 |
#define DEFAULT_REOPTIMIZATION TRUE |
#define DEFAULT_MASTERSTALLNODES 5000L |
#define SCIP_CALL_PARAM | ( | x | ) |
Definition at line 52 of file miniisc.c.
Referenced by BENDERS_CUTORACLE(), checkAltLPInfeasible(), and solveMinIISC().
|
static |
Fix variable ind to 0
lp | alternative LP |
ind | variable that should be fixed to 0 |
Definition at line 67 of file miniisc.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPlpiChgBounds().
Referenced by BENDERS_CUTORACLE().
|
static |
fix variables in S to 0
masterscip | SCIP pointer |
nmastervars | number of variables in master |
S | indices to fix |
lp | alternative LP |
Definition at line 84 of file miniisc.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPlpiChgBounds().
Referenced by BENDERS_CUTORACLE().
|
static |
unfix variables in S
masterscip | SCIP pointer |
nmastervars | number of variables in master |
S | indices to fix |
lp | alternative LP |
Definition at line 132 of file miniisc.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPlpiChgBounds(), and SCIPlpiInfinity().
Referenced by BENDERS_CUTORACLE().
|
static |
Check whether the given LP is infeasible
If primal is false we assume that the problem is dual feasible, e.g., the problem was only changed by fixing bounds!
This is the workhorse for all methods that have to solve the alternative LP. We try in several ways to recover from possible stability problems.
masterscip | SCIP pointer |
lp | LP |
primal | whether we are using the primal or dual simplex |
infeasible | output: whether the LP is infeasible |
error | output: whether an error occured |
Definition at line 189 of file miniisc.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CALL_PARAM, SCIP_LPERROR, SCIP_LPPAR_FROMSCRATCH, SCIP_LPPAR_PRESOLVING, SCIP_LPPAR_SCALING, SCIP_OKAY, SCIPlpiExistsPrimalRay(), SCIPlpiGetInternalStatus(), SCIPlpiIsOptimal(), SCIPlpiIsPrimalInfeasible(), SCIPlpiIsPrimalUnbounded(), SCIPlpiIsStable(), SCIPlpiSetIntpar(), SCIPlpiSolveDual(), SCIPlpiSolvePrimal(), SCIPwarningMessage(), and TRUE.
Referenced by BENDERS_CUTORACLE().
|
static |
produce Benders cuts from the alternative polyhedron
input:
Definition at line 318 of file miniisc.c.
References assert(), BENDERS_STATUS_ADDEDCUT, BENDERS_STATUS_ERROR, BENDERS_STATUS_SUCCESS, BENDERS_STATUS_UNKNOWN, checkAltLPInfeasible(), FALSE, fixAltLPVariable(), fixAltLPVariables(), NULL, primsol, SCIP_Bool, SCIP_CALL, SCIP_CALL_PARAM, SCIP_LPPAR_FROMSCRATCH, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateConsLogicor(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPisFeasZero(), SCIPlpiGetNCols(), SCIPlpiGetSol(), SCIPlpiSetIntpar(), SCIPprintCons(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetObj(), TRUE, unfixAltLPVariables(), and vars.
|
static |
creates column in alternative polyhedron
origscip | SCIP pointer |
lp | alternative LP |
nvars | number of variables in column |
vars | variables for column |
vals | values for column |
rhscoef | coefficient for first row |
sign | sign (+1,-1) for column |
Definition at line 490 of file miniisc.c.
References assert(), NULL, nvars, obj, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPlpiAddCols(), SCIPlpiInfinity(), SCIPvarGetIndex(), and vars.
Referenced by createAltLP().
|
static |
create alternative polyhedron
origscip | original SCIP instance |
lp | alternative polyhedron |
Definition at line 553 of file miniisc.c.
References assert(), c, createAltLPColumn(), NULL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPgetCapacityKnapsack(), SCIPgetConss(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetNConss(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsSetppc(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsSetppc(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), and SCIPwarningMessage().
Referenced by solveMinIISC().
|
static |
solve minimum IIS cover problem
filename | problem name |
settingsname | name of parameter file (or NULL) |
timelimit | time limit read from arguments |
memlimit | memory limit read from arguments |
dispfreq | display frequency |
Definition at line 662 of file miniisc.c.
References assert(), createAltLP(), DEFAULT_MASTERGAPLIMIT, DEFAULT_MASTERSTALLNODES, DEFAULT_REOPTIMIZATION, DEFAULT_SOLVEMASTERAPPROX, FALSE, getProblemName(), BENDERS_Data::lp, BENDERS_Data::m, NULL, obj, runBenders(), SCIP_Bool, SCIP_CALL, SCIP_CALL_PARAM, SCIP_ERROR, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_LPPAR_FASTMIP, SCIP_LPPAR_FROMSCRATCH, SCIP_LPPAR_PRESOLVING, SCIP_LPPAR_SCALING, SCIP_MAXSTRLEN, SCIP_OBJSEN_MINIMIZE, SCIP_OBJSENSE_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_BINARY, SCIP_VERBLEVEL_NORMAL, SCIPaddBoolParam(), SCIPaddLongintParam(), SCIPaddRealParam(), SCIPaddVar(), SCIPcreate(), SCIPcreateProb(), SCIPcreateVar(), SCIPerrorMessage, SCIPfileExists(), SCIPfree(), SCIPgetMessagehdlr(), SCIPgetNOrigBinVars(), SCIPgetNOrigIntVars(), SCIPgetNOrigVars(), SCIPgetOrigVars(), SCIPincludeDefaultPlugins(), SCIPinfoMessage(), SCIPisInfinity(), SCIPisZero(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiCreate(), SCIPlpiFree(), SCIPlpiGetNCols(), SCIPlpiGetNRows(), SCIPlpiInfinity(), SCIPlpiSetIntpar(), SCIPlpiWriteLP(), SCIPprintVersion(), SCIPreadParams(), SCIPreadProb(), SCIPreleaseVar(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), SCIPwriteParams(), TRUE, and var.
Referenced by main().
int main | ( | int | argc, |
char ** | argv ) |
main function
argc | number of shell parameters |
argv | array with shell parameters |
Definition at line 884 of file miniisc.c.
References assert(), BMScheckEmptyMemory, NULL, readArguments(), SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPfileExists(), SCIPprintError(), and solveMinIISC().