Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

LP interface for QSopt version >= 070303.

Author
Daniel Espinoza
Marc Pfetsch

Definition in file lpi_qso.c.

#include "qsopt.h"
#include "scip/bitencode.h"
#include "lpi/lpi.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include <string.h>

Go to the source code of this file.

Data Structures

struct  SCIP_LPi
 
struct  SCIP_LPiNorms
 
struct  SCIP_LPiState
 

Macros

#define COLS_PER_PACKET   SCIP_DUALPACKETSIZE
 
#define ROWS_PER_PACKET   SCIP_DUALPACKETSIZE
 
#define FEASTOL   1e-6
 
#define EPSILON   1e-9
 
#define QS_TESTG(A, B, C)
 
#define QS_ERROR(A, ...)
 
#define QS_RETURN(A)
 
#define QS_CONDRET(A)
 

Typedefs

typedef SCIP_DUALPACKET COLPACKET
 
typedef SCIP_DUALPACKET ROWPACKET
 
typedef enum LPI_QSOPT_Algo LPI_QSOPT_ALGO
 

Enumerations

enum  LPI_QSOPT_Algo {
  LPI_QSOPT_ALGO_UNKNOWN = 0,
  LPI_QSOPT_ALGO_PRIMAL = 1,
  LPI_QSOPT_ALGO_DUAL = 2
}
 

Functions

static int colpacketNum (int ncols)
 
static int rowpacketNum (int nrows)
 
static void lpistatePack (SCIP_LPISTATE *lpistate, const int *cstat, const int *rstat)
 
static void lpistateUnpack (const SCIP_LPISTATE *lpistate, int *cstat, int *rstat)
 
static SCIP_RETCODE lpistateCreate (SCIP_LPISTATE **lpistate, BMS_BLKMEM *blkmem, int ncols, int nrows)
 
static void lpistateFree (SCIP_LPISTATE **lpistate, BMS_BLKMEM *blkmem)
 
static SCIP_RETCODE ensureTabMem (SCIP_LPI *const lpi, int sz)
 
static SCIP_RETCODE ensureColMem (SCIP_LPI *const lpi, int ncols)
 
static SCIP_RETCODE ensureRowMem (SCIP_LPI *const lpi, int nrows)
 
static SCIP_RETCODE convertSides (SCIP_LPI *const lpi, int nrows, const double *const lhs, const double *const rhs)
 
Miscellaneous Methods
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)
 
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 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 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 SCIPlpiGetObjsen (SCIP_LPI *lpi, SCIP_OBJSEN *objsen)
 
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
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)
 
SCIP_RETCODE SCIPlpiStrongbranchFrac (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 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
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)
 
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)
 

Macro Definition Documentation

◆ COLS_PER_PACKET

#define COLS_PER_PACKET   SCIP_DUALPACKETSIZE

Definition at line 33 of file lpi_qso.c.

Referenced by colpacketNum().

◆ ROWS_PER_PACKET

#define ROWS_PER_PACKET   SCIP_DUALPACKETSIZE

Definition at line 35 of file lpi_qso.c.

Referenced by rowpacketNum().

◆ FEASTOL

#define FEASTOL   1e-6

(feasibility) tolerance for qsopt

Definition at line 90 of file lpi_qso.c.

Referenced by SCIPlpiGetSol(), SCIPlpiStrongbranchesFrac(), SCIPlpiStrongbranchesInt(), SCIPlpiStrongbranchFrac(), and SCIPlpiStrongbranchInt().

◆ EPSILON

#define EPSILON   1e-9

tolerance for testing equality

Definition at line 93 of file lpi_qso.c.

Referenced by convertSides(), nail(), SCIPStpValidateSol(), and trail().

◆ QS_TESTG

#define QS_TESTG (   A,
  B,
 
)
Value:
do{{ \
if (A){ \
fprintf(stderr, C); \
__QS_PRINTLOC__; \
goto B;}}}while(0)

This macro is to print error messages and jump to the given point in the code, it also prints the file name and line where this happened.

Definition at line 100 of file lpi_qso.c.

Referenced by SCIPlpiGetCols(), SCIPlpiGetRows(), SCIPlpiGetSides(), SCIPlpiScaleCol(), and SCIPlpiScaleRow().

◆ QS_ERROR

#define QS_ERROR (   A,
  ... 
)
Value:
do{{ \
if (A){ \
fprintf(stderr,__VA_ARGS__); \
__QS_PRINTLOC__; \
return SCIP_LPERROR;}}}while(0)

This macro is to print error messages and to exit with SCIP_LPERROR.

Definition at line 107 of file lpi_qso.c.

Referenced by SCIPlpiGetColNames(), SCIPlpiGetRowNames(), and SCIPlpiWriteState().

◆ QS_RETURN

#define QS_RETURN (   A)
Value:
do{ \
const int __RVAL__ = (A); \
if (__RVAL__){ \
fprintf(stderr,"LP Error: QSopt returned %d",__RVAL__); \
__QS_PRINTLOC__; \
return SCIP_ERROR;} \
return SCIP_OKAY;}while(0)

Return value macro, if the value is non-zero, write to standard error the returning code and where this happened, and return SCIP_ERROR, otherwise return normal SCIP_OKAY termination code.

Definition at line 115 of file lpi_qso.c.

Referenced by SCIPlpiGetCols(), SCIPlpiGetRows(), SCIPlpiGetSides(), SCIPlpiScaleCol(), and SCIPlpiScaleRow().

◆ QS_CONDRET

Typedef Documentation

◆ COLPACKET

Definition at line 32 of file lpi_qso.c.

◆ ROWPACKET

Definition at line 34 of file lpi_qso.c.

