SCIP
Solving Constraint Integer Programs
lpi_spx1.cpp File Reference
Detailed Description
LP interface for SoPlex version 1.4 and higher.
This is an implementation of SCIP's LP interface for SoPlex. While the ratio test is fixed to SoPlex's standard, different pricing methods can be chosen and an autopricing strategy (start with devex and switch to steepest edge after too many iterations) is implemented directly. Scaler and simplifier may be applied if solving from scratch.
For debugging purposes, the SoPlex results can be double checked with CPLEX if SCIP_WITH_LPSCHECK is defined. This may yield false positives, since the LP is dumped to a file for transfering it to CPLEX, hence, precision may be lost.
Definition in file lpi_spx1.cpp.
#include "soplex.h"#include "spxsolver.h"#include "slufactor.h"#include "spxsteeppr.h"#include "spxparmultpr.h"#include "spxdevexpr.h"#include "spxfastrt.h"#include "spxmainsm.h"#include "spxequilisc.h"#include "spxboundflippingrt.h"#include "scip/pub_message.h"#include <cassert>#include "lpi/lpi.h"#include "scip/bitencode.h"Go to the source code of this file.
Data Structures | |
| struct | SCIP_LPi |
| struct | SCIP_LPiState |
| struct | SCIP_LPiNorms |
Macros | |
| #define | AUTOPRICING_ITERSWITCH 10000 |
| #define | STRONGBRANCH_RESTOREBASIS |
| #define | SOPLEX_SUBVERSION 0 |
| #define | SOPLEX_APIVERSION 0 |
| #define | WITH_BOUNDFLIPPING |
| #define | SOPLEX_VERBLEVEL 5 |
| #define | NULL 0 |
| #define | SOPLEX_TRY(messagehdlr, x) |
| #define | SOPLEX_TRY_ABORT(x) |
| #define | COLS_PER_PACKET SCIP_DUALPACKETSIZE |
| #define | ROWS_PER_PACKET SCIP_DUALPACKETSIZE |
Typedefs | |
| typedef SCIP_DUALPACKET | COLPACKET |
| typedef SCIP_DUALPACKET | ROWPACKET |
Variables | |
| static const char | spxname [20] = {'S', 'o', 'p', 'l', 'e', 'x', '1', ' ', SOPLEX_VERSION/100 + '0', '.', (SOPLEX_VERSION % 100)/10 + '0', '.', SOPLEX_VERSION % 10 + '0', '\0'} |
| static char * | spxdesc = initSpxDesc() |
Macro Definition Documentation
◆ AUTOPRICING_ITERSWITCH
| #define AUTOPRICING_ITERSWITCH 10000 |
start with devex and switch to steepest edge after this many iterations
Definition at line 43 of file lpi_spx1.cpp.
◆ STRONGBRANCH_RESTOREBASIS
| #define STRONGBRANCH_RESTOREBASIS |
if defined then in SCIPlpiStrongbranch() we restore the basis after the down branch and after the up branch; if false only after the end of a strong branching phase, which however seems to mostly increase strong branching time and iterations
Definition at line 47 of file lpi_spx1.cpp.
◆ SOPLEX_SUBVERSION
| #define SOPLEX_SUBVERSION 0 |
Definition at line 98 of file lpi_spx1.cpp.
◆ SOPLEX_APIVERSION
| #define SOPLEX_APIVERSION 0 |
Definition at line 102 of file lpi_spx1.cpp.
◆ WITH_BOUNDFLIPPING
| #define WITH_BOUNDFLIPPING |
Definition at line 117 of file lpi_spx1.cpp.
◆ SOPLEX_VERBLEVEL
| #define SOPLEX_VERBLEVEL 5 |
verbosity level for LPINFO
Definition at line 151 of file lpi_spx1.cpp.
◆ NULL
| #define NULL 0 |
Definition at line 161 of file lpi_spx1.cpp.
◆ SOPLEX_TRY
| #define SOPLEX_TRY | ( | messagehdlr, | |
| x | |||
| ) |
Value:
do \
{ \
try \
{ \
(x); \
} \
catch( const SPxMemoryException& E ) \
{ \
std::string s = E.what(); \
SCIPerrorMessage("SoPlex threw a memory exception: %s\n", s.c_str()); \
return SCIP_ERROR; \
} \
catch( const SPxException& E ) \
{ \
std::string s = E.what(); \
SCIPmessagePrintWarning((messagehdlr), "SoPlex threw an exception: %s\n", s.c_str()); \
return SCIP_LPERROR; \
} \
} \
while( FALSE )
Macro for a single SoPlex call for which exceptions have to be catched - return an LP error. We make no distinction between different exception types, e.g., between memory allocation and other exceptions.
Definition at line 172 of file lpi_spx1.cpp.
◆ SOPLEX_TRY_ABORT
| #define SOPLEX_TRY_ABORT | ( | x | ) |
Value:
do \
{ \
try \
{ \
(x); \
} \
catch( const SPxException& E ) \
{ \
std::string s = E.what(); \
SCIPerrorMessage("SoPlex threw an exception: %s\n", s.c_str()); \
abort(); \
} \
} \
while( FALSE )
Definition at line 217 of file lpi_spx1.cpp.
◆ COLS_PER_PACKET
| #define COLS_PER_PACKET SCIP_DUALPACKETSIZE |
Definition at line 1395 of file lpi_spx1.cpp.
◆ ROWS_PER_PACKET
| #define ROWS_PER_PACKET SCIP_DUALPACKETSIZE |
Definition at line 1397 of file lpi_spx1.cpp.
Typedef Documentation
◆ COLPACKET
| typedef SCIP_DUALPACKET COLPACKET |
Definition at line 1394 of file lpi_spx1.cpp.
◆ ROWPACKET
| typedef SCIP_DUALPACKET ROWPACKET |
Definition at line 1396 of file lpi_spx1.cpp.
Function Documentation
◆ ensureCstatMem()
|
static |
resizes cstat array to have at least num entries
- Parameters
-
lpi LP interface structure num minimal number of entries in array
Definition at line 1442 of file lpi_spx1.cpp.
References BMSreallocMemoryArray, SCIP_LPi::cstat, SCIP_LPi::cstatsize, MAX, NULL, SCIP_ALLOC, and SCIP_OKAY.
Referenced by SCIPlpiGetState(), and SCIPlpiSetState().
◆ ensureRstatMem()
|
static |
resizes rstat array to have at least num entries
- Parameters
-
lpi LP interface structure num minimal number of entries in array
Definition at line 1464 of file lpi_spx1.cpp.
References BMSreallocMemoryArray, MAX, NULL, SCIP_LPi::rstat, SCIP_LPi::rstatsize, SCIP_ALLOC, and SCIP_OKAY.
Referenced by SCIPlpiGetState(), and SCIPlpiSetState().
◆ colpacketNum()
|
static |
returns the number of packets needed to store column packet information
- Parameters
-
ncols number of columns to store
Definition at line 1493 of file lpi_spx1.cpp.
References COLS_PER_PACKET.
Referenced by lpistateCreate(), and lpistateFree().
◆ rowpacketNum()
|
static |
returns the number of packets needed to store row packet information
- Parameters
-
nrows number of rows to store
Definition at line 1502 of file lpi_spx1.cpp.
References ROWS_PER_PACKET.
Referenced by lpistateCreate(), and lpistateFree().
◆ lpistatePack()
|
static |
store row and column basis status in a packed LPi state object
- Parameters
-
lpistate pointer to LPi state data cstat basis status of columns in unpacked format rstat basis status of rows in unpacked format
Definition at line 1511 of file lpi_spx1.cpp.
References SCIP_LPiState::ncols, SCIP_LPiState::nrows, NULL, SCIP_LPiState::packcstat, SCIP_LPiState::packrstat, and SCIPencodeDualBit().
Referenced by SCIPlpiGetState().
◆ lpistateUnpack()
|
static |
unpacks row and column basis status from a packed LPi state object
- Parameters
-
lpistate pointer to LPi state data cstat buffer for storing basis status of columns in unpacked format rstat buffer for storing basis status of rows in unpacked format
Definition at line 1527 of file lpi_spx1.cpp.
References SCIP_LPiState::ncols, SCIP_LPiState::nrows, NULL, SCIP_LPiState::packcstat, SCIP_LPiState::packrstat, and SCIPdecodeDualBit().
Referenced by SCIPlpiSetState().
◆ lpistateCreate()
|
static |
creates LPi state information object
- Parameters
-
lpistate pointer to LPi state blkmem block memory ncols number of columns to store nrows number of rows to store
Definition at line 1543 of file lpi_spx1.cpp.
References BMSallocBlockMemory, BMSallocBlockMemoryArray, colpacketNum(), NULL, rowpacketNum(), SCIP_ALLOC, and SCIP_OKAY.
Referenced by SCIPlpiGetState().
◆ lpistateFree()
|
static |
frees LPi state information
- Parameters
-
lpistate pointer to LPi state information (like basis information) blkmem block memory
Definition at line 1567 of file lpi_spx1.cpp.
References BMSfreeBlockMemory, BMSfreeBlockMemoryArray, colpacketNum(), NULL, and rowpacketNum().
Referenced by SCIPlpiFreeState().
◆ spxObjsen()
|
static |
converts SCIP's objective sense into SoPlex's objective sense
- Parameters
-
objsen SCIP's objective sense value
Definition at line 1593 of file lpi_spx1.cpp.
References SCIP_OBJSEN_MAXIMIZE, SCIP_OBJSEN_MINIMIZE, SCIPABORT, and SCIPerrorMessage.
Referenced by SCIPlpiChgObjsen(), and SCIPlpiLoadColLP().
◆ invalidateSolution()
|
static |
marks the current LP to be unsolved
Definition at line 1612 of file lpi_spx1.cpp.
References SCIP_LPi::factorization, FALSE, NULL, and SCIP_LPi::solved.
Referenced by SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiChgBounds(), SCIPlpiChgCoef(), SCIPlpiChgObj(), SCIPlpiChgObjsen(), SCIPlpiChgSides(), SCIPlpiClear(), SCIPlpiCreate(), SCIPlpiDelCols(), SCIPlpiDelColset(), SCIPlpiDelRows(), SCIPlpiDelRowset(), SCIPlpiLoadColLP(), SCIPlpiScaleCol(), SCIPlpiScaleRow(), SCIPlpiSetBase(), and spxSolve().
◆ initSpxDesc()
| char * initSpxDesc | ( | ) |
Definition at line 1644 of file lpi_spx1.cpp.
References spxdesc.
◆ spxSolve()
|
static |
solves LP – used for both, primal and dual simplex, because SoPlex doesn't distinct the two cases
- Parameters
-
lpi LP interface structure rep basis representation type algorithm type
Definition at line 2883 of file lpi_spx1.cpp.
References invalidateSolution(), NULL, SCIP_LPERROR, SCIP_OKAY, SCIPdebugMessage, SCIP_LPi::solved, SCIP_LPi::spx, TRUE, and UNKNOWN.
Referenced by SCIPlpiSolveDual(), and SCIPlpiSolvePrimal().
◆ lpiStrongbranch()
|
static |
performs strong branching iterations on one arbitrary candidate
- Parameters
-
lpi LP interface structure col column to apply strong branching on psol 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 3065 of file lpi_spx1.cpp.
References EPSCEIL, EPSFLOOR, FALSE, NULL, SCIP_LPERROR, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIP_LPi::spx, TRUE, and UNKNOWN.
Referenced by SCIPlpiStrongbranchesFrac(), SCIPlpiStrongbranchesInt(), SCIPlpiStrongbranchFrac(), and SCIPlpiStrongbranchInt().
◆ getRedCostEst()
|
static |
Return reduced cost of column col if this is readily available, otherwise return 0.0
Definition at line 3997 of file lpi_spx1.cpp.
References NULL, SCIP_OKAY, and SCIP_Real.
Referenced by SCIPlpiGetBase().
◆ lpiGetBInvVec()
|
static |
get solution of basis matrix B * coef = rhs
- Parameters
-
lpi LP interface structure rhs right-hand side vector coef vector to return coefficients
Definition at line 4532 of file lpi_spx1.cpp.
References BMSallocMemoryArray, BMSfreeMemoryArray, SCIP_LPi::factorization, SCIP_LPi::messagehdlr, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_LPERROR, SCIP_OKAY, SCIPdebugMessage, SCIPlpiGetBasisInd(), SCIPmessagePrintWarning(), SCIP_LPi::spx, x, and y.
Referenced by SCIPlpiGetBInvACol(), and SCIPlpiGetBInvCol().
◆ fileExists()
|
static |
returns, whether the given file exists
- Parameters
-
filename file name
Definition at line 5449 of file lpi_spx1.cpp.
References FALSE, NULL, and TRUE.
Referenced by SCIPlpiReadLP().
Variable Documentation
◆ spxname
|
static |
Definition at line 1639 of file lpi_spx1.cpp.
Referenced by SCIPlpiGetSolverName().
◆ spxdesc
|
static |
Definition at line 1642 of file lpi_spx1.cpp.
Referenced by initSpxDesc(), and SCIPlpiGetSolverDesc().