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
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 [128]

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 126 of file lpi_glop.cpp.

Function Documentation

updateScaledLP()

static void updateScaledLP ( SCIP_LPI *  lpi )

static

update scaled linear program

Parameters

lpi	LP interface structure

Definition at line 1280 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

lpi	LP interface structure

Definition at line 1300 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

lpi	LP interface structure
recursive	Is this a recursive call?
time_limit	time limit

Definition at line 1354 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

status

status to be checked

Definition at line 1493 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

lpi	LP interface structure
col_index	column to apply strong branching on
psol	fractional current primal solution value of column
itlim	iteration limit for strong branchings
down	stores dual bound after branching column down
up	stores dual bound after branching column up
downvalid	stores whether the returned down value is a valid dual bound; otherwise, it can only be used as an estimate value
upvalid	stores whether the returned up value is a valid dual bound; otherwise, it can only be used as an estimate value
iter	stores total number of strong branching iterations, or -1; may be NULL

Definition at line 1502 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

status	variable status
rc	reduced cost of variable

Definition at line 2195 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

status	constraint status
dual	dual variable value

Definition at line 2220 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

status

SCIP variable status

Definition at line 2245 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

status

SCIP constraint status

Definition at line 2270 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[128]

static

Definition at line 134 of file lpi_glop.cpp.

Referenced by SCIPlpiGetSolverName().