Scippy

SCIP

Solving Constraint Integer Programs

miniisc.c File Reference

Detailed Description

find a minimum IIS cover

Author
Marc Pfetsch

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)
 

Macro Definition Documentation

◆ DEFAULT_SOLVEMASTERAPPROX

#define DEFAULT_SOLVEMASTERAPPROX   FALSE

Solve master problem approximately?

Definition at line 29 of file miniisc.c.

Referenced by solveMinIISC().

◆ DEFAULT_MASTERGAPLIMIT

#define DEFAULT_MASTERGAPLIMIT   0.1

gap bound for approximately solving the master problem

Definition at line 30 of file miniisc.c.

Referenced by solveMinIISC().

◆ DEFAULT_REOPTIMIZATION

#define DEFAULT_REOPTIMIZATION   TRUE

Use reoptimization to solve master problem?

Definition at line 31 of file miniisc.c.

Referenced by solveMinIISC().

◆ DEFAULT_MASTERSTALLNODES

#define DEFAULT_MASTERSTALLNODES   5000L

stall nodes for the master problem

Definition at line 32 of file miniisc.c.

Referenced by solveMinIISC().

◆ SCIP_CALL_PARAM

#define SCIP_CALL_PARAM (   x)
Value:
/*lint -e527 */ do \
{ \
SCIP_RETCODE _restat_; \
if ( (_restat_ = (x)) != SCIP_OKAY && (_restat_ != SCIP_PARAMETERUNKNOWN) ) \
{ \
SCIPerrorMessage("[%s:%d] Error <%d> in function call\n", __FILE__, __LINE__, _restat_); \
SCIPABORT(); \
return _restat_; \
} \
} \
while ( FALSE )
#define FALSE
Definition: def.h:73
SCIP_VAR ** x
Definition: circlepacking.c:54

Definition at line 43 of file miniisc.c.

Referenced by BENDERS_CUTORACLE(), checkAltLPInfeasible(), and solveMinIISC().

Function Documentation

◆ fixAltLPVariable()

static SCIP_RETCODE fixAltLPVariable ( SCIP_LPI lp,
int  ind 
)
static

Fix variable ind to 0

Parameters
lpalternative LP
indvariable that should be fixed to 0

Definition at line 58 of file miniisc.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, and SCIPlpiChgBounds().

Referenced by BENDERS_CUTORACLE().

◆ fixAltLPVariables()

static SCIP_RETCODE fixAltLPVariables ( SCIP masterscip,
int  nmastervars,
SCIP_Bool S,
SCIP_LPI lp 
)
static

fix variables in S to 0

Parameters
masterscipSCIP pointer
nmastervarsnumber of variables in master
Sindices to fix
lpalternative LP

Definition at line 75 of file miniisc.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, and SCIPlpiChgBounds().

Referenced by BENDERS_CUTORACLE().

◆ unfixAltLPVariables()

static SCIP_RETCODE unfixAltLPVariables ( SCIP masterscip,
int  nmastervars,
SCIP_Bool S,
SCIP_LPI lp 
)
static

unfix variables in S

Parameters
masterscipSCIP pointer
nmastervarsnumber of variables in master
Sindices to fix
lpalternative LP

Definition at line 123 of file miniisc.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPlpiChgBounds(), and SCIPlpiInfinity().

Referenced by BENDERS_CUTORACLE().

◆ checkAltLPInfeasible()

static SCIP_RETCODE checkAltLPInfeasible ( SCIP masterscip,
SCIP_LPI lp,
SCIP_Bool  primal,
SCIP_Bool infeasible,
SCIP_Bool error 
)
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.

Precondition
It is assumed that all parameters for the alternative LP are set.
Parameters
masterscipSCIP pointer
lpLP
primalwhether we are using the primal or dual simplex
infeasibleoutput: whether the LP is infeasible
erroroutput: whether an error occured

Definition at line 180 of file miniisc.c.

References FALSE, NULL, 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().

◆ BENDERS_CUTORACLE()

static BENDERS_CUTORACLE ( cutoracle  )
static

produce Benders cuts from the alternative polyhedron

input:

  • masterscip: SCIP pointer of Benders master problem
  • nmastervars: number of variables in master problem
  • mastervars: variables in master problem
  • mastersolution: solution of Benders master problem
  • data: user data for oracle
  • timelimit: time limit for subproblem
  • ntotalcuts: total number of cuts output:
  • ncuts: number of cuts added
  • status: status

Definition at line 309 of file miniisc.c.

References BENDERS_STATUS_ADDEDCUT, BENDERS_STATUS_ERROR, BENDERS_STATUS_SUCESS, BENDERS_STATUS_UNKNOWN, checkAltLPInfeasible(), FALSE, fixAltLPVariable(), fixAltLPVariables(), BENDERS_Data::lp, NULL, 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, and unfixAltLPVariables().

◆ createAltLPColumn()

static SCIP_RETCODE createAltLPColumn ( SCIP origscip,
SCIP_LPI lp,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
SCIP_Real  rhscoef,
SCIP_Real  sign 
)
static

creates column in alternative polyhedron

Parameters
origscipSCIP pointer
lpalternative LP
nvarsnumber of variables in column
varsvariables for column
valsvalues for column
rhscoefcoefficient for first row
signsign (+1,-1) for column

Definition at line 481 of file miniisc.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPlpiAddCols(), SCIPlpiInfinity(), SCIPvarGetIndex(), and sign().

Referenced by createAltLP().

◆ createAltLP()

◆ solveMinIISC()

static SCIP_RETCODE solveMinIISC ( const char *  filename,
const char *  settingsname,
SCIP_Real  timelimit,
SCIP_Real  memlimit,
int  dispfreq 
)
static

solve minimum IIS cover problem

Parameters
filenameproblem name
settingsnamename of parameter file (or NULL)
timelimittime limit read from arguments
memlimitmemory limit read from arguments
dispfreqdisplay frequency

Definition at line 653 of file miniisc.c.

References createAltLP(), DEFAULT_MASTERGAPLIMIT, DEFAULT_MASTERSTALLNODES, DEFAULT_REOPTIMIZATION, DEFAULT_SOLVEMASTERAPPROX, FALSE, getProblemName(), BENDERS_Data::lp, BENDERS_Data::m, NULL, 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(), and TRUE.

Referenced by main().

◆ main()

int main ( int  argc,
char **  argv 
)

main function

Parameters
argcnumber of shell parameters
argvarray with shell parameters

Definition at line 875 of file miniisc.c.

References BMScheckEmptyMemory, NULL, readArguments(), SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPfileExists(), SCIPprintError(), and solveMinIISC().