◆ LPI_QSOPT_ALGO

Definition at line 43 of file lpi_qso.c.

Enumeration Type Documentation

◆ LPI_QSOPT_Algo

Enumerator
LPI_QSOPT_ALGO_UNKNOWN 

unknown

LPI_QSOPT_ALGO_PRIMAL 

primal simplex

LPI_QSOPT_ALGO_DUAL 

dual simplex

Definition at line 37 of file lpi_qso.c.

Function Documentation

◆ colpacketNum()

static int colpacketNum ( int  ncols)
static

returns the number of packets needed to store column packet information

Parameters
ncolsnumber of columns to store

Definition at line 151 of file lpi_qso.c.

References COLS_PER_PACKET.

Referenced by lpistateCreate(), and lpistateFree().

◆ rowpacketNum()

static int rowpacketNum ( int  nrows)
static

returns the number of packets needed to store row packet information

Parameters
nrowsnumber of rows to store

Definition at line 160 of file lpi_qso.c.

References ROWS_PER_PACKET.

Referenced by lpistateCreate(), and lpistateFree().

◆ lpistatePack()

static void lpistatePack ( SCIP_LPISTATE lpistate,
const int *  cstat,
const int *  rstat 
)
static

store row and column basis status in a packed LPi state object

Parameters
lpistatepointer to LPi state data
cstatbasis status of columns in unpacked format
rstatbasis status of rows in unpacked format

Definition at line 169 of file lpi_qso.c.

References SCIP_LPiState::ncols, SCIP_LPiState::nrows, NULL, SCIP_LPiState::packcstat, SCIP_LPiState::packrstat, and SCIPencodeDualBit().

Referenced by SCIPlpiGetState().

◆ lpistateUnpack()

static void lpistateUnpack ( const SCIP_LPISTATE lpistate,
int *  cstat,
int *  rstat 
)
static

unpacks row and column basis status from a packed LPi state object

Parameters
lpistatepointer to LPi state data
cstatbuffer for storing basis status of columns in unpacked format
rstatbuffer for storing basis status of rows in unpacked format

Definition at line 185 of file lpi_qso.c.

References SCIP_LPiState::ncols, SCIP_LPiState::nrows, NULL, SCIP_LPiState::packcstat, SCIP_LPiState::packrstat, and SCIPdecodeDualBit().

Referenced by SCIPlpiSetState().

◆ lpistateCreate()

static SCIP_RETCODE lpistateCreate ( SCIP_LPISTATE **  lpistate,
BMS_BLKMEM blkmem,
int  ncols,
int  nrows 
)
static

creates LPi state information object

Parameters
lpistatepointer to LPi state
blkmemblock memory
ncolsnumber of columns to store
nrowsnumber of rows to store

Definition at line 201 of file lpi_qso.c.

References BMSallocBlockMemory, BMSallocBlockMemoryArray, colpacketNum(), NULL, rowpacketNum(), SCIP_ALLOC, and SCIP_OKAY.

Referenced by SCIPlpiGetState().

◆ lpistateFree()

static void lpistateFree ( SCIP_LPISTATE **  lpistate,
BMS_BLKMEM blkmem 
)
static

frees LPi state information

Parameters
lpistatepointer to LPi state information (like basis information)
blkmemblock memory

Definition at line 222 of file lpi_qso.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArray, colpacketNum(), NULL, and rowpacketNum().

Referenced by SCIPlpiFreeState().

◆ ensureTabMem()

static SCIP_RETCODE ensureTabMem ( SCIP_LPI *const  lpi,
int  sz 
)
static

ensure size of column-related arrays

Parameters
lpipointer to an LP interface structure
szsize

Definition at line 244 of file lpi_qso.c.

References BMSreallocMemoryArray, SCIP_LPi::ibas, SCIP_LPi::itab, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIP_LPi::tbsz.

Referenced by SCIPlpiGetBase(), SCIPlpiGetBInvARow(), SCIPlpiGetSol(), SCIPlpiSetBase(), and SCIPlpiSetState().

◆ ensureColMem()

static SCIP_RETCODE ensureColMem ( SCIP_LPI *const  lpi,
int  ncols 
)
static

ensure size of column-related arrays

Parameters
lpipointer to an LP interface structure
ncolsnumber of columns

Definition at line 261 of file lpi_qso.c.

References BMSreallocMemoryArray, SCIP_LPi::colspace, SCIP_LPi::iccha, SCIP_LPi::iccnt, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by SCIPlpiAddCols(), SCIPlpiChgBounds(), SCIPlpiDelCols(), SCIPlpiGetBounds(), SCIPlpiGetCols(), SCIPlpiGetObj(), SCIPlpiGetState(), SCIPlpiLoadColLP(), and SCIPlpiSetState().

◆ ensureRowMem()

static SCIP_RETCODE ensureRowMem ( SCIP_LPI *const  lpi,
int  nrows 
)
static

◆ convertSides()

static SCIP_RETCODE convertSides ( SCIP_LPI *const  lpi,
int  nrows,
const double *const  lhs,
const double *const  rhs 
)
static

transform lhs/rhs into qsopt format

Parameters
lpipointer to an LP interface structure
nrowsnumber of rows
lhsleft hand side
rhsright hand side

Definition at line 298 of file lpi_qso.c.

References EPSEQ, EPSILON, SCIP_LPi::irbeg, SCIP_LPi::ircnt, SCIP_LPi::irhs, SCIP_LPi::irng, SCIP_LPi::isen, SCIP_LPi::nrows, NULL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPABORT, and SCIPerrorMessage.

Referenced by SCIPlpiAddRows(), SCIPlpiChgSides(), and SCIPlpiLoadColLP().