Scippy

SCIP

Solving Constraint Integer Programs

lpi_glop.cpp File Reference

Detailed Description

LP interface for Glop.

Author
Frederic Didier
Marc Pfetsch

Definition in file lpi_glop.cpp.

#include "ortools/base/version.h"
#include "ortools/glop/lp_solver.h"
#include "ortools/glop/revised_simplex.h"
#include "ortools/lp_data/lp_print_utils.h"
#include "ortools/lp_data/lp_data_utils.h"
#include "ortools/lp_data/proto_utils.h"
#include "ortools/util/file_util.h"
#include "ortools/util/stats.h"
#include "ortools/util/time_limit.h"
#include "ortools/base/logging.h"
#include "ortools/base/vlog_is_on.h"
#include "lpi/lpi.h"
#include "scip/pub_message.h"
#include <assert.h>

Go to the source code of this file.

Data Structures

struct  SCIP_LPi
 
struct  SCIP_LPiState
 
struct  SCIP_LPiNorms
 

Macros

#define UNSCALEDFEAS_CHECK   2
 

Functions

char * initGlopName ()
 
const char * SCIPlpiGetSolverName (void)
 
const char * SCIPlpiGetSolverDesc (void)
 
void * SCIPlpiGetSolverPointer (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiSetIntegralityInformation (SCIP_LPI *lpi, int ncols, int *intInfo)
 
SCIP_Bool SCIPlpiHasPrimalSolve (void)
 
SCIP_Bool SCIPlpiHasDualSolve (void)
 
SCIP_Bool SCIPlpiHasBarrierSolve (void)
 
LPI Creation and Destruction Methods
SCIP_RETCODE SCIPlpiCreate (SCIP_LPI **lpi, SCIP_MESSAGEHDLR *messagehdlr, const char *name, SCIP_OBJSEN objsen)
 
SCIP_RETCODE SCIPlpiFree (SCIP_LPI **lpi)
 
Modification Methods
SCIP_RETCODE SCIPlpiLoadColLP (SCIP_LPI *lpi, SCIP_OBJSEN objsen, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
 
SCIP_RETCODE SCIPlpiAddCols (SCIP_LPI *lpi, int ncols, const SCIP_Real *obj, const SCIP_Real *lb, const SCIP_Real *ub, char **colnames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
 
SCIP_RETCODE SCIPlpiDelCols (SCIP_LPI *lpi, int firstcol, int lastcol)
 
SCIP_RETCODE SCIPlpiDelColset (SCIP_LPI *lpi, int *dstat)
 
SCIP_RETCODE SCIPlpiAddRows (SCIP_LPI *lpi, int nrows, const SCIP_Real *lhs, const SCIP_Real *rhs, char **rownames, int nnonz, const int *beg, const int *ind, const SCIP_Real *val)
 
static void deleteRowsAndUpdateCurrentBasis (SCIP_LPI *lpi, const DenseBooleanColumn &rows_to_delete)
 
SCIP_RETCODE SCIPlpiDelRows (SCIP_LPI *lpi, int firstrow, int lastrow)
 
SCIP_RETCODE SCIPlpiDelRowset (SCIP_LPI *lpi, int *dstat)
 
SCIP_RETCODE SCIPlpiClear (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiChgBounds (SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *lb, const SCIP_Real *ub)
 
SCIP_RETCODE SCIPlpiChgSides (SCIP_LPI *lpi, int nrows, const int *ind, const SCIP_Real *lhs, const SCIP_Real *rhs)
 
SCIP_RETCODE SCIPlpiChgCoef (SCIP_LPI *lpi, int row, int col, SCIP_Real newval)
 
SCIP_RETCODE SCIPlpiChgObjsen (SCIP_LPI *lpi, SCIP_OBJSEN objsen)
 
SCIP_RETCODE SCIPlpiChgObj (SCIP_LPI *lpi, int ncols, const int *ind, const SCIP_Real *obj)
 
SCIP_RETCODE SCIPlpiScaleRow (SCIP_LPI *lpi, int row, SCIP_Real scaleval)
 
SCIP_RETCODE SCIPlpiScaleCol (SCIP_LPI *lpi, int col, SCIP_Real scaleval)
 
Data Accessing Methods
SCIP_RETCODE SCIPlpiGetNRows (SCIP_LPI *lpi, int *nrows)
 
SCIP_RETCODE SCIPlpiGetNCols (SCIP_LPI *lpi, int *ncols)
 
SCIP_RETCODE SCIPlpiGetObjsen (SCIP_LPI *lpi, SCIP_OBJSEN *objsen)
 
SCIP_RETCODE SCIPlpiGetNNonz (SCIP_LPI *lpi, int *nnonz)
 
SCIP_RETCODE SCIPlpiGetCols (SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *lb, SCIP_Real *ub, int *nnonz, int *beg, int *ind, SCIP_Real *val)
 
SCIP_RETCODE SCIPlpiGetRows (SCIP_LPI *lpi, int firstrow, int lastrow, SCIP_Real *lhs, SCIP_Real *rhs, int *nnonz, int *beg, int *ind, SCIP_Real *val)
 
SCIP_RETCODE SCIPlpiGetColNames (SCIP_LPI *lpi, int firstcol, int lastcol, char **colnames, char *namestorage, int namestoragesize, int *storageleft)
 
SCIP_RETCODE SCIPlpiGetRowNames (SCIP_LPI *lpi, int firstrow, int lastrow, char **rownames, char *namestorage, int namestoragesize, int *storageleft)
 
SCIP_RETCODE SCIPlpiGetObj (SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *vals)
 
SCIP_RETCODE SCIPlpiGetBounds (SCIP_LPI *lpi, int firstcol, int lastcol, SCIP_Real *lbs, SCIP_Real *ubs)
 
SCIP_RETCODE SCIPlpiGetSides (SCIP_LPI *lpi, int firstrow, int lastrow, SCIP_Real *lhss, SCIP_Real *rhss)
 
SCIP_RETCODE SCIPlpiGetCoef (SCIP_LPI *lpi, int row, int col, SCIP_Real *val)
 
Solving Methods
static void updateScaledLP (SCIP_LPI *lpi)
 
static bool checkUnscaledPrimalFeasibility (SCIP_LPI *lpi)
 
static SCIP_RETCODE SolveInternal (SCIP_LPI *lpi, bool recursive, std::unique_ptr< TimeLimit > &time_limit)
 
SCIP_RETCODE SCIPlpiSolvePrimal (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiSolveDual (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiSolveBarrier (SCIP_LPI *lpi, SCIP_Bool crossover)
 
SCIP_RETCODE SCIPlpiStartStrongbranch (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiEndStrongbranch (SCIP_LPI *lpi)
 
static bool IsDualBoundValid (ProblemStatus status)
 
static SCIP_RETCODE strongbranch (SCIP_LPI *lpi, int col_index, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
 
SCIP_RETCODE SCIPlpiStrongbranchFrac (SCIP_LPI *lpi, int col_index, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
 
SCIP_RETCODE SCIPlpiStrongbranchesFrac (SCIP_LPI *lpi, int *cols, int ncols, SCIP_Real *psols, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
 
SCIP_RETCODE SCIPlpiStrongbranchInt (SCIP_LPI *lpi, int col, SCIP_Real psol, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
 
SCIP_RETCODE SCIPlpiStrongbranchesInt (SCIP_LPI *lpi, int *cols, int ncols, SCIP_Real *psols, int itlim, SCIP_Real *down, SCIP_Real *up, SCIP_Bool *downvalid, SCIP_Bool *upvalid, int *iter)
 
Solution Information Methods
SCIP_Bool SCIPlpiWasSolved (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiGetSolFeasibility (SCIP_LPI *lpi, SCIP_Bool *primalfeasible, SCIP_Bool *dualfeasible)
 
SCIP_Bool SCIPlpiExistsPrimalRay (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiHasPrimalRay (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsPrimalUnbounded (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsPrimalInfeasible (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsPrimalFeasible (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiExistsDualRay (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiHasDualRay (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsDualUnbounded (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsDualInfeasible (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsDualFeasible (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsOptimal (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsStable (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsObjlimExc (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsIterlimExc (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsTimelimExc (SCIP_LPI *lpi)
 
int SCIPlpiGetInternalStatus (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiIgnoreInstability (SCIP_LPI *lpi, SCIP_Bool *success)
 
SCIP_RETCODE SCIPlpiGetObjval (SCIP_LPI *lpi, SCIP_Real *objval)
 
SCIP_RETCODE SCIPlpiGetSol (SCIP_LPI *lpi, SCIP_Real *objval, SCIP_Real *primsol, SCIP_Real *dualsol, SCIP_Real *activity, SCIP_Real *redcost)
 
SCIP_RETCODE SCIPlpiGetPrimalRay (SCIP_LPI *lpi, SCIP_Real *ray)
 
SCIP_RETCODE SCIPlpiGetDualfarkas (SCIP_LPI *lpi, SCIP_Real *dualfarkas)
 
SCIP_RETCODE SCIPlpiGetIterations (SCIP_LPI *lpi, int *iterations)
 
SCIP_RETCODE SCIPlpiGetRealSolQuality (SCIP_LPI *lpi, SCIP_LPSOLQUALITY qualityindicator, SCIP_Real *quality)
 
LP Basis Methods
static SCIP_BASESTAT ConvertGlopVariableStatus (VariableStatus status, Fractional rc)
 
static SCIP_BASESTAT ConvertGlopConstraintStatus (ConstraintStatus status, Fractional dual)
 
static VariableStatus ConvertSCIPVariableStatus (int status)
 
static VariableStatus ConvertSCIPConstraintStatusToSlackStatus (int status)
 
SCIP_RETCODE SCIPlpiGetBase (SCIP_LPI *lpi, int *cstat, int *rstat)
 
SCIP_RETCODE SCIPlpiSetBase (SCIP_LPI *lpi, const int *cstat, const int *rstat)
 
SCIP_RETCODE SCIPlpiGetBasisInd (SCIP_LPI *lpi, int *bind)
 
SCIP_RETCODE SCIPlpiGetBInvRow (SCIP_LPI *lpi, int r, SCIP_Real *coef, int *inds, int *ninds)
 
SCIP_RETCODE SCIPlpiGetBInvCol (SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
 
SCIP_RETCODE SCIPlpiGetBInvARow (SCIP_LPI *lpi, int r, const SCIP_Real *binvrow, SCIP_Real *coef, int *inds, int *ninds)
 
SCIP_RETCODE SCIPlpiGetBInvACol (SCIP_LPI *lpi, int c, SCIP_Real *coef, int *inds, int *ninds)
 
LP State Methods
SCIP_RETCODE SCIPlpiGetState (SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
 
SCIP_RETCODE SCIPlpiSetState (SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPISTATE *lpistate)
 
SCIP_RETCODE SCIPlpiClearState (SCIP_LPI *lpi)
 
SCIP_RETCODE SCIPlpiFreeState (SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPISTATE **lpistate)
 
SCIP_Bool SCIPlpiHasStateBasis (SCIP_LPI *lpi, SCIP_LPISTATE *lpistate)
 
SCIP_RETCODE SCIPlpiReadState (SCIP_LPI *lpi, const char *fname)
 
SCIP_RETCODE SCIPlpiWriteState (SCIP_LPI *lpi, const char *fname)
 
LP Pricing Norms Methods
SCIP_RETCODE SCIPlpiGetNorms (SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
 
SCIP_RETCODE SCIPlpiSetNorms (SCIP_LPI *lpi, BMS_BLKMEM *blkmem, const SCIP_LPINORMS *lpinorms)
 
SCIP_RETCODE SCIPlpiFreeNorms (SCIP_LPI *lpi, BMS_BLKMEM *blkmem, SCIP_LPINORMS **lpinorms)
 
Parameter Methods
SCIP_RETCODE SCIPlpiGetIntpar (SCIP_LPI *lpi, SCIP_LPPARAM type, int *ival)
 
SCIP_RETCODE SCIPlpiSetIntpar (SCIP_LPI *lpi, SCIP_LPPARAM type, int ival)
 
SCIP_RETCODE SCIPlpiGetRealpar (SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real *dval)
 
SCIP_RETCODE SCIPlpiSetRealpar (SCIP_LPI *lpi, SCIP_LPPARAM type, SCIP_Real dval)
 
SCIP_RETCODE SCIPlpiInterrupt (SCIP_LPI *lpi, SCIP_Bool interrupt)
 
Numerical Methods
SCIP_Real SCIPlpiInfinity (SCIP_LPI *lpi)
 
SCIP_Bool SCIPlpiIsInfinity (SCIP_LPI *lpi, SCIP_Real val)
 
File Interface Methods
SCIP_RETCODE SCIPlpiReadLP (SCIP_LPI *lpi, const char *fname)
 
SCIP_RETCODE SCIPlpiWriteLP (SCIP_LPI *lpi, const char *fname)
 

Variables

static char * glopname = initGlopName( )
 

Macro Definition Documentation

◆ UNSCALEDFEAS_CHECK

#define UNSCALEDFEAS_CHECK   2

uncomment to turn off scaling define feasibility check to possibly reoptimize: 0: no check, 1: completely new check, 2: check unscaled variable and activity values

Definition at line 135 of file lpi_glop.cpp.

Function Documentation

◆ initGlopName()

char * initGlopName ( )

Definition at line 147 of file lpi_glop.cpp.

References glopname.

◆ updateScaledLP()

static void updateScaledLP ( SCIP_LPI lpi)
static

update scaled linear program

Parameters
lpiLP interface structure

Definition at line 1297 of file lpi_glop.cpp.

References SCIP_LPi::linear_program, SCIP_LPi::lp_modified_since_last_solve, SCIP_LPi::parameters, SCIP_LPi::scaled_lp, and SCIP_LPi::scaler.

Referenced by SCIPlpiStartStrongbranch(), and SolveInternal().

◆ checkUnscaledPrimalFeasibility()

static bool checkUnscaledPrimalFeasibility ( SCIP_LPI lpi)
static

check primal feasibility

Parameters
lpiLP interface structure

Definition at line 1317 of file lpi_glop.cpp.

References SCIP_LPi::feastol, SCIP_LPi::linear_program, NULL, SCIP_LPi::parameters, SCIP_LPi::scaler, and SCIP_LPi::solver.

Referenced by SolveInternal().

◆ SolveInternal()

static SCIP_RETCODE SolveInternal ( SCIP_LPI lpi,
bool  recursive,
std::unique_ptr< TimeLimit > &  time_limit 
)
static

common function between the two LPI Solve() functions

Parameters
lpiLP interface structure
recursiveIs this a recursive call?
time_limittime limit

Definition at line 1371 of file lpi_glop.cpp.

References checkUnscaledPrimalFeasibility(), SCIP_LPi::from_scratch, SCIP_LPi::lp_modified_since_last_solve, SCIP_LPi::lp_time_limit_was_reached, SCIP_LPi::niterations, NULL, SCIP_LPi::parameters, SCIP_LPi::scaled_lp, SCIP_Longint, SCIP_LPERROR, SCIP_OKAY, SCIPdebugMessage, SCIP_LPi::solver, and updateScaledLP().

Referenced by SCIPlpiSolveDual(), and SCIPlpiSolvePrimal().

◆ IsDualBoundValid()

static bool IsDualBoundValid ( ProblemStatus  status)
static

determine whether the dual bound is valid

Parameters
statusstatus to be checked

Definition at line 1510 of file lpi_glop.cpp.

Referenced by strongbranch().

◆ strongbranch()

static SCIP_RETCODE strongbranch ( SCIP_LPI lpi,
int  col_index,
SCIP_Real  psol,
int  itlim,
SCIP_Real down,
SCIP_Real up,
SCIP_Bool downvalid,
SCIP_Bool upvalid,
int *  iter 
)
static

performs strong branching iterations

Parameters
lpiLP interface structure
col_indexcolumn to apply strong branching on
psolfractional current primal solution value of column
itlimiteration limit for strong branchings
downstores dual bound after branching column down
upstores dual bound after branching column up
downvalidstores whether the returned down value is a valid dual bound; otherwise, it can only be used as an estimate value
upvalidstores whether the returned up value is a valid dual bound; otherwise, it can only be used as an estimate value
iterstores total number of strong branching iterations, or -1; may be NULL

Definition at line 1519 of file lpi_glop.cpp.

References eps, EPSCEIL, EPSFLOOR, FALSE, IsDualBoundValid(), SCIP_LPi::linear_program, NULL, SCIP_LPi::parameters, SCIP_LPi::scaled_lp, SCIP_LPi::scaler, SCIP_OKAY, SCIPdebugMessage, SCIPerrorMessage, SCIP_LPi::solver, and TRUE.

Referenced by SCIPlpiStrongbranchFrac(), and SCIPlpiStrongbranchInt().

◆ ConvertGlopVariableStatus()

static SCIP_BASESTAT ConvertGlopVariableStatus ( VariableStatus  status,
Fractional  rc 
)
static

convert Glop variable basis status to SCIP status

Parameters
statusvariable status
rcreduced cost of variable

Definition at line 2212 of file lpi_glop.cpp.

References SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, and SCIPerrorMessage.

Referenced by SCIPlpiGetBase().

◆ ConvertGlopConstraintStatus()

static SCIP_BASESTAT ConvertGlopConstraintStatus ( ConstraintStatus  status,
Fractional  dual 
)
static

convert Glop constraint basis status to SCIP status

Parameters
statusconstraint status
dualdual variable value

Definition at line 2237 of file lpi_glop.cpp.

References SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, and SCIPerrorMessage.

Referenced by SCIPlpiGetBase().

◆ ConvertSCIPVariableStatus()

static VariableStatus ConvertSCIPVariableStatus ( int  status)
static

Convert SCIP variable status to Glop status

Parameters
statusSCIP variable status

Definition at line 2262 of file lpi_glop.cpp.

References SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, and SCIPerrorMessage.

Referenced by SCIPlpiSetBase().

◆ ConvertSCIPConstraintStatusToSlackStatus()

static VariableStatus ConvertSCIPConstraintStatusToSlackStatus ( int  status)
static

Convert a SCIP constraint status to its corresponding Glop slack VariableStatus.

Note that we swap the upper/lower bounds.

Parameters
statusSCIP constraint status

Definition at line 2287 of file lpi_glop.cpp.

References SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, and SCIPerrorMessage.

Referenced by SCIPlpiSetBase().

Variable Documentation

◆ glopname

char* glopname = initGlopName( )
static

Definition at line 145 of file lpi_glop.cpp.

Referenced by initGlopName(), and SCIPlpiGetSolverName().