/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the program and library */ /* SCIP --- Solving Constraint Integer Programs */ /* */ /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */ /* fuer Informationstechnik Berlin */ /* */ /* SCIP is distributed under the terms of the ZIB Academic License. */ /* */ /* You should have received a copy of the ZIB Academic License */ /* along with SCIP; see the file COPYING. If not visit scipopt.org. */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /**@file lpi_qso.c * @ingroup OTHER_CFILES * @brief LP interface for QSopt version >= 070303 * @author Daniel Espinoza * @author Marc Pfetsch */ /*--+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ #include "qsopt.h" #include "scip/bitencode.h" #include "lpi/lpi.h" #include "scip/pub_message.h" #include "scip/pub_misc.h" #include typedef SCIP_DUALPACKET COLPACKET; /* each column needs two bits of information (basic/on_lower/on_upper) */ #define COLS_PER_PACKET SCIP_DUALPACKETSIZE typedef SCIP_DUALPACKET ROWPACKET; /* each row needs two bit of information (basic/on_lower/on_upper) */ #define ROWS_PER_PACKET SCIP_DUALPACKETSIZE enum LPI_QSOPT_Algo { LPI_QSOPT_ALGO_UNKNOWN = 0, /**< unknown */ LPI_QSOPT_ALGO_PRIMAL = 1, /**< primal simplex */ LPI_QSOPT_ALGO_DUAL = 2 /**< dual simplex */ }; typedef enum LPI_QSOPT_Algo LPI_QSOPT_ALGO; /** LP interface */ struct SCIP_LPi { QSprob prob; /**< LP struct pointer */ int solstat; /**< solution status of last optimization call */ LPI_QSOPT_ALGO algo; /**< previously used algorithm */ int previt; /**< previous number of simplex iterations performed */ int rowspace; /**< current size of internal row-related arrays */ char* isen; /**< array of length rowspace */ double* irhs; /**< array of rhs rowspace */ double* irng; /**< array of range rowspace */ int* ircnt; /**< array of count rowspace */ int* irbeg; /**< array of beginning index rowspace */ int colspace; /**< current size of internal column-related arrays */ int* iccnt; /**< array of length colspace */ char* iccha; /**< array of type colspace */ int tbsz; /**< current size of tableau-related arrays */ double* itab; /**< array of length tbsz */ char* ibas; /**< array of length tbsz */ int pricing; /**< SCIP pricing option */ SCIP_MESSAGEHDLR* messagehdlr; /**< messagehdlr handler to printing messages, or NULL */ }; /** row norms */ struct SCIP_LPiNorms { int nrows; /**< number of rows */ int ncols; /**< number of columns */ char* cstat; /**< basis status of columns */ char* rstat; /**< basis status of rows */ SCIP_Real* norms; /**< row norms */ }; /** solver name */ static char __qsstr[SCIP_MAXSTRLEN]; /* * local defines */ /** (feasibility) tolerance for qsopt */ #define FEASTOL 1e-6 /** tolerance for testing equality */ #define EPSILON 1e-9 /** print location of the calling line */ #define __QS_PRINTLOC__ fprintf(stderr,", in (%s:%d)\n", __FILE__, __LINE__) /** 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. */ #define QS_TESTG(A,B,C) do{{ \ if (A){ \ fprintf(stderr, C); \ __QS_PRINTLOC__; \ goto B;}}}while(0) /** This macro is to print error messages and to exit with SCIP_LPERROR. */ #define QS_ERROR(A,...) do{{ \ if (A){ \ fprintf(stderr,__VA_ARGS__); \ __QS_PRINTLOC__; \ return SCIP_LPERROR;}}}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. */ #define QS_RETURN(A) 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 do nothing. */ #define QS_CONDRET(A) do{ \ const int __RVAL__ = (A); \ if (__RVAL__){ \ fprintf(stderr,"LP Error: QSopt returned %d",__RVAL__); \ __QS_PRINTLOC__; \ return SCIP_LPERROR;} \ }while(0) /* * LPi state methods */ /** LPi state stores basis information */ struct SCIP_LPiState { int ncols; /**< number of LP columns */ int nrows; /**< number of LP rows */ COLPACKET* packcstat; /**< column basis status in compressed form */ ROWPACKET* packrstat; /**< row basis status in compressed form */ }; /** returns the number of packets needed to store column packet information */ static int colpacketNum( int ncols /**< number of columns to store */ ) { return (ncols + (int)COLS_PER_PACKET-1)/(int)COLS_PER_PACKET; } /** returns the number of packets needed to store row packet information */ static int rowpacketNum( int nrows /**< number of rows to store */ ) { return (nrows + (int)ROWS_PER_PACKET-1)/(int)ROWS_PER_PACKET; } /** store row and column basis status in a packed LPi state object */ static void lpistatePack( SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */ const int* cstat, /**< basis status of columns in unpacked format */ const int* rstat /**< basis status of rows in unpacked format */ ) { assert(lpistate != NULL); assert(lpistate->packcstat != NULL); assert(lpistate->packrstat != NULL); SCIPencodeDualBit(cstat, lpistate->packcstat, lpistate->ncols); SCIPencodeDualBit(rstat, lpistate->packrstat, lpistate->nrows); } /** unpacks row and column basis status from a packed LPi state object */ static void lpistateUnpack( const SCIP_LPISTATE* lpistate, /**< pointer to LPi state data */ int* cstat, /**< buffer for storing basis status of columns in unpacked format */ int* rstat /**< buffer for storing basis status of rows in unpacked format */ ) { assert(lpistate != NULL); assert(lpistate->packcstat != NULL); assert(lpistate->packrstat != NULL); SCIPdecodeDualBit(lpistate->packcstat, cstat, lpistate->ncols); SCIPdecodeDualBit(lpistate->packrstat, rstat, lpistate->nrows); } /** creates LPi state information object */ static SCIP_RETCODE lpistateCreate( SCIP_LPISTATE** lpistate, /**< pointer to LPi state */ BMS_BLKMEM* blkmem, /**< block memory */ int ncols, /**< number of columns to store */ int nrows /**< number of rows to store */ ) { assert(lpistate != NULL); assert(blkmem != NULL); assert(ncols >= 0); assert(nrows >= 0); SCIP_ALLOC( BMSallocBlockMemory(blkmem, lpistate) ); SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum(ncols)) ); SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum(nrows)) ); return SCIP_OKAY; } /** frees LPi state information */ static void lpistateFree( SCIP_LPISTATE** lpistate, /**< pointer to LPi state information (like basis information) */ BMS_BLKMEM* blkmem /**< block memory */ ) { assert(blkmem != NULL); assert(lpistate != NULL); assert(*lpistate != NULL); BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packcstat, colpacketNum((*lpistate)->ncols)); BMSfreeBlockMemoryArray(blkmem, &(*lpistate)->packrstat, rowpacketNum((*lpistate)->nrows)); BMSfreeBlockMemory(blkmem, lpistate); } /* * local functions */ /** ensure size of column-related arrays */ static SCIP_RETCODE ensureTabMem( SCIP_LPI* const lpi, /**< pointer to an LP interface structure */ int sz /**< size */ ) { assert(lpi != NULL); if( lpi->tbsz < sz ) { lpi->tbsz = sz*2; SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->itab), lpi->tbsz) ); SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->ibas), lpi->tbsz) ); } return SCIP_OKAY; } /** ensure size of column-related arrays */ static SCIP_RETCODE ensureColMem( SCIP_LPI* const lpi, /**< pointer to an LP interface structure */ int ncols /**< number of columns */ ) { assert(lpi != NULL); if( lpi->colspace < ncols ) { lpi->colspace = ncols*2; SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->iccnt), lpi->colspace) ); SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->iccha), lpi->colspace) ); } return SCIP_OKAY; } /** ensure size of row-related arrays */ static SCIP_RETCODE ensureRowMem( SCIP_LPI* const lpi, /**< pointer to an LP interface structure */ int nrows /**< number of rows */ ) { assert(lpi != NULL); if( lpi->rowspace < nrows ) { lpi->rowspace = nrows*2; SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->isen), lpi->rowspace) ); SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->irhs), lpi->rowspace) ); SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->irng), lpi->rowspace) ); SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->ircnt), lpi->rowspace) ); SCIP_ALLOC( BMSreallocMemoryArray(&(lpi->irbeg), lpi->rowspace) ); } return SCIP_OKAY; } /** transform lhs/rhs into qsopt format */ static SCIP_RETCODE convertSides( SCIP_LPI* const lpi, /**< pointer to an LP interface structure */ int nrows, /**< number of rows */ const double* const lhs, /**< left hand side */ const double* const rhs /**< right hand side */ ) { int state; register int i; assert(lpi != NULL); assert(lhs != NULL); assert(rhs!= NULL); for( i = 0 ; i < nrows ; ++i ) { state = ((lhs[i] <= -QS_MAXDOUBLE ? 1 : 0) | (rhs[i] >= QS_MAXDOUBLE ? 2 : 0)); lpi->ircnt[i] = 0; lpi->irbeg[i] = 0; switch( state ) { case 0: /* check for equations */ if( EPSEQ(lhs[i], rhs[i], EPSILON) ) { lpi->isen[i] = 'E'; lpi->irhs[i] = lhs[i]; lpi->irng[i] = 0.0; } else { lpi->isen[i] = 'R'; lpi->irhs[i] = lhs[i]; lpi->irng[i] = rhs[i] - lhs[i]; assert(lpi->irng[i] >= 0.0); } break; case 1: lpi->isen[i] = 'L'; lpi->irhs[i] = rhs[i]; lpi->irng[i] = 0; break; case 2: lpi->isen[i] = 'G'; lpi->irhs[i] = lhs[i]; lpi->irng[i] = 0; break; default: SCIPerrorMessage("Error, constraint %d has no bounds!", i); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } return SCIP_OKAY; } /* * Miscellaneous Methods */ /**@name Miscellaneous Methods */ /**@{ */ /** gets name and version of LP solver */ const char* SCIPlpiGetSolverName(void) { char* vname; size_t vnamelen; /* need to copy string to __qsstr, since vname will be freed */ vname = QSversion(); vnamelen = strlen(vname); if ( vnamelen >= SCIP_MAXSTRLEN-1 ) vnamelen = SCIP_MAXSTRLEN - 2; memcpy(__qsstr, vname, vnamelen); __qsstr[vnamelen+1] = '\0'; QSfree(vname); return __qsstr; } /** gets description of LP solver (developer, webpage, ...) */ const char* SCIPlpiGetSolverDesc( void ) { return "Linear Programming Solver developed by D. Applegate, W. Cook, S. Dash, and M. Mevenkamp (www.isye.gatech.edu/~wcook/qsopt)"; } /** gets pointer for LP solver - use only with great care */ void* SCIPlpiGetSolverPointer( SCIP_LPI* lpi /**< pointer to an LP interface structure */ ) { assert(lpi != NULL); return (void*) lpi->prob; } /** pass integrality information to LP solver */ SCIP_RETCODE SCIPlpiSetIntegralityInformation( SCIP_LPI* lpi, /**< pointer to an LP interface structure */ int ncols, /**< length of integrality array */ int* intInfo /**< integrality array (0: continuous, 1: integer). May be NULL iff ncols is 0. */ ) { /*lint --e{715}*/ assert( lpi != NULL ); assert( ncols >= 0 ); assert( ncols == 0 || intInfo != NULL ); SCIPerrorMessage("SCIPlpiSetIntegralityInformation() has not been implemented yet.\n"); return SCIP_LPERROR; } /** informs about availability of a primal simplex solving method */ SCIP_Bool SCIPlpiHasPrimalSolve( void ) { return TRUE; } /** informs about availability of a dual simplex solving method */ SCIP_Bool SCIPlpiHasDualSolve( void ) { return TRUE; } /** informs about availability of a barrier solving method */ SCIP_Bool SCIPlpiHasBarrierSolve( void ) { return FALSE; } /**@} */ /* * LPI Creation and Destruction Methods */ /**@name LPI Creation and Destruction Methods */ /**@{ */ /** creates an LP problem object */ SCIP_RETCODE SCIPlpiCreate( SCIP_LPI** lpi, /**< pointer to an LP interface structure */ SCIP_MESSAGEHDLR* messagehdlr, /**< message handler to use for printing messages, or NULL */ const char* name, /**< problem name */ SCIP_OBJSEN objsen /**< objective sense */ ) { /* QSopt only works with doubles as floating points and bool as integers */ assert(sizeof(SCIP_Real) == sizeof(double)); /*lint !e506*/ assert(sizeof(SCIP_Bool) == sizeof(int)); /*lint !e506*/ assert(name != NULL); assert(lpi != NULL); SCIPdebugMessage("SCIPlpiCreate()\n"); /* create LP */ SCIP_ALLOC( BMSallocMemory(lpi) ); memset(*lpi, 0, sizeof(struct SCIP_LPi)); (*lpi)->prob = QScreate_prob(name, (int) objsen); if ( (*lpi)->prob == NULL ) { SCIPerrorMessage("No memory\n"); return SCIP_LPERROR; } (*lpi)->rowspace = 1024; SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->isen),1024) ); SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->irhs),1024) ); SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->irng),1024) ); SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->irbeg),1024) ); SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->ircnt),1024) ); (*lpi)->colspace = 1024; SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->iccnt), 1024) ); SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->iccha), 1024) ); (*lpi)->tbsz = 1024; SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->itab), 1024) ); SCIP_ALLOC( BMSallocMemoryArray(&((*lpi)->ibas), 1024) ); (*lpi)->messagehdlr = messagehdlr; (*lpi)->algo = LPI_QSOPT_ALGO_UNKNOWN; return SCIP_OKAY; } /** deletes an LP problem object */ SCIP_RETCODE SCIPlpiFree( SCIP_LPI** lpi /**< pointer to an LP interface structure */ ) { assert(lpi != NULL); assert(*lpi != NULL); SCIPdebugMessage("SCIPlpiFree()\n"); /* free LP */ QSfree_prob((*lpi)->prob); BMSfreeMemoryArray( &((*lpi)->isen) ); BMSfreeMemoryArray( &((*lpi)->irhs) ); BMSfreeMemoryArray( &((*lpi)->irng) ); BMSfreeMemoryArray( &((*lpi)->ircnt) ); BMSfreeMemoryArray( &((*lpi)->irbeg) ); BMSfreeMemoryArray( &((*lpi)->iccnt) ); BMSfreeMemoryArray( &((*lpi)->iccha) ); BMSfreeMemoryArray( &((*lpi)->itab) ); BMSfreeMemoryArray( &((*lpi)->ibas) ); /* free memory */ BMSfreeMemory(lpi); return SCIP_OKAY; } /**@} */ /* * Modification Methods */ /**@name Modification Methods */ /**@{ */ /** copies LP data with column matrix into LP solver */ SCIP_RETCODE SCIPlpiLoadColLP( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_OBJSEN objsen, /**< objective sense */ int ncols, /**< number of columns */ const SCIP_Real* obj, /**< objective function values of columns */ const SCIP_Real* lb, /**< lower bounds of columns */ const SCIP_Real* ub, /**< upper bounds of columns */ char** colnames, /**< column names, or NULL */ int nrows, /**< number of rows */ const SCIP_Real* lhs, /**< left hand sides of rows */ const SCIP_Real* rhs, /**< right hand sides of rows */ char** rownames, /**< row names, or NULL */ int nnonz, /**< number of nonzero elements in the constraint matrix */ const int* beg, /**< start index of each column in ind- and val-array */ const int* ind, /**< row indices of constraint matrix entries */ const SCIP_Real* val /**< values of constraint matrix entries */ ) { register int i; #ifndef NDEBUG { int j; for( j = 0; j < nnonz; j++ ) assert( val[j] != 0 ); } #endif assert(lpi != NULL); assert(lpi->prob != NULL); assert(lhs != NULL); assert(rhs != NULL); assert(obj != NULL); assert(lb != NULL); assert(ub != NULL); assert(beg != NULL); assert(ind != NULL); assert(val != NULL); lpi->solstat = 0; SCIPdebugMessage("loading LP in column format into QSopt: %d cols, %d rows\n", ncols, nrows); /* delete old LP */ SCIP_CALL( SCIPlpiClear(lpi) ); /* set sense */ if( objsen == SCIP_OBJSEN_MAXIMIZE ) { QS_CONDRET( QSchange_objsense(lpi->prob, QS_MAX) ); } else { QS_CONDRET( QSchange_objsense(lpi->prob, QS_MIN) ); } /* add rows with no matrix, and then the columns, first ensure space */ SCIP_CALL( ensureRowMem(lpi, nrows) ); /* convert lhs/rhs into sen/rhs/range tuples */ SCIP_CALL( convertSides(lpi, nrows, lhs, rhs) ); /* now we add the rows */ QS_CONDRET( QSadd_ranged_rows(lpi->prob, nrows, lpi->ircnt, lpi->irbeg, 0, 0, lpi->irhs, lpi->isen, lpi->irng, (const char**)rownames) ); /* ensure column size */ SCIP_CALL( ensureColMem(lpi, ncols) ); /* compute column lengths */ for( i = 0; i < ncols-1; ++i ) { lpi->iccnt[i] = beg[i+1] - beg[i]; assert(lpi->iccnt[i] >= 0); } if( ncols > 0 ) { lpi->iccnt[ncols-1] = nnonz - beg[ncols-1]; assert(lpi->iccnt[ncols-1] >= 0); } /* and add the columns */ QS_CONDRET( QSadd_cols(lpi->prob, ncols, lpi->iccnt, (int*) beg, (int*) ind, (SCIP_Real*) val, (SCIP_Real*) obj, (SCIP_Real*) lb, (SCIP_Real*) ub, (const char**)colnames) ); return SCIP_OKAY; } /** adds columns to the LP */ SCIP_RETCODE SCIPlpiAddCols( SCIP_LPI* lpi, /**< LP interface structure */ int ncols, /**< number of columns to be added */ const SCIP_Real* obj, /**< objective function values of new columns */ const SCIP_Real* lb, /**< lower bounds of new columns */ const SCIP_Real* ub, /**< upper bounds of new columns */ char** colnames, /**< column names, or NULL */ int nnonz, /**< number of nonzero elements to be added to the constraint matrix */ const int* beg, /**< start index of each column in ind- and val-array, or NULL if nnonz == 0 */ const int* ind, /**< row indices of constraint matrix entries, or NULL if nnonz == 0 */ const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */ ) { register int i; int* lbeg; assert( lpi != NULL ); assert( lpi->prob != NULL ); assert(obj != NULL); assert(nnonz == 0 || beg != NULL); assert(nnonz == 0 || ind != NULL); assert(nnonz == 0 || val != NULL); assert(nnonz >= 0); assert(ncols >= 0); SCIPdebugMessage("adding %d columns with %d nonzeros to QSopt\n", ncols, nnonz); if ( ncols <= 0 ) return SCIP_OKAY; assert( lb != NULL && ub != NULL ); lpi->solstat = 0; /* ensure column size */ SCIP_CALL( ensureColMem(lpi, ncols) ); /* if there are no nonzeros, we have to set up an artificial beg array */ if ( nnonz == 0 ) { SCIP_ALLOC( BMSallocMemoryArray(&lbeg, ncols) ); /* compute column lengths */ for( i = 0; i < ncols; ++i ) { lpi->iccnt[i] = 0; lbeg[i] = 0; } } else { #ifndef NDEBUG /* perform check that no new rows are added - this is forbidden */ int nrows; nrows = QSget_rowcount(lpi->prob); for (i = 0; i < nnonz; ++i) { assert( 0 <= ind[i] && ind[i] < nrows ); assert( val[i] != 0.0 ); } #endif /* compute column lengths */ for( i = 0; i < ncols - 1; ++i ) { lpi->iccnt[i] = beg[i+1] - beg[i]; assert(lpi->iccnt[i] >= 0); } lpi->iccnt[ncols-1] = nnonz - beg[ncols-1]; assert(lpi->iccnt[ncols-1] >= 0); lbeg = (int*) beg; } /* add the columns */ QS_CONDRET( QSadd_cols(lpi->prob, ncols, lpi->iccnt, (int*) lbeg, (int*) ind, (SCIP_Real*) val, (SCIP_Real*) obj, (SCIP_Real*) lb, (SCIP_Real*) ub, (const char**)colnames) ); /* possibly free space */ if ( nnonz == 0 ) { BMSfreeMemoryArray(&lbeg); } return SCIP_OKAY; } /** deletes all columns in the given range from LP */ SCIP_RETCODE SCIPlpiDelCols( SCIP_LPI* lpi, /**< LP interface structure */ int firstcol, /**< first column to be deleted */ int lastcol /**< last column to be deleted */ ) { int len; register int i; assert(lpi != NULL); assert(lpi->prob != NULL); len = lastcol - firstcol +1; lpi->solstat = 0; assert(0 <= firstcol && len > 0 && lastcol < QSget_colcount(lpi->prob)); SCIPdebugMessage("deleting %d columns from QSopt\n", len); SCIP_CALL( ensureColMem(lpi, len) ); for( i = firstcol ; i <= lastcol ; i++ ) lpi->iccnt[i-firstcol] = i; QS_CONDRET( QSdelete_cols(lpi->prob, len, lpi->iccnt) ); return SCIP_OKAY; } /** deletes columns from SCIP_LP; the new position of a column must not be greater that its old position */ SCIP_RETCODE SCIPlpiDelColset( SCIP_LPI* lpi, /**< LP interface structure */ int* dstat /**< deletion status of columns * input: 1 if column should be deleted, 0 if not * output: new position of column, -1 if column was deleted */ ) { int ncols; int ccnt; register int i; assert(lpi != NULL); assert(lpi->prob != NULL); assert(dstat != NULL); ncols = QSget_colcount(lpi->prob); lpi->solstat = 0; SCIPdebugMessage("deleting a column set from QSopt\n"); QS_CONDRET( QSdelete_setcols(lpi->prob,dstat) ); for( i=0, ccnt=0; i < ncols; i++ ) { if( dstat[i] ) dstat[i] = -1; else dstat[i] = ccnt++; } return SCIP_OKAY; } /** adds rows to the LP */ SCIP_RETCODE SCIPlpiAddRows( SCIP_LPI* lpi, /**< LP interface structure */ int nrows, /**< number of rows to be added */ const SCIP_Real* lhs, /**< left hand sides of new rows */ const SCIP_Real* rhs, /**< right hand sides of new rows */ char** rownames, /**< row names, or NULL */ int nnonz, /**< number of nonzero elements to be added to the constraint matrix */ const int* beg, /**< start index of each row in ind- and val-array, or NULL if nnonz == 0 */ const int* ind, /**< column indices of constraint matrix entries, or NULL if nnonz == 0 */ const SCIP_Real* val /**< values of constraint matrix entries, or NULL if nnonz == 0 */ ) { register int i; assert( lpi != NULL ); assert( lpi->prob != NULL ); assert( nrows >= 0 ); assert(lhs != NULL); assert(rhs != NULL); lpi->solstat = 0; SCIPdebugMessage("adding %d rows with %d nonzeros to QSopt\n", nrows, nnonz); if ( nrows <= 0 ) return SCIP_OKAY; /* add rows with no matrix, and then the columns, first ensure space */ SCIP_CALL( ensureRowMem(lpi, nrows) ); /* convert lhs/rhs into sen/rhs/range tuples */ SCIP_CALL( convertSides(lpi, nrows, lhs, rhs) ); /* compute row count */ if( nnonz > 0 ) { assert(beg != NULL); assert(ind != NULL); assert(val != NULL); #ifndef NDEBUG { /* perform check that no new cols are added - this is forbidden */ int ncols; ncols = QSget_colcount(lpi->prob); for (i = 0; i < nnonz; ++i) { assert( val[i] != 0.0 ); assert( 0 <= ind[i] && ind[i] < ncols ); } } #endif for( i = 0 ; i < nrows -1 ; i++ ) { lpi->ircnt[i] = beg[i+1] - beg[i]; assert(lpi->ircnt[i] >= 0); } assert( nrows > 0 ); lpi->ircnt[nrows-1] = nnonz - beg[nrows-1]; assert(lpi->ircnt[nrows-1] >= 0); /* now we add the rows */ QS_CONDRET( QSadd_ranged_rows(lpi->prob, nrows, lpi->ircnt, (int*) beg, (int*) ind, (SCIP_Real*) val, lpi->irhs, lpi->isen, lpi->irng, (const char**)rownames) ); } else { for( i = 0; i < nrows -1; ++i ) { lpi->ircnt[i] = 0; lpi->irbeg[i] = 0; } /* now we add the rows */ QS_CONDRET( QSadd_ranged_rows(lpi->prob, nrows, lpi->ircnt, lpi->irbeg, (int*) ind, (SCIP_Real*) val, lpi->irhs, lpi->isen, lpi->irng, (const char**)rownames) ); } return SCIP_OKAY; } /** gets column names */ SCIP_RETCODE SCIPlpiGetColNames( SCIP_LPI* lpi, /**< LP interface structure */ int firstcol, /**< first column to get name from LP */ int lastcol, /**< last column to get name from LP */ char** colnames, /**< pointers to column names (of size at least lastcol-firstcol+1) or NULL if namestoragesize is zero */ char* namestorage, /**< storage for col names or NULL if namestoragesize is zero */ int namestoragesize, /**< size of namestorage (if 0, storageleft returns the storage needed) */ int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */ ) { char** cnames; char* s; int ncols; int rval; int j; int sizeleft; assert(lpi != NULL); assert(lpi->prob != NULL); assert(colnames != NULL || namestoragesize == 0); assert(namestorage != NULL || namestoragesize == 0); assert(namestoragesize >= 0); assert(storageleft != NULL); assert(0 <= firstcol && firstcol <= lastcol && lastcol < QSget_colcount(lpi->prob)); SCIPdebugMessage("getting column names %d to %d\n", firstcol, lastcol); ncols = QSget_colcount(lpi->prob); SCIP_ALLOC( BMSallocMemoryArray(&cnames, ncols) ); rval = QSget_colnames(lpi->prob, cnames); QS_ERROR(rval, "failed getting column names"); /* copy column names */ s = namestorage; sizeleft = namestoragesize; for( j = firstcol; j <= lastcol; ++j ) { const char* t; assert( s != NULL ); t = cnames[j]; if( colnames != NULL ) colnames[j-firstcol] = s; while( *t != '\0' ) { if( sizeleft > 0 ) *(s++) = *(t++); --sizeleft; } *(s++) = '\0'; } *storageleft = sizeleft; /* free space */ for( j = 0; j < ncols; ++j ) free(cnames[j]); return SCIP_OKAY; } /** gets row names */ SCIP_RETCODE SCIPlpiGetRowNames( SCIP_LPI* lpi, /**< LP interface structure */ int firstrow, /**< first row to get name from LP */ int lastrow, /**< last row to get name from LP */ char** rownames, /**< pointers to row names (of size at least lastrow-firstrow+1) or NULL if namestoragesize is zero */ char* namestorage, /**< storage for row names or NULL if namestoragesize is zero */ int namestoragesize, /**< size of namestorage (if 0, -storageleft returns the storage needed) */ int* storageleft /**< amount of storage left (if < 0 the namestorage was not big enough) or NULL if namestoragesize is zero */ ) { char** rnames; char* s; int nrows; int rval; int i; int sizeleft; assert(lpi != NULL); assert(lpi->prob != NULL); assert(rownames != NULL || namestoragesize == 0); assert(namestorage != NULL || namestoragesize == 0); assert(namestoragesize >= 0); assert(storageleft != NULL); assert(0 <= firstrow && firstrow <= lastrow && lastrow < QSget_rowcount(lpi->prob)); SCIPdebugMessage("getting row names %d to %d\n", firstrow, lastrow); nrows = QSget_rowcount(lpi->prob); SCIP_ALLOC( BMSallocMemoryArray(&rnames, nrows) ); rval = QSget_rownames(lpi->prob, rnames); QS_ERROR(rval, "failed getting row names"); s = namestorage; sizeleft = namestoragesize; for( i = firstrow; i <= lastrow; ++i ) { const char* t; assert( s != NULL ); t = rnames[i]; if( rownames != NULL ) rownames[i-firstrow] = s; while( *t != '\0' ) { if( sizeleft > 0 ) *(s++) = *(t++); --sizeleft; } *(s++) = '\0'; } *storageleft = sizeleft; /* free space */ for( i = 0; i < nrows; ++i ) free(rnames[i]); return SCIP_OKAY; } /** deletes all rows in the given range from LP */ SCIP_RETCODE SCIPlpiDelRows( SCIP_LPI* lpi, /**< LP interface structure */ int firstrow, /**< first row to be deleted */ int lastrow /**< last row to be deleted */ ) { const int len = lastrow - firstrow +1; register int i; assert(lpi != NULL); assert(lpi->prob != NULL); lpi->solstat = 0; assert(0 <= firstrow && len > 0 && lastrow < QSget_rowcount (lpi->prob)); SCIPdebugMessage("deleting %d rows from QSopt\n", len); SCIP_CALL( ensureRowMem(lpi, len) ); for( i = firstrow; i <= lastrow; i++ ) lpi->ircnt[i-firstrow] = i; QS_CONDRET( QSdelete_rows(lpi->prob, len, lpi->ircnt) ); return SCIP_OKAY; } /** deletes rows from SCIP_LP; the new position of a row must not be greater that its old position */ SCIP_RETCODE SCIPlpiDelRowset( SCIP_LPI* lpi, /**< LP interface structure */ int* dstat /**< deletion status of rows * input: 1 if row should be deleted, 0 if not * output: new position of row, -1 if row was deleted */ ) { int nrows; int ccnt; int ndel = 0; register int i; assert(lpi != NULL); assert(lpi->prob != NULL); nrows = QSget_rowcount(lpi->prob); lpi->solstat = 0; for( i = 0; i < nrows; ++i ) { if( dstat[i] == 1 ) ndel++; } SCIPdebugMessage("deleting a row set from QSopt (%d)\n", ndel); QS_CONDRET( QSdelete_setrows(lpi->prob,dstat) ); for( i=0, ccnt=0; i < nrows; i++ ) { if( dstat[i] ) dstat[i] = -1; else dstat[i] = ccnt++; } return SCIP_OKAY; } /** clears the whole LP */ SCIP_RETCODE SCIPlpiClear( SCIP_LPI* lpi /**< LP interface structure */ ) { char savename[1024]; char* name; int objsen; assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("clearing QSopt LP\n"); lpi->solstat = 0; /* save sense and name of problem */ QS_CONDRET( QSget_objsense(lpi->prob, &objsen) ); name = QSget_probname(lpi->prob); (void)strncpy(savename, name, 1023); name[1023] = '\0'; QSfree_prob(lpi->prob); lpi->prob = QScreate_prob(savename, objsen); return SCIP_OKAY; } /** changes lower and upper bounds of columns */ SCIP_RETCODE SCIPlpiChgBounds( SCIP_LPI* lpi, /**< LP interface structure */ int ncols, /**< number of columns to change bounds for */ const int* ind, /**< column indices or NULL if ncols is zero */ const SCIP_Real* lb, /**< values for the new lower bounds or NULL if ncols is zero */ const SCIP_Real* ub /**< values for the new upper bounds or NULL if ncols is zero */ ) { register int i; assert(lpi != NULL); assert(lpi->prob != NULL); assert(ncols == 0 || (ind != NULL && lb != NULL && ub != NULL)); if( ncols <= 0 ) return SCIP_OKAY; lpi->solstat = 0; SCIPdebugMessage("changing %d bounds in QSopt\n", ncols); for (i = 0; i < ncols; ++i) { SCIPdebugPrintf(" col %d: [%g,%g]\n", ind[i], lb[i], ub[i]); if ( SCIPlpiIsInfinity(lpi, lb[i]) ) { SCIPerrorMessage("LP Error: fixing lower bound for variable %d to infinity.\n", ind[i]); return SCIP_LPERROR; } if ( SCIPlpiIsInfinity(lpi, -ub[i]) ) { SCIPerrorMessage("LP Error: fixing upper bound for variable %d to -infinity.\n", ind[i]); return SCIP_LPERROR; } } SCIP_CALL(ensureColMem(lpi, ncols)); for( i = 0; i < ncols; ++i ) lpi->iccha[i] = 'L'; QS_CONDRET( QSchange_bounds(lpi->prob, ncols, (int*) ind, lpi->iccha, (SCIP_Real*) lb) ); for( i = 0; i < ncols; ++i ) lpi->iccha[i] = 'U'; QS_CONDRET( QSchange_bounds(lpi->prob, ncols, (int*) ind, lpi->iccha, (SCIP_Real*) ub) ); return SCIP_OKAY; } /** changes left and right hand sides of rows */ SCIP_RETCODE SCIPlpiChgSides( SCIP_LPI* lpi, /**< LP interface structure */ int nrows, /**< number of rows to change sides for */ const int* ind, /**< row indices */ const SCIP_Real* lhs, /**< new values for left hand sides */ const SCIP_Real* rhs /**< new values for right hand sides */ ) { register int i; assert(lpi != NULL); assert(lpi->prob != NULL); assert(ind != NULL); if( nrows <= 0 ) return SCIP_OKAY; lpi->solstat = 0; SCIPdebugMessage("changing %d sides in QSopt\n", nrows); SCIP_CALL( ensureRowMem(lpi, nrows) ); /* convert lhs/rhs into sen/rhs/range tuples */ SCIP_CALL( convertSides(lpi, nrows, lhs, rhs) ); /* now we change all rows */ for( i = 0; i < nrows; ++i ) { QS_CONDRET( QSchange_sense(lpi->prob, ind[i], lpi->isen[i]) ); QS_CONDRET( QSchange_rhscoef(lpi->prob, ind[i], lpi->irhs[i]) ); if( lpi->isen[i] == 'R' ) { QS_CONDRET( QSchange_range(lpi->prob, ind[i], lpi->irng[i]) ); } } return SCIP_OKAY; } /** changes a single coefficient */ SCIP_RETCODE SCIPlpiChgCoef( SCIP_LPI* lpi, /**< LP interface structure */ int row, /**< row number of coefficient to change */ int col, /**< column number of coefficient to change */ SCIP_Real newval /**< new value of coefficient */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); lpi->solstat = 0; SCIPdebugMessage("changing coefficient row %d, column %d in QSopt to %g\n", row, col, newval); QS_CONDRET( QSchange_coef(lpi->prob, row, col, newval) ); return SCIP_OKAY; } /** changes the objective sense */ SCIP_RETCODE SCIPlpiChgObjsen( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_OBJSEN objsen /**< new objective sense */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); lpi->solstat = 0; SCIPdebugMessage("changing objective sense in QSopt to %d\n", objsen); /* set sense */ if( objsen == SCIP_OBJSEN_MAXIMIZE ) { QS_CONDRET( QSchange_objsense(lpi->prob, QS_MAX) ); } else { QS_CONDRET( QSchange_objsense(lpi->prob, QS_MIN) ); } return SCIP_OKAY; } /** changes objective values of columns in the LP */ SCIP_RETCODE SCIPlpiChgObj( SCIP_LPI* lpi, /**< LP interface structure */ int ncols, /**< number of columns to change objective value for */ const int* ind, /**< column indices to change objective value for */ const SCIP_Real* obj /**< new objective values for columns */ ) { register int i; assert(lpi != NULL); assert(lpi->prob != NULL); assert(ind != NULL); assert(obj != NULL); lpi->solstat = 0; SCIPdebugMessage("changing %d objective values in QSopt\n", ncols); for( i = 0; i < ncols; ++i ) { QS_CONDRET( QSchange_objcoef(lpi->prob, ind[i], obj[i]) ); } return SCIP_OKAY; } /** multiplies a row with a non-zero scalar; for negative scalars, the row's sense is switched accordingly */ SCIP_RETCODE SCIPlpiScaleRow( SCIP_LPI* lpi, /**< LP interface structure */ int row, /**< row number to scale */ SCIP_Real scaleval /**< scaling multiplier */ ) { register int i; int rowlist[1]; int* rowcnt = NULL, *rowbeg = NULL, *rowind = NULL; double* rowval = NULL, *rhs = NULL, *range = NULL; char* sense = NULL; int rval; assert(lpi != NULL); assert(lpi->prob != NULL); lpi->solstat = 0; SCIPdebugMessage("scaling row %d with factor %g in QSopt\n", row, scaleval); rowlist[0] = row; /* get row */ rval = QSget_ranged_rows_list(lpi->prob, 1, rowlist, &rowcnt, &rowbeg, &rowind, &rowval, &rhs, &sense, &range, 0); QS_TESTG(rval, CLEANUP, " "); /* change all coefficients in the constraint */ for( i = 0; i < rowcnt[0]; ++i ) { rval = QSchange_coef(lpi->prob, row, rowind[i], rowval[i] * scaleval); QS_TESTG(rval, CLEANUP, " "); } /* if we have a positive scalar, we just scale rhs and range */ if( scaleval >= 0 ) { rval = QSchange_rhscoef(lpi->prob, row, rhs[0] * scaleval); QS_TESTG(rval, CLEANUP, " "); if( sense[0] == 'R' ) { rval = QSchange_range(lpi->prob, row, range[0] * scaleval); QS_TESTG(rval, CLEANUP, " "); } } /* otherwise, we must change everything */ else { switch( sense[0] ) { case 'E': rval = QSchange_rhscoef(lpi->prob, row, rhs[0]*scaleval); QS_TESTG(rval, CLEANUP, " "); break; case 'L': rval = QSchange_rhscoef(lpi->prob, row, rhs[0]*scaleval); QS_TESTG(rval, CLEANUP, " "); rval = QSchange_sense(lpi->prob, row, 'G'); QS_TESTG(rval, CLEANUP, " "); break; case 'G': rval = QSchange_rhscoef(lpi->prob, row, rhs[0]*scaleval); QS_TESTG(rval, CLEANUP, " "); rval = QSchange_sense(lpi->prob, row, 'L'); QS_TESTG(rval, CLEANUP, " "); break; case 'R': rhs[0] = (rhs[0] + range[0]) * scaleval; range[0] = fabs(scaleval) * range[0]; rval = QSchange_rhscoef(lpi->prob, row, rhs[0]); QS_TESTG(rval, CLEANUP, " "); rval = QSchange_range(lpi->prob, row, range[0]); QS_TESTG(rval, CLEANUP, " "); break; default: SCIPerrorMessage("Impossible! received sense %c (not E L G R)", sense[0]); rval = 1; goto CLEANUP; } } /* now we must free all received arrays */ /* ending */ CLEANUP: if( rowcnt != NULL ) QSfree(rowcnt); if( rowbeg != NULL ) QSfree(rowbeg); if( rowind != NULL ) QSfree(rowind); if( rowval != NULL ) QSfree(rowval); if( rhs != NULL ) QSfree(rhs); if( sense != NULL ) QSfree(sense); if( range != NULL ) QSfree(range); QS_RETURN(rval); } /** multiplies a column with a non-zero scalar; the objective value is multiplied with the scalar, and the bounds * are divided by the scalar; for negative scalars, the column's bounds are switched */ SCIP_RETCODE SCIPlpiScaleCol( SCIP_LPI* lpi, /**< LP interface structure */ int col, /**< column number to scale */ SCIP_Real scaleval /**< scaling multiplier */ ) { register int i; int collist[1]; int* colcnt=0; int* colbeg=0; int* colind=0; double* colval=0; double* lb=0; double* ub=0; double* obj=0; int rval; assert(lpi != NULL); assert(lpi->prob != NULL); lpi->solstat = 0; SCIPdebugMessage("scaling column %d with factor %g in QSopt\n", col, scaleval); /* get the column */ collist[0] = col; rval = QSget_columns_list(lpi->prob, 1, collist, &colcnt, &colbeg, &colind, &colval, &obj, &lb, &ub, 0); QS_TESTG(rval, CLEANUP, " "); /* scale column coefficients */ for( i = 0; i < colcnt[0]; ++i ) { rval = QSchange_coef(lpi->prob, colind[i], col, colval[i]*scaleval); QS_TESTG(rval, CLEANUP, " "); } /* scale objective value */ rval = QSchange_objcoef(lpi->prob, col, obj[0]*scaleval); QS_TESTG(rval, CLEANUP, " "); /* scale column bounds */ if( scaleval < 0 ) { scaleval = -scaleval; obj[0] = lb[0]; lb[0] = -ub[0]; ub[0] = -obj[0]; } if( lb[0] > -QS_MAXDOUBLE ) lb[0] *= scaleval; if( ub[0] < QS_MAXDOUBLE ) ub[0] *= scaleval; if( lb[0] < -QS_MAXDOUBLE ) lb[0] = -QS_MAXDOUBLE; if( ub[0] > QS_MAXDOUBLE ) ub[0] = QS_MAXDOUBLE; rval = QSchange_bound(lpi->prob, col, 'L', lb[0]); QS_TESTG(rval, CLEANUP, " "); rval = QSchange_bound(lpi->prob, col, 'U', ub[0]); QS_TESTG(rval, CLEANUP, " "); /* ending */ CLEANUP: if( colcnt != NULL ) QSfree(colcnt); if( colbeg != NULL ) QSfree(colbeg); if( colind != NULL ) QSfree(colind); if( colval != NULL ) QSfree(colval); if( obj != NULL ) QSfree(obj); if( lb != NULL ) QSfree(lb); if( ub != NULL ) QSfree(ub); QS_RETURN(rval); } /**@} */ /* * Data Accessing Methods */ /**@name Data Accessing Methods */ /**@{ */ /** gets the number of rows in the LP */ SCIP_RETCODE SCIPlpiGetNRows( SCIP_LPI* lpi, /**< LP interface structure */ int* nrows /**< pointer to store the number of rows */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(nrows != NULL); SCIPdebugMessage("getting number of rows\n"); *nrows = QSget_rowcount(lpi->prob); return SCIP_OKAY; } /** gets the number of columns in the LP */ SCIP_RETCODE SCIPlpiGetNCols( SCIP_LPI* lpi, /**< LP interface structure */ int* ncols /**< pointer to store the number of cols */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(ncols != NULL); SCIPdebugMessage("getting number of columns\n"); *ncols = QSget_colcount(lpi->prob); return SCIP_OKAY; } /** gets the number of nonzero elements in the LP constraint matrix */ SCIP_RETCODE SCIPlpiGetNNonz( SCIP_LPI* lpi, /**< LP interface structure */ int* nnonz /**< pointer to store the number of nonzeros */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(nnonz != NULL); SCIPdebugMessage("getting number of columns\n"); *nnonz = QSget_nzcount(lpi->prob); return SCIP_OKAY; } /** gets columns from LP problem object; the arrays have to be large enough to store all values * Either both, lb and ub, have to be NULL, or both have to be non-NULL, * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL. */ SCIP_RETCODE SCIPlpiGetCols( SCIP_LPI* lpi, /**< LP interface structure */ int firstcol, /**< first column to get from LP */ int lastcol, /**< last column to get from LP */ SCIP_Real* lb, /**< buffer to store the lower bound vector, or NULL */ SCIP_Real* ub, /**< buffer to store the upper bound vector, or NULL */ int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */ int* beg, /**< buffer to store start index of each column in ind- and val-array, or NULL */ int* ind, /**< buffer to store row indices of constraint matrix entries, or NULL */ SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */ ) { int len; register int i; double* lval = NULL; double* llb = NULL; double* lub = NULL; int rval; int* lcnt = NULL; int* lbeg = NULL; int* lind = NULL; assert(lpi != NULL); assert(lpi->prob != NULL); assert(0 <= firstcol && firstcol <= lastcol && lastcol < QSget_colcount(lpi->prob)); assert((lb == NULL && ub == NULL) || (lb != NULL && ub != NULL)); assert((nnonz != NULL && beg != NULL && ind != NULL && val != NULL) || (nnonz == NULL && beg == NULL && ind == NULL && val == NULL)); SCIPdebugMessage("getting columns %d to %d\n", firstcol, lastcol); /* build col-list */ len = lastcol - firstcol + 1; assert( len > 0 ); SCIP_CALL( ensureColMem(lpi, len) ); for( i = 0; i < len; ++i ) lpi->iccnt[i] = i + firstcol; /* get data from qsopt */ if ( nnonz != NULL ) rval = QSget_columns_list(lpi->prob, len, lpi->iccnt, &lcnt, &lbeg, &lind, &lval, NULL, lb ? (&llb) : NULL, ub ? (&lub) : NULL, NULL); /*lint !e826*/ else rval = QSget_columns_list(lpi->prob, len, lpi->iccnt, NULL, NULL, NULL, NULL, NULL, lb ? (&llb) : NULL, ub ? (&lub) : NULL, NULL); /*lint !e826*/ QS_TESTG(rval, CLEANUP, " "); /* store in the user-provided data */ if( nnonz != NULL ) { assert(beg != NULL && ind != NULL && val != NULL); /* for lint */ if( lcnt == NULL || lbeg == NULL || lind == NULL || lval == NULL ) { SCIPerrorMessage("QSget_columns_list() failed to allocate memory.\n"); return SCIP_LPERROR; } *nnonz = lbeg[len-1] + lcnt[len-1]; for( i = 0 ; i < len ; i++ ) beg[i] = lbeg[i]; for( i = 0; i < *nnonz; ++i ) { ind[i] = lind[i]; val[i] = lval[i]; } } if( lb != NULL ) { assert( ub != NULL ); /* for lint */ if( llb == NULL || lub == NULL ) /*lint !e774*/ { SCIPerrorMessage("QSget_columns_list() failed to allocate memory.\n"); return SCIP_LPERROR; } for( i = 0; i < len; ++i ) { lb[i] = llb[i]; ub[i] = lub[i]; } } CLEANUP: if( lval != NULL ) QSfree(lval); if( lub != NULL ) /*lint !e831 !e774*/ QSfree(lub); if( llb != NULL ) /*lint !e831 !e774*/ QSfree(llb); if( lind != NULL ) QSfree(lind); if( lbeg != NULL ) QSfree(lbeg); if( lcnt != NULL ) QSfree(lcnt); QS_RETURN(rval); } /** gets rows from LP problem object; the arrays have to be large enough to store all values. * Either both, lhs and rhs, have to be NULL, or both have to be non-NULL, * either nnonz, beg, ind, and val have to be NULL, or all of them have to be non-NULL. */ SCIP_RETCODE SCIPlpiGetRows( SCIP_LPI* lpi, /**< LP interface structure */ int firstrow, /**< first row to get from LP */ int lastrow, /**< last row to get from LP */ SCIP_Real* lhs, /**< buffer to store left hand side vector, or NULL */ SCIP_Real* rhs, /**< buffer to store right hand side vector, or NULL */ int* nnonz, /**< pointer to store the number of nonzero elements returned, or NULL */ int* beg, /**< buffer to store start index of each row in ind- and val-array, or NULL */ int* ind, /**< buffer to store column indices of constraint matrix entries, or NULL */ SCIP_Real* val /**< buffer to store values of constraint matrix entries, or NULL */ ) { const int len = lastrow - firstrow + 1; register int i; double* lval = NULL; double* lrhs = NULL; double* lrng = NULL; int rval; int* lcnt = NULL; int* lbeg = NULL; int* lind = NULL; char* lsense = NULL; assert(lpi != NULL); assert(lpi->prob != NULL); assert(0 <= firstrow && firstrow <= lastrow && lastrow < QSget_rowcount (lpi->prob)); assert((lhs == NULL && rhs == NULL) || (rhs != NULL && lhs != NULL)); assert((nnonz != NULL && beg != NULL && ind != NULL && val != NULL) || (nnonz == NULL && beg == NULL && ind == NULL && val == NULL)); SCIPdebugMessage("getting rows %d to %d\n", firstrow, lastrow); /* build row-list */ SCIP_CALL( ensureRowMem(lpi, len) ); for( i = 0; i < len; ++i ) lpi->ircnt[i] = i + firstrow; /* get data from qsopt */ if ( nnonz != NULL ) rval = QSget_ranged_rows_list(lpi->prob, len, lpi->ircnt, &lcnt, &lbeg, &lind, &lval, rhs ? (&lrhs) : NULL, rhs ? (&lsense) : NULL, rhs ? (&lrng) : NULL, NULL); /*lint !e826*/ else rval = QSget_ranged_rows_list(lpi->prob, len, lpi->ircnt, NULL, NULL, NULL, NULL, rhs ? (&lrhs) : NULL, rhs ? (&lsense) : NULL, rhs ? (&lrng) : NULL, NULL); /*lint !e826*/ QS_TESTG(rval, CLEANUP, " "); /* store in the user-provided data */ if( nnonz != NULL ) { assert( beg != NULL && ind != NULL && val != NULL ); /* for lint */ if( lcnt == NULL || lbeg == NULL || lind == NULL || lval == NULL ) { SCIPerrorMessage("QSget_ranged_rows_list() failed to allocate memory.\n"); return SCIP_LPERROR; } *nnonz = lbeg[len-1] + lcnt[len-1]; for( i = 0 ; i < len; i++ ) beg[i] = lbeg[i]; for( i = 0; i < *nnonz; ++i ) { ind[i] = lind[i]; val[i] = lval[i]; } } if( rhs != NULL ) { if( lrhs == NULL || lrng == NULL || lsense == NULL ) /*lint !e774*/ { SCIPerrorMessage("QSget_ranged_rows_list() failed to allocate memory.\n"); return SCIP_LPERROR; } assert( lhs != NULL ); /* for lint */ for( i = 0; i < len; ++i ) { switch( lsense[i] ) { case 'R': lhs[i] = lrhs[i]; rhs[i] = lrhs[i] + lrng[i]; break; case 'E': lhs[i] = lrhs[i]; rhs[i] = lrhs[i]; break; case 'L': rhs[i] = lrhs[i]; lhs[i] = -QS_MAXDOUBLE; break; case 'G': lhs[i] = lrhs[i]; rhs[i] = QS_MAXDOUBLE; break; default: SCIPerrorMessage("Unknown sense %c from QSopt", lsense[i]); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } } CLEANUP: if( lsense != NULL ) /*lint !e774*/ QSfree(lsense); if( lrng != NULL ) /*lint !e774*/ QSfree(lrng); if( lrhs != NULL ) /*lint !e774*/ QSfree(lrhs); if( lval != NULL ) QSfree(lval); if( lind != NULL ) QSfree(lind); if( lbeg != NULL ) QSfree(lbeg); if( lcnt != NULL ) QSfree(lcnt); QS_RETURN(rval); } /** gets the objective sense of the LP */ SCIP_RETCODE SCIPlpiGetObjsen( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_OBJSEN* objsen /**< pointer to store objective sense */ ) { int sense; assert(lpi != NULL); assert(lpi->prob != NULL); assert( objsen != NULL ); QS_CONDRET( QSget_objsense(lpi->prob, &sense) ); if ( sense == QS_MIN ) *objsen = SCIP_OBJSEN_MINIMIZE; else *objsen = SCIP_OBJSEN_MAXIMIZE; return SCIP_OKAY; } /** gets objective coefficients from LP problem object */ SCIP_RETCODE SCIPlpiGetObj( SCIP_LPI* lpi, /**< LP interface structure */ int firstcol, /**< first column to get objective coefficient for */ int lastcol, /**< last column to get objective coefficient for */ SCIP_Real* vals /**< array to store objective coefficients */ ) { /*lint --e{715}*/ int len; register int i; double* qsoptvals; assert(lpi != NULL); assert(lpi->prob != NULL); assert(vals != NULL); assert(0 <= firstcol && firstcol <= lastcol && lastcol < QSget_colcount (lpi->prob)); SCIPdebugMessage("getting objective values %d to %d\n", firstcol, lastcol); /* build col-list */ len = lastcol - firstcol + 1; SCIP_CALL(ensureColMem(lpi,len)); for( i = 0; i < len; ++i ) lpi->iccnt[i] = i + firstcol; /* get data from qsopt */ /* There seems to be a bug in qsopt: The function QSget_obj_list might return values for slack variables. We * therefore have to use a workarround. */ #ifdef SCIP_DISABLED_CODE QS_CONDRET( QSget_obj_list(lpi->prob, len, lpi->iccnt, vals) ); #endif QS_CONDRET( QSget_columns_list(lpi->prob, len, lpi->iccnt, NULL, NULL, NULL, NULL, &qsoptvals, NULL, NULL, NULL) ); for (i = 0; i < len; ++i) vals[i] = qsoptvals[i]; free( qsoptvals ); return SCIP_OKAY; } /** gets current bounds from LP problem object */ SCIP_RETCODE SCIPlpiGetBounds( SCIP_LPI* lpi, /**< LP interface structure */ int firstcol, /**< first column to get objective value for */ int lastcol, /**< last column to get objective value for */ SCIP_Real* lbs, /**< array to store lower bound values, or NULL */ SCIP_Real* ubs /**< array to store upper bound values, or NULL */ ) { const int len = lastcol - firstcol + 1; register int i; assert(lpi != NULL); assert(lpi->prob != NULL); assert(0 <= firstcol && firstcol <= lastcol&& lastcol < QSget_colcount (lpi->prob)); SCIPdebugMessage("getting bound values %d to %d\n", firstcol, lastcol); /* build col-list */ SCIP_CALL(ensureColMem(lpi,len)); for( i = 0; i < len; ++i ) lpi->iccnt[i] = i + firstcol; /* get data from qsopt */ QS_CONDRET( QSget_bounds_list(lpi->prob, len, lpi->iccnt, lbs, ubs) ); return SCIP_OKAY; } /** gets current row sides from LP problem object */ SCIP_RETCODE SCIPlpiGetSides( SCIP_LPI* lpi, /**< LP interface structure */ int firstrow, /**< first row to get sides for */ int lastrow, /**< last row to get sides for */ SCIP_Real* lhss, /**< array to store left hand side values, or NULL */ SCIP_Real* rhss /**< array to store right hand side values, or NULL */ ) { const int len = lastrow - firstrow + 1; register int i; double* lrhs=0, *lrng=0; int rval; char* lsense=0; assert(lpi != NULL); assert(lpi->prob != NULL); assert(0 <= firstrow && firstrow <= lastrow && lastrow < QSget_rowcount (lpi->prob)); assert(rhss != NULL); assert(lhss != NULL); SCIPdebugMessage("getting row sides %d to %d\n", firstrow, lastrow); /* build row-list */ SCIP_CALL( ensureRowMem(lpi, len) ); for( i = 0; i < len; ++i ) lpi->ircnt[i] = i + firstrow; /* get data from qsopt */ rval = QSget_ranged_rows_list(lpi->prob, len, lpi->ircnt, 0, 0, 0, 0, &lrhs, &lsense, &lrng, 0); QS_TESTG(rval, CLEANUP, " "); /* store in the user-provided data */ for( i = 0; i < len; ++i ) { switch( lsense[i] ) { case 'R': lhss[i] = lrhs[i]; rhss[i] = lrhs[i] + lrng[i]; break; case 'E': lhss[i] = rhss[i] = lrhs[i]; break; case 'L': rhss[i] = lrhs[i]; lhss[i] = -QS_MAXDOUBLE; break; case 'G': lhss[i] = lrhs[i]; rhss[i] = QS_MAXDOUBLE; break; default: SCIPerrorMessage("Unknown sense %c from QSopt", lsense[i]); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } CLEANUP: if( lsense != NULL ) QSfree(lsense); if( lrng != NULL ) QSfree(lrng); if( lrhs != NULL ) QSfree(lrhs); QS_RETURN(rval); } /** gets a single coefficient */ SCIP_RETCODE SCIPlpiGetCoef( SCIP_LPI* lpi, /**< LP interface structure */ int row, /**< row number of coefficient */ int col, /**< column number of coefficient */ SCIP_Real* val /**< pointer to store the value of the coefficient */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(val != NULL); SCIPdebugMessage("getting coefficient of row %d col %d\n", row, col); QS_CONDRET( QSget_coef(lpi->prob, row, col, val) ); return SCIP_OKAY; } /**@} */ /* * Solving Methods */ /**@name Solving Methods */ /**@{ */ /** calls primal simplex to solve the LP */ SCIP_RETCODE SCIPlpiSolvePrimal( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("calling QSopt primal simplex: %d cols, %d rows, %d nz\n", QSget_colcount(lpi->prob), QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob)); QS_CONDRET( QSopt_primal(lpi->prob, &(lpi->solstat)) ); lpi->algo = LPI_QSOPT_ALGO_PRIMAL; return SCIP_OKAY; } /** calls dual simplex to solve the LP */ SCIP_RETCODE SCIPlpiSolveDual( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("calling QSopt dual simplex: %d cols, %d rows, %d nz\n", QSget_colcount(lpi->prob), QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob)); QS_CONDRET( QSopt_dual(lpi->prob, &(lpi->solstat)) ); lpi->algo = LPI_QSOPT_ALGO_DUAL; return SCIP_OKAY; } /** calls barrier or interior point algorithm to solve the LP with crossover to simplex basis */ SCIP_RETCODE SCIPlpiSolveBarrier( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Bool crossover /**< perform crossover */ ) { /*lint --e{715}*/ assert(lpi != NULL); assert(lpi->prob != NULL); SCIP_UNUSED( crossover ); return SCIPlpiSolveDual(lpi); } /** start strong branching - call before any strong branching */ SCIP_RETCODE SCIPlpiStartStrongbranch( SCIP_LPI* lpi /**< LP interface structure */ ) { /*lint --e{715}*/ assert(lpi != NULL); assert(lpi->prob != NULL); /* currently do nothing */ return SCIP_OKAY; } /** end strong branching - call after any strong branching */ SCIP_RETCODE SCIPlpiEndStrongbranch( SCIP_LPI* lpi /**< LP interface structure */ ) { /*lint --e{715}*/ assert(lpi != NULL); assert(lpi->prob != NULL); /* currently do nothing */ return SCIP_OKAY; } /** performs strong branching iterations on one @b fractional candidate */ SCIP_RETCODE SCIPlpiStrongbranchFrac( SCIP_LPI* lpi, /**< LP interface structure */ int col, /**< column to apply strong branching on */ SCIP_Real psol, /**< fractional current primal solution value of column */ int itlim, /**< iteration limit for strong branchings */ SCIP_Real* down, /**< stores dual bound after branching column down */ SCIP_Real* up, /**< stores dual bound after branching column up */ SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound; * otherwise, it can only be used as an estimate value */ SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound; * otherwise, it can only be used as an estimate value */ int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */ ) { int nit; assert(lpi != NULL); assert(lpi->prob != NULL); assert(down != NULL); assert(up != NULL); assert(downvalid != NULL); assert(upvalid != NULL); SCIPdebugMessage("calling QSopt strong branching on variable %d with fractional value (%d it lim)\n", col, itlim); /* results of QSopt are valid in any case */ *downvalid = TRUE; *upvalid = TRUE; assert( ! EPSISINT(psol, FEASTOL) ); /* call QSopt */ QS_CONDRET( QSopt_strongbranch(lpi->prob, 1, &col, &psol, down, up, itlim, QS_MAXDOUBLE) ); QS_CONDRET( QSget_itcnt(lpi->prob, 0, 0, 0, 0, &nit) ); if( iter ) *iter = nit - lpi->previt; lpi->previt = nit; return SCIP_OKAY; } /** performs strong branching iterations on given @b fractional candidates */ SCIP_RETCODE SCIPlpiStrongbranchesFrac( SCIP_LPI* lpi, /**< LP interface structure */ int* cols, /**< columns to apply strong branching on */ int ncols, /**< number of columns */ SCIP_Real* psols, /**< fractional current primal solution values of columns */ int itlim, /**< iteration limit for strong branchings */ SCIP_Real* down, /**< stores dual bounds after branching columns down */ SCIP_Real* up, /**< stores dual bounds after branching columns up */ SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds; * otherwise, they can only be used as an estimate values */ SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds; * otherwise, they can only be used as an estimate values */ int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */ ) { int nit; int j; assert(lpi != NULL); assert(lpi->prob != NULL); assert(cols != NULL); assert(psols != NULL); assert(down != NULL); assert(up != NULL); assert(downvalid != NULL); assert(upvalid != NULL); SCIPdebugMessage("calling QSopt strong branching on %d variables with fractional value (%d it lim)\n", ncols, itlim); /* results of QSopt are valid in any case */ for( j = 0; j < ncols; ++j ) { downvalid[j] = TRUE; upvalid[j] = TRUE; assert( ! EPSISINT(psols[j], FEASTOL) ); } /* call QSopt */ QS_CONDRET( QSopt_strongbranch(lpi->prob, ncols, cols, psols, down, up, itlim, QS_MAXDOUBLE) ); QS_CONDRET( QSget_itcnt(lpi->prob, 0, 0, 0, 0, &nit) ); if( iter ) *iter = nit - lpi->previt; lpi->previt = nit; return SCIP_OKAY; } /** performs strong branching iterations on one candidate with @b integral value */ SCIP_RETCODE SCIPlpiStrongbranchInt( SCIP_LPI* lpi, /**< LP interface structure */ int col, /**< column to apply strong branching on */ SCIP_Real psol, /**< current integral primal solution value of column */ int itlim, /**< iteration limit for strong branchings */ SCIP_Real* down, /**< stores dual bound after branching column down */ SCIP_Real* up, /**< stores dual bound after branching column up */ SCIP_Bool* downvalid, /**< stores whether the returned down value is a valid dual bound; * otherwise, it can only be used as an estimate value */ SCIP_Bool* upvalid, /**< stores whether the returned up value is a valid dual bound; * otherwise, it can only be used as an estimate value */ int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */ ) { SCIP_Real objval; assert(lpi != NULL); assert(lpi->prob != NULL); assert(down != NULL); assert(up != NULL); assert(downvalid != NULL); assert(upvalid != NULL); SCIPdebugMessage("calling QSopt strong branching on variable %d with integral value (%d it lim)\n", col, itlim); assert(EPSISINT(psol, FEASTOL)); /* QSopt cannot directly strong branch on integral values! We thus return the current objective * value for both cases. Could also implement a manual search as in lpi_cpx.c */ QS_CONDRET( QSget_objval(lpi->prob, &objval) ); *down = objval; *up = objval; *downvalid = TRUE; *upvalid = TRUE; if( iter ) *iter = 0; return SCIP_OKAY; } /** performs strong branching iterations on given candidates with @b integral values */ SCIP_RETCODE SCIPlpiStrongbranchesInt( SCIP_LPI* lpi, /**< LP interface structure */ int* cols, /**< columns to apply strong branching on */ int ncols, /**< number of columns */ SCIP_Real* psols, /**< current integral primal solution values of columns */ int itlim, /**< iteration limit for strong branchings */ SCIP_Real* down, /**< stores dual bounds after branching columns down */ SCIP_Real* up, /**< stores dual bounds after branching columns up */ SCIP_Bool* downvalid, /**< stores whether the returned down values are valid dual bounds; * otherwise, they can only be used as an estimate values */ SCIP_Bool* upvalid, /**< stores whether the returned up values are a valid dual bounds; * otherwise, they can only be used as an estimate values */ int* iter /**< stores total number of strong branching iterations, or -1; may be NULL */ ) { /*lint --e{715}*/ SCIP_Real objval; int j; assert(lpi != NULL); assert(lpi->prob != NULL); assert(down != NULL); assert(up != NULL); assert(downvalid != NULL); assert(upvalid != NULL); SCIP_UNUSED( cols ); SCIPdebugMessage("calling QSopt strong branching on %d variables with integral value (%d it lim)\n", ncols, itlim); /* QSopt cannot directly strong branch on integral values! We thus return the current objective * value for all cases. Could also implement a manual search as in lpi_cpx.c. */ QS_CONDRET( QSget_objval(lpi->prob, &objval) ); for( j = 0; j < ncols; ++j ) { assert(EPSISINT(psols[j], FEASTOL)); down[j] = objval; up[j] = objval; downvalid[j] = TRUE; upvalid[j] = TRUE; } if( iter ) *iter = 0; return SCIP_OKAY; } /**@} */ /* * Solution Information Methods */ /**@name Solution Information Methods */ /**@{ */ /** returns whether a solve method was called after the last modification of the LP */ SCIP_Bool SCIPlpiWasSolved( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi!=NULL); assert(lpi->prob!=NULL); return (lpi->solstat != 0 && lpi->solstat != QS_LP_MODIFIED); } /** gets information about primal and dual feasibility of the current LP solution * * The feasibility information is with respect to the last solving call and it is only relevant if SCIPlpiWasSolved() * returns true. If the LP is changed, this information might be invalidated. * * Note that @a primalfeasible and @a dualfeasible should only return true if the solver has proved the respective LP to * be feasible. Thus, the return values should be equal to the values of SCIPlpiIsPrimalFeasible() and * SCIPlpiIsDualFeasible(), respectively. Note that if feasibility cannot be proved, they should return false (even if * the problem might actually be feasible). */ SCIP_RETCODE SCIPlpiGetSolFeasibility( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Bool* primalfeasible, /**< pointer to store primal feasibility status */ SCIP_Bool* dualfeasible /**< pointer to store dual feasibility status */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(lpi->solstat != 0); assert(primalfeasible != NULL); assert(dualfeasible != NULL); SCIPdebugMessage("getting solution feasibility\n"); if( lpi->solstat == QS_LP_OPTIMAL || (lpi->algo == LPI_QSOPT_ALGO_PRIMAL && lpi->solstat == QS_LP_UNBOUNDED) ) *primalfeasible = TRUE; else *primalfeasible = FALSE; if( lpi->solstat == QS_LP_OPTIMAL || (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE) || lpi->solstat == QS_LP_OBJ_LIMIT ) *dualfeasible = TRUE; else *dualfeasible = FALSE; return SCIP_OKAY; } /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point); * this does not necessarily mean, that the solver knows and can return the primal ray */ SCIP_Bool SCIPlpiExistsPrimalRay( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking primal ray existence\n"); return (lpi->solstat == QS_LP_UNBOUNDED); } /** returns TRUE iff LP is proven to have a primal unbounded ray (but not necessary a primal feasible point), * and the solver knows and can return the primal ray */ SCIP_Bool SCIPlpiHasPrimalRay( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for primal ray\n"); /* the current version of QSopt cannot give a primal certificate of unboundedness */ return FALSE; } /** returns TRUE iff LP is proven to be primal unbounded */ SCIP_Bool SCIPlpiIsPrimalUnbounded( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for primal unboundedness\n"); return (lpi->algo == LPI_QSOPT_ALGO_PRIMAL && lpi->solstat == QS_LP_UNBOUNDED); } /** returns TRUE iff LP is proven to be primal infeasible */ SCIP_Bool SCIPlpiIsPrimalInfeasible( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for primal infeasibility\n"); (void) QSget_status(lpi->prob, &(lpi->solstat)); return (lpi->solstat == QS_LP_INFEASIBLE); } /** returns TRUE iff LP is proven to be primal feasible */ SCIP_Bool SCIPlpiIsPrimalFeasible( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for primal feasibility\n"); return (lpi->solstat == QS_LP_OPTIMAL || lpi->solstat == QS_LP_UNBOUNDED); } /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point); * this does not necessarily mean, that the solver knows and can return the dual ray */ SCIP_Bool SCIPlpiExistsDualRay( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for dual ray availability\n"); return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE); } /** returns TRUE iff LP is proven to have a dual unbounded ray (but not necessary a dual feasible point), * and the solver knows and can return the dual ray */ SCIP_Bool SCIPlpiHasDualRay( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for dual ray availability\n"); return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE); } /** returns TRUE iff LP is dual unbounded */ SCIP_Bool SCIPlpiIsDualUnbounded( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for dual unboundedness\n"); return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE); } /** returns TRUE iff LP is dual infeasible */ SCIP_Bool SCIPlpiIsDualInfeasible( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for dual infeasibility\n"); return (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE); } /** returns TRUE iff LP is proven to be dual feasible */ SCIP_Bool SCIPlpiIsDualFeasible( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for dual feasibility\n"); return ( lpi->solstat == QS_LP_OPTIMAL || (lpi->algo == LPI_QSOPT_ALGO_DUAL && lpi->solstat == QS_LP_INFEASIBLE) || lpi->solstat == QS_LP_OBJ_LIMIT ); } /** returns TRUE iff LP was solved to optimality */ SCIP_Bool SCIPlpiIsOptimal( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for optimality\n"); return (lpi->solstat == QS_LP_OPTIMAL); } /** returns TRUE iff current LP solution is stable * * This function should return true if the solution is reliable, i.e., feasible and optimal (or proven * infeasible/unbounded) with respect to the original problem. The optimality status might be with respect to a scaled * version of the problem, but the solution might not be feasible to the unscaled original problem; in this case, * SCIPlpiIsStable() should return false. */ SCIP_Bool SCIPlpiIsStable( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for numerical stability\n"); return (lpi->solstat != QS_LP_NUMERR); } /** returns TRUE iff the objective limit was reached */ SCIP_Bool SCIPlpiIsObjlimExc( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for objective limit exceeded\n"); return (lpi->solstat == QS_LP_OBJ_LIMIT); } /** returns TRUE iff the iteration limit was reached */ SCIP_Bool SCIPlpiIsIterlimExc( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for iteration limit exceeded\n"); return (lpi->solstat == QS_LP_ITER_LIMIT); } /** returns TRUE iff the time limit was reached */ SCIP_Bool SCIPlpiIsTimelimExc( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("checking for time limit exceeded\n"); return (lpi->solstat == QS_LP_TIME_LIMIT); } /** returns the internal solution status of the solver */ int SCIPlpiGetInternalStatus( SCIP_LPI* lpi /**< LP interface structure */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("getting internal solution status\n"); return lpi->solstat; } /** tries to reset the internal status of the LP solver in order to ignore an instability of the last solving call */ SCIP_RETCODE SCIPlpiIgnoreInstability( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Bool* success /**< pointer to store, whether the instability could be ignored */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(success != NULL); SCIPdebugMessage("ignore instability (will fail)\n"); /* it seems that in QSopt this does not make much sense */ *success = FALSE; return SCIP_OKAY; } /** gets objective value of solution */ SCIP_RETCODE SCIPlpiGetObjval( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Real* objval /**< stores the objective value */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(objval != NULL); SCIPdebugMessage("getting solution's objective value\n"); QS_CONDRET( QSget_objval(lpi->prob, objval) ); return SCIP_OKAY; } /** gets primal and dual solution vectors for feasible LPs * * Before calling this function, the caller must ensure that the LP has been solved to optimality, i.e., that * SCIPlpiIsOptimal() returns true. */ SCIP_RETCODE SCIPlpiGetSol( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Real* objval, /**< stores the objective value, may be NULL if not needed */ SCIP_Real* primsol, /**< primal solution vector, may be NULL if not needed */ SCIP_Real* dualsol, /**< dual solution vector, may be NULL if not needed */ SCIP_Real* activity, /**< row activity vector, may be NULL if not needed */ SCIP_Real* redcost /**< reduced cost vector, may be NULL if not needed */ ) { int nrows; register int i; assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("getting solution\n"); /* Do nothing if the status is not optimal, e.g., if we reached the objective limit or the problem is * infeasible. QSopt cannot return a solution in this case.*/ if ( lpi->solstat != QS_LP_OPTIMAL ) return SCIP_OKAY; nrows = QSget_rowcount(lpi->prob); SCIP_CALL( ensureRowMem(lpi, nrows) ); QS_CONDRET( QSget_solution(lpi->prob, objval, primsol, dualsol, lpi->irng, redcost) ); /* build back the activity */ if( activity ) { QS_CONDRET( QSget_rhs(lpi->prob, lpi->irhs) ); QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) ); for( i = 0; i < nrows; ++i ) { switch( lpi->isen[i] ) { case 'R': case 'E': case 'G': activity[i] = lpi->irhs[i] + lpi->irng[i]; break; case 'L': activity[i] = lpi->irhs[i] - lpi->irng[i]; break; default: SCIPerrorMessage("unknown sense %c\n", lpi->isen[i]); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } } #ifdef SCIP_DISABLED_CODE { int stat; int ncols; int sense; char* icstat; char* irstat; QSget_status(lpi->prob, &stat); if( stat == QS_LP_OPTIMAL ) { QS_CONDRET( QSget_objsense(lpi->prob, &sense) ); ncols = QSget_colcount(lpi->prob); SCIP_CALL(ensureTabMem(lpi, nrows + ncols)); icstat = lpi->ibas; irstat = lpi->ibas + ncols; QS_CONDRET( QSget_basis_array(lpi->prob,icstat, irstat) ); for( i = ncols ; i-- ; ) { switch( icstat[i] ) { case QS_COL_BSTAT_BASIC: case QS_COL_BSTAT_FREE: if( fabs(redcost[i])> FEASTOL ) { SCIPerrorMessage("stat col[%d] = %c, rd[%d] = %lg sense %d\n", i, icstat[i], i, redcost[i] * sense, sense); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } break; case QS_COL_BSTAT_UPPER: if( redcost[i] * sense > FEASTOL ) { SCIPerrorMessage("stat col[%d] = %c, rd[%d] = %lg sense %d\n", i, icstat[i], i, redcost[i] * sense, sense); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } break; case QS_COL_BSTAT_LOWER: if( redcost[i] * sense < -FEASTOL ) { SCIPerrorMessage("stat col[%d] = %c, rd[%d] = %lg sense %d\n", i, icstat[i], i, redcost[i] * sense, sense); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } break; default: SCIPerrorMessage("unknown stat col[%d] = %c, rd[%d] = %lg\n", i, icstat[i], i, redcost[i] * sense); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } } } #endif return SCIP_OKAY; } /** gets primal ray for unbounded LPs */ SCIP_RETCODE SCIPlpiGetPrimalRay( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Real* ray /**< primal ray */ ) { /*lint --e{715}*/ assert(lpi != NULL); assert(lpi->prob != NULL); assert(ray != NULL); SCIPerrorMessage("SCIPlpiGetPrimalRay() not supported by QSopt.\n"); return SCIP_LPERROR; } /** gets dual Farkas proof for infeasibility */ SCIP_RETCODE SCIPlpiGetDualfarkas( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Real* dualfarkas /**< dual Farkas row multipliers */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(dualfarkas != NULL); SCIPdebugMessage("calling QSopt dual Farkas: %d cols, %d rows, %d non zeros\n", QSget_colcount (lpi->prob), QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob)); QS_CONDRET( QSget_infeas_array(lpi->prob, dualfarkas) ); return SCIP_OKAY; } /** gets the number of LP iterations of the last solve call */ SCIP_RETCODE SCIPlpiGetIterations( SCIP_LPI* lpi, /**< LP interface structure */ int* iterations /**< pointer to store the number of iterations of the last solve call */ ) { int nit; assert(lpi != NULL); assert(lpi->prob != NULL); assert(iterations != NULL); QS_CONDRET( QSget_itcnt(lpi->prob, 0, 0, 0, 0, &nit) ); *iterations = nit - lpi->previt; lpi->previt = nit; return SCIP_OKAY; } /** gets information about the quality of an LP solution * * Such information is usually only available, if also a (maybe not optimal) solution is available. * The LPI should return SCIP_INVALID for @p quality, if the requested quantity is not available. */ SCIP_RETCODE SCIPlpiGetRealSolQuality( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_LPSOLQUALITY qualityindicator, /**< indicates which quality should be returned */ SCIP_Real* quality /**< pointer to store quality number */ ) { /*lint --e{715}*/ assert(lpi != NULL); assert(quality != NULL); SCIP_UNUSED( qualityindicator ); *quality = SCIP_INVALID; return SCIP_OKAY; } /**@} */ /* * LP Basis Methods */ /**@name LP Basis Methods */ /**@{ */ /** gets current basis status for columns and rows; arrays must be large enough to store the basis status */ SCIP_RETCODE SCIPlpiGetBase( SCIP_LPI* lpi, /**< LP interface structure */ int* cstat, /**< array to store column basis status, or NULL */ int* rstat /**< array to store row basis status, or NULL */ ) { int ncols; int nrows; char* icstat; char* irstat; register int i; assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("saving QSopt basis into %p/%p\n", (void*)cstat, (void*)rstat); ncols = QSget_colcount(lpi->prob); nrows = QSget_rowcount(lpi->prob); SCIP_CALL( ensureTabMem(lpi, nrows + ncols) ); SCIP_CALL( ensureRowMem(lpi, nrows) ); /* get senses */ QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) ); /* get basis */ icstat = lpi->ibas; irstat = lpi->ibas + ncols; QS_CONDRET( QSget_basis_array(lpi->prob, icstat, irstat) ); /* Now we must transform QSopt codes into SCIP codes. * We have the following cases: * 'G': b <= ax -> b = ax - s, s >= 0 * 'L': ax <= b -> b = ax + s, s >= 0 * 'R': b <= ax <= c -> c - b = ax + s, 0 <= s <= c - b */ for( i = 0; i < nrows; ++i ) { switch( irstat[i] ) { case QS_ROW_BSTAT_LOWER: if ( lpi->isen[i] == 'L' ) rstat[i] = (char) SCIP_BASESTAT_UPPER; else rstat[i] = (char) SCIP_BASESTAT_LOWER; break; case QS_ROW_BSTAT_BASIC: rstat[i] = (char) SCIP_BASESTAT_BASIC; break; case QS_ROW_BSTAT_UPPER: rstat[i] = (char) SCIP_BASESTAT_UPPER; break; default: SCIPerrorMessage("Unknown row basic status %c", rstat[i]); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } for( i = 0; i < ncols; ++i ) { switch( icstat[i] ) { case QS_COL_BSTAT_LOWER: cstat[i] = (char) SCIP_BASESTAT_LOWER; break; case QS_COL_BSTAT_BASIC: cstat[i] = (char) SCIP_BASESTAT_BASIC; break; case QS_COL_BSTAT_UPPER: cstat[i] = (char) SCIP_BASESTAT_UPPER; break; case QS_COL_BSTAT_FREE: cstat[i] = (char) SCIP_BASESTAT_ZERO; break; default: SCIPerrorMessage("Unknown column basic status %c", cstat[i]); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } return SCIP_OKAY; } /** sets current basis status for columns and rows */ SCIP_RETCODE SCIPlpiSetBase( SCIP_LPI* lpi, /**< LP interface structure */ const int* cstat, /**< array with column basis status */ const int* rstat /**< array with row basis status */ ) { int ncols; int nrows; register int i; char* icstat; char* irstat; assert(lpi != NULL); assert(lpi->prob != NULL); SCIP_CALL( SCIPlpiGetNRows(lpi, &nrows) ); SCIP_CALL( SCIPlpiGetNCols(lpi, &ncols) ); assert(cstat != NULL || ncols == 0); assert(rstat != NULL || nrows == 0); SCIPdebugMessage("loading basis %p/%p into QSopt\n", (void*)cstat, (void*)rstat); SCIP_CALL( ensureTabMem(lpi, ncols) ); SCIP_CALL( ensureRowMem(lpi, nrows) ); /* get senses */ QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) ); icstat = lpi->ibas; irstat = lpi->ibas + ncols; /* now we must transform QSopt codes into SCIP codes */ for( i = 0; i < nrows; ++i ) { switch( rstat[i] ) /*lint !e613*/ { case SCIP_BASESTAT_LOWER: irstat[i] = QS_ROW_BSTAT_LOWER; break; case SCIP_BASESTAT_BASIC: irstat[i] = QS_ROW_BSTAT_BASIC; break; case SCIP_BASESTAT_UPPER: if ( lpi->isen[i] == 'L' ) irstat[i] = QS_ROW_BSTAT_LOWER; else irstat[i] = QS_ROW_BSTAT_UPPER; break; default: SCIPerrorMessage("Unknown row basic status %d", rstat[i]); /*lint !e613*/ SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } for( i = 0; i < ncols; ++i ) { switch( cstat[i] ) /*lint !e613*/ { case SCIP_BASESTAT_LOWER: icstat[i] = QS_COL_BSTAT_LOWER; break; case SCIP_BASESTAT_BASIC: icstat[i] = QS_COL_BSTAT_BASIC; break; case SCIP_BASESTAT_UPPER: icstat[i] = QS_COL_BSTAT_UPPER; break; case SCIP_BASESTAT_ZERO: icstat[i] = QS_COL_BSTAT_FREE; break; default: SCIPerrorMessage("Unknown column basic status %d", cstat[i]); /*lint !e613*/ SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } /* set the basis */ QS_CONDRET( QSload_basis_array(lpi->prob, icstat, irstat) ); return SCIP_OKAY; } /** returns the indices of the basic columns and rows; basic column n gives value n, basic row m gives value -1-m */ SCIP_RETCODE SCIPlpiGetBasisInd( SCIP_LPI* lpi, /**< LP interface structure */ int* bind /**< pointer to store basis indices ready to keep number of rows entries */ ) { int nrows; int ncols; int stat; register int i; assert(lpi!=NULL); assert(lpi->prob!=NULL); assert(bind != NULL); SCIPdebugMessage("getting basis information\n"); nrows = QSget_rowcount(lpi->prob); ncols = QSget_colcount(lpi->prob); QS_CONDRET( QSget_status(lpi->prob, &stat) ); if ( stat == QS_LP_UNSOLVED || stat == QS_LP_MODIFIED || stat == QS_LP_NUMERR ) { QS_CONDRET( QSopt_dual(lpi->prob, &(lpi->solstat)) ); } QS_CONDRET( QSget_basis_order(lpi->prob, bind) ); /* transform QSopt basis header into SCIP format */ for( i = 0; i < nrows; ++i ) { if( bind[i] >= ncols ) bind[i] = -(bind[i] - ncols) - 1; } return SCIP_OKAY; } /** get row of inverse basis matrix B^-1 * * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated; * see also the explanation in lpi.h. * * @todo check that the result is in terms of the LP interface definition */ SCIP_RETCODE SCIPlpiGetBInvRow( SCIP_LPI* lpi, /**< LP interface structure */ int r, /**< row number */ SCIP_Real* coef, /**< pointer to store the coefficients of the row */ int* inds, /**< array to store the non-zero indices, or NULL */ int* ninds /**< pointer to store the number of non-zero indices, or NULL * (-1: if we do not store sparsity information) */ ) { /*lint --e{715} */ int nrows; int i; assert(lpi!=NULL); assert(lpi->prob!=NULL); assert(coef != NULL); SCIP_UNUSED( inds ); nrows = QSget_rowcount(lpi->prob); assert( 0 <= r && r < nrows ); SCIPdebugMessage("getting binv-row %d from Qsopt %d cols, %d rows, %d nonz\n", r, QSget_colcount(lpi->prob), QSget_rowcount(lpi->prob), QSget_nzcount(lpi->prob)); /* can only return dense result */ if ( ninds != NULL ) *ninds = -1; QS_CONDRET( QSget_binv_row(lpi->prob, r, coef) ); for (i = 0; i < nrows; i++) coef[i] *= -1.0; return SCIP_OKAY; } /** get column of inverse basis matrix B^-1 * * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated; * see also the explanation in lpi.h. * * @todo check that the result is in terms of the LP interface definition */ SCIP_RETCODE SCIPlpiGetBInvCol( SCIP_LPI* lpi, /**< LP interface structure */ int c, /**< column number of B^-1; this is NOT the number of the column in the LP; * you have to call SCIPlpiGetBasisInd() to get the array which links the * B^-1 column numbers to the row and column numbers of the LP! * c must be between 0 and nrows-1, since the basis has the size * nrows * nrows */ SCIP_Real* coef, /**< pointer to store the coefficients of the column */ int* inds, /**< array to store the non-zero indices, or NULL */ int* ninds /**< pointer to store the number of non-zero indices, or NULL * (-1: if we do not store sparsity information) */ ) { /*lint --e{715} */ assert(lpi!=NULL); assert(lpi->prob!=NULL); assert(coef != NULL); SCIP_UNUSED( c ); SCIP_UNUSED( inds ); SCIP_UNUSED( ninds ); SCIPerrorMessage("SCIPlpiGetBInvCol() not supported by QSopt.\n"); /* QSopt does not provide an interface for this yet */ return SCIP_LPERROR; } /** get row of inverse basis matrix times constraint matrix B^-1 * A * * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated; * see also the explanation in lpi.h. * * @todo check that the result is in terms of the LP interface definition */ SCIP_RETCODE SCIPlpiGetBInvARow( SCIP_LPI* lpi, /**< LP interface structure */ int r, /**< row number */ const SCIP_Real* binvrow, /**< row in (A_B)^-1 from prior call to SCIPlpiGetBInvRow(), or NULL */ SCIP_Real* coef, /**< vector to return coefficients of the row */ int* inds, /**< array to store the non-zero indices, or NULL */ int* ninds /**< pointer to store the number of non-zero indices, or NULL * (-1: if we do not store sparsity information) */ ) { /*lint --e{715} */ int ncols; int nrows; int i; assert(lpi != NULL); assert(lpi->prob != NULL); assert(coef != NULL); SCIP_UNUSED( binvrow ); SCIP_UNUSED( inds ); SCIPdebugMessage("getting binva-row %d\n", r); /* can only return dense result */ if ( ninds != NULL ) *ninds = -1; ncols = QSget_colcount(lpi->prob); nrows = QSget_rowcount(lpi->prob); SCIP_CALL( ensureTabMem(lpi, nrows + ncols) ); QS_CONDRET( QSget_tableau_row(lpi->prob, r, lpi->itab) ); /* copy local information to the outside */ BMScopyMemoryArray(coef, lpi->itab, ncols); for (i = 0; i < ncols; ++i) coef[i] *= -1.0; return SCIP_OKAY; } /** get column of inverse basis matrix times constraint matrix B^-1 * A * * @note The LP interface defines slack variables to have coefficient +1. This means that if, internally, the LP solver * uses a -1 coefficient, then rows associated with slacks variables whose coefficient is -1, should be negated; * see also the explanation in lpi.h. * * @todo check that the result is in terms of the LP interface definition */ SCIP_RETCODE SCIPlpiGetBInvACol( SCIP_LPI* lpi, /**< LP interface structure */ int c, /**< column number */ SCIP_Real* coef, /**< vector to return coefficients of the column */ int* inds, /**< array to store the non-zero indices, or NULL */ int* ninds /**< pointer to store the number of non-zero indices, or NULL * (-1: if we do not store sparsity information) */ ) { /*lint --e{715} */ assert(lpi!=NULL); assert(lpi->prob!=NULL); assert(coef != NULL); assert(c >= 0); SCIP_UNUSED( inds ); SCIP_UNUSED( ninds ); SCIPerrorMessage("SCIPlpiGetBInvACol() not supported by QSopt.\n"); /* QSopt does not provide an interface for this yet */ return SCIP_LPERROR; } /**@} */ /* * LP State Methods */ /**@name LP State Methods */ /**@{ */ /** stores LPi state (like basis information) into lpistate object */ SCIP_RETCODE SCIPlpiGetState( SCIP_LPI* lpi, /**< LP interface structure */ BMS_BLKMEM* blkmem, /**< block memory */ SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */ ) { int ncols, nrows; assert(lpi != NULL); assert(lpi->prob != NULL); assert(blkmem != NULL); assert(lpistate != NULL); ncols = QSget_colcount(lpi->prob); nrows = QSget_rowcount(lpi->prob); assert(ncols >= 0); assert(nrows >= 0); /* allocate lpistate data */ SCIP_CALL( lpistateCreate(lpistate, blkmem, ncols, nrows)); SCIPdebugMessage("storing QSopt LPI state in %p (%d cols, %d rows)\n", (void*)*lpistate, ncols, nrows); /* get unpacked basis information from QSopt */ SCIP_CALL( ensureColMem(lpi, ncols) ); SCIP_CALL( ensureRowMem(lpi, nrows) ); SCIP_CALL( SCIPlpiGetBase(lpi, lpi->iccnt, lpi->ircnt) ); /* pack LPi state data */ (*lpistate)->ncols = ncols; (*lpistate)->nrows = nrows; lpistatePack(*lpistate, lpi->iccnt, lpi->ircnt); return SCIP_OKAY; } /** loads LPi state (like basis information) into solver; note that the LP might have been extended with additional * columns and rows since the state was stored with SCIPlpiGetState() */ SCIP_RETCODE SCIPlpiSetState( SCIP_LPI* lpi, /**< LP interface structure */ BMS_BLKMEM* blkmem, /**< block memory */ const SCIP_LPISTATE* lpistate /**< LPi state information (like basis information), or NULL */ ) { /*lint --e{715} */ char* icstat; char* irstat; int i; int ncols; int nrows; assert(lpi != NULL); assert(lpi->prob != NULL); assert(blkmem != NULL); /* if there was no basis information available, LPI state was not stored */ if( lpistate == NULL ) return SCIP_OKAY; /* continue test */ ncols = QSget_colcount(lpi->prob); nrows = QSget_rowcount(lpi->prob); assert(ncols >= 0); assert(nrows >= 0); assert(lpistate->ncols <= ncols); assert(lpistate->nrows <= nrows); SCIPdebugMessage("loading LPI state %p (%d cols, %d rows) into QSopt LP with %d cols and %d rows\n", (void*)lpistate, lpistate->ncols, lpistate->nrows, ncols, nrows); if( lpistate->ncols == 0 || lpistate->nrows == 0 ) return SCIP_OKAY; /* allocate enough memory for storing uncompressed basis information */ SCIP_CALL( ensureColMem(lpi, ncols) ); SCIP_CALL( ensureRowMem(lpi, nrows) ); SCIP_CALL( ensureTabMem(lpi, nrows + ncols) ); icstat = lpi->ibas; irstat = lpi->ibas + ncols; /* get senses */ QS_CONDRET( QSget_senses(lpi->prob, lpi->isen) ); /* unpack LPi state data */ lpistateUnpack(lpistate, lpi->iccnt, lpi->ircnt); /* extend the basis to the current LP beyond the previously existing columns */ for( i = lpistate->ncols; i < ncols; ++i ) { SCIP_Real lb; SCIP_Real ub; /* get bounds from qsopt */ QS_CONDRET( QSget_bounds_list(lpi->prob, 1, &i, &lb, &ub) ); if ( SCIPlpiIsInfinity(lpi, REALABS(lb)) ) { /* if lower bound is +/- infinity -> try upper bound */ if ( SCIPlpiIsInfinity(lpi, REALABS(ub)) ) lpi->iccnt[i] = (int) SCIP_BASESTAT_ZERO; /* variable is free */ else lpi->iccnt[i] = (int) SCIP_BASESTAT_UPPER; /* use finite upper bound */ } else lpi->iccnt[i] = (int) SCIP_BASESTAT_LOWER; /* use finite lower bound */ } for( i = lpistate->nrows; i < nrows; ++i ) /*lint !e850*/ lpi->ircnt[i] = (int) SCIP_BASESTAT_BASIC; /* convert the loaded basis into QSopt format */ for( i = 0; i < nrows; ++i ) { switch( lpi->ircnt[i] ) { case SCIP_BASESTAT_LOWER: irstat[i] = QS_ROW_BSTAT_LOWER; break; case SCIP_BASESTAT_BASIC: irstat[i] = QS_ROW_BSTAT_BASIC; break; case SCIP_BASESTAT_UPPER: if ( lpi->isen[i] == 'L' ) irstat[i] = QS_ROW_BSTAT_LOWER; else irstat[i] = QS_ROW_BSTAT_UPPER; break; default: SCIPerrorMessage("Unknown row basic status %d", lpi->ircnt[i]); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } for( i = 0; i < ncols; ++i ) { switch( lpi->iccnt[i] ) { case SCIP_BASESTAT_LOWER: icstat[i] = QS_COL_BSTAT_LOWER; break; case SCIP_BASESTAT_BASIC: icstat[i] = QS_COL_BSTAT_BASIC; break; case SCIP_BASESTAT_UPPER: icstat[i] = QS_COL_BSTAT_UPPER; break; case SCIP_BASESTAT_ZERO: icstat[i] = QS_COL_BSTAT_FREE; break; default: SCIPerrorMessage("Unknown column basic status %d", lpi->iccnt[i]); SCIPABORT(); return SCIP_INVALIDDATA; /*lint !e527*/ } } /* set the basis */ QS_CONDRET( QSload_basis_array(lpi->prob, icstat, irstat) ); return SCIP_OKAY; } /** clears current LPi state (like basis information) of the solver */ SCIP_RETCODE SCIPlpiClearState( SCIP_LPI* lpi /**< LP interface structure */ ) { int ncols; int nrows; int* cstat; int* rstat; int i; assert( lpi != NULL ); assert( lpi->prob != NULL ); SCIPdebugMessage("SCIPlpiClearState()\n"); ncols = QSget_colcount(lpi->prob); nrows = QSget_rowcount(lpi->prob); if ( ncols == 0 || nrows == 0 ) return SCIP_OKAY; SCIP_ALLOC( BMSallocMemoryArray(&cstat, ncols) ); SCIP_ALLOC( BMSallocMemoryArray(&rstat, nrows) ); for (i = 0; i < ncols; ++i) cstat[i] = (char) SCIP_BASESTAT_LOWER; for (i = 0; i < nrows; ++i) rstat[i] = (char) SCIP_BASESTAT_BASIC; SCIP_CALL( SCIPlpiSetBase(lpi, cstat, rstat) ); BMSfreeMemoryArray(&cstat); BMSfreeMemoryArray(&rstat); return SCIP_OKAY; } /** frees LPi state information */ SCIP_RETCODE SCIPlpiFreeState( SCIP_LPI* lpi, /**< LP interface structure */ BMS_BLKMEM* blkmem, /**< block memory */ SCIP_LPISTATE** lpistate /**< pointer to LPi state information (like basis information) */ ) { assert(lpi != NULL); assert(lpistate != NULL); assert(blkmem != NULL); if( *lpistate != NULL ) lpistateFree(lpistate, blkmem); return SCIP_OKAY; } /** checks, whether the given LP state contains simplex basis information */ SCIP_Bool SCIPlpiHasStateBasis( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_LPISTATE* lpistate /**< LP state information (like basis information), or NULL */ ) { /*lint --e{715} */ assert(lpi != NULL); return (lpistate != NULL); } /** reads LP state (like basis information from a file */ SCIP_RETCODE SCIPlpiReadState( SCIP_LPI* lpi, /**< LP interface structure */ const char* fname /**< file name */ ) { int rval; assert(lpi != NULL); assert(lpi->prob != NULL); assert(fname != NULL); SCIPdebugMessage("reading QSopt LP state from file <%s>\n", fname); rval = QSread_and_load_basis(lpi->prob, fname); if( rval ) { SCIPerrorMessage("Error while loading basis from file <%s>.\n", fname); return SCIP_READERROR; } return SCIP_OKAY; } /** writes LPi state (i.e. basis information) to a file */ SCIP_RETCODE SCIPlpiWriteState( SCIP_LPI* lpi, /**< LP interface structure */ const char* fname /**< file name */ ) { QSbas bas; int rval; assert(lpi != NULL); assert(lpi->prob != NULL); assert(fname != NULL); SCIPdebugMessage("writing QSopt LP state to file <%s>\n", fname); bas = QSget_basis(lpi->prob); QS_ERROR(bas == 0, "Could not get basis from problem."); /*lint !e820*/ assert(bas); rval = QSwrite_basis(lpi->prob, bas, fname); QSfree(bas); if( rval ) { SCIPerrorMessage("Could not write basis to file <%s>.\n", fname); return SCIP_WRITEERROR; } return SCIP_OKAY; } /**@} */ /* * LP Pricing Norms Methods */ /**@name LP Pricing Norms Methods */ /**@{ */ /** stores LPi pricing norms information * @todo should we store norm information? */ SCIP_RETCODE SCIPlpiGetNorms( SCIP_LPI* lpi, /**< LP interface structure */ BMS_BLKMEM* blkmem, /**< block memory */ SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information */ ) { /*lint --e{715} */ int ncols; int nrows; assert( lpi != NULL ); assert( lpi->prob != NULL ); assert( lpinorms != NULL ); assert( blkmem != NULL ); ncols = QSget_colcount(lpi->prob); nrows = QSget_rowcount(lpi->prob); /* allocate lpinorms data */ SCIP_ALLOC( BMSallocBlockMemory(blkmem, lpinorms) ); (*lpinorms)->ncols = ncols; (*lpinorms)->nrows = nrows; if ( QStest_row_norms(lpi->prob) ) { SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->cstat, ncols) ); SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->rstat, nrows) ); SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &(*lpinorms)->norms, nrows) ); QS_CONDRET( QSget_basis_and_row_norms_array(lpi->prob, (*lpinorms)->cstat, (*lpinorms)->rstat, (*lpinorms)->norms) ); } else { (*lpinorms)->cstat = NULL; (*lpinorms)->rstat = NULL; (*lpinorms)->norms = NULL; } return SCIP_OKAY; } /** loads LPi pricing norms into solver; note that the LP might have been extended with additional * columns and rows since the state was stored with SCIPlpiGetNorms() */ SCIP_RETCODE SCIPlpiSetNorms( SCIP_LPI* lpi, /**< LP interface structure */ BMS_BLKMEM* blkmem, /**< block memory */ const SCIP_LPINORMS* lpinorms /**< LPi pricing norms information, or NULL */ ) { /*lint --e{715} */ int ncols; int nrows; assert( lpi != NULL ); assert( lpi->prob != NULL ); SCIP_UNUSED( blkmem ); if ( lpinorms->norms == NULL ) return SCIP_OKAY; ncols = QSget_colcount(lpi->prob); nrows = QSget_rowcount(lpi->prob); if ( nrows != lpinorms->nrows || ncols != lpinorms->ncols ) return SCIP_OKAY; /* load row norms */ assert( lpinorms->cstat != NULL && lpinorms->rstat != NULL && lpinorms->norms != NULL ); QS_CONDRET( QSload_basis_and_row_norms_array(lpi->prob, lpinorms->cstat, lpinorms->rstat, lpinorms->norms) ); return SCIP_OKAY; } /** frees pricing norms information */ SCIP_RETCODE SCIPlpiFreeNorms( SCIP_LPI* lpi, /**< LP interface structure */ BMS_BLKMEM* blkmem, /**< block memory */ SCIP_LPINORMS** lpinorms /**< pointer to LPi pricing norms information, or NULL */ ) { /*lint --e{715} */ assert( lpinorms != NULL ); assert( lpi != NULL ); if ( (*lpinorms)->norms != NULL ) { assert( (*lpinorms)->cstat != NULL && (*lpinorms)->rstat != NULL ); BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->norms, (*lpinorms)->nrows); BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->rstat, (*lpinorms)->nrows); BMSfreeBlockMemoryArray(blkmem, &(*lpinorms)->cstat, (*lpinorms)->ncols); } BMSfreeBlockMemory(blkmem, lpinorms); return SCIP_OKAY; } /**@} */ /* * Parameter Methods */ /**@name Parameter Methods */ /**@{ */ /** gets integer parameter of LP */ SCIP_RETCODE SCIPlpiGetIntpar( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_LPPARAM type, /**< parameter number */ int* ival /**< buffer to store the parameter value */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(ival != NULL); SCIPdebugMessage("getting int parameter %d\n", type); switch( type ) { case SCIP_LPPAR_FROMSCRATCH: case SCIP_LPPAR_FASTMIP: case SCIP_LPPAR_PRESOLVING: return SCIP_PARAMETERUNKNOWN; case SCIP_LPPAR_SCALING: QS_CONDRET( QSget_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, ival) ); assert((*ival) == 0 || (*ival) == 1); break; case SCIP_LPPAR_PRICING: *ival = lpi->pricing; break; case SCIP_LPPAR_LPINFO: QS_CONDRET( QSget_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, ival) ); if( *ival ) *ival = TRUE; else *ival = FALSE; break; case SCIP_LPPAR_LPITLIM: QS_CONDRET( QSget_param(lpi->prob, QS_PARAM_SIMPLEX_MAX_ITERATIONS, ival) ); break; default: return SCIP_PARAMETERUNKNOWN; } /*lint !e788*/ return SCIP_OKAY; } /** sets integer parameter of LP */ SCIP_RETCODE SCIPlpiSetIntpar( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_LPPARAM type, /**< parameter number */ int ival /**< parameter value */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("setting int parameter %d to %d\n", type, ival); switch( type ) { case SCIP_LPPAR_SCALING: if( ival == 0 ) QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, 0) ); else QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_SCALING, 1) ); break; case SCIP_LPPAR_PRICING: lpi->pricing = ival; switch( ival ) { case SCIP_PRICING_AUTO: case SCIP_PRICING_LPIDEFAULT: case SCIP_PRICING_FULL: case SCIP_PRICING_STEEP: case SCIP_PRICING_STEEPQSTART: QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_PRIMAL_PRICING, QS_PRICE_PSTEEP) ); QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_DUAL_PRICING, QS_PRICE_DSTEEP) ); break; case SCIP_PRICING_PARTIAL: QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_PRIMAL_PRICING,QS_PRICE_PMULTPARTIAL) ); QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_DUAL_PRICING,QS_PRICE_DMULTPARTIAL) ); break; case SCIP_PRICING_DEVEX: QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_PRIMAL_PRICING,QS_PRICE_PDEVEX) ); QS_CONDRET( QSset_param(lpi->prob,QS_PARAM_DUAL_PRICING,QS_PRICE_DDEVEX) ); break; default: return SCIP_LPERROR; } break; case SCIP_LPPAR_LPINFO: if( ival ) QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, 1) ); else QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_DISPLAY, 0) ); break; case SCIP_LPPAR_LPITLIM: /* The maximum number of pivots allowed in the algorithm can be set with the QS_PARAM_SIMPLEX_MAX_ITERATIONS parameter. * ival can be any positive integer, 0 stopping immediately */ assert( ival >= 0 ); QS_CONDRET( QSset_param(lpi->prob, QS_PARAM_SIMPLEX_MAX_ITERATIONS, ival) ); break; default: return SCIP_PARAMETERUNKNOWN; } /*lint !e788*/ return SCIP_OKAY; } /** gets floating point parameter of LP */ SCIP_RETCODE SCIPlpiGetRealpar( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_LPPARAM type, /**< parameter number */ SCIP_Real* dval /**< buffer to store the parameter value */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(dval != NULL); SCIPdebugMessage("getting real parameter %d\n", type); switch( type ) { case SCIP_LPPAR_OBJLIM: { int sense; QS_CONDRET( QSget_objsense(lpi->prob, &sense) ); if ( sense == QS_MIN ) { QS_CONDRET( QSget_param_double(lpi->prob, QS_PARAM_OBJULIM, dval) ); } else { QS_CONDRET( QSget_param_double(lpi->prob, QS_PARAM_OBJLLIM, dval) ); } break; } case SCIP_LPPAR_LPTILIM: QS_CONDRET( QSget_param_double(lpi->prob, QS_PARAM_SIMPLEX_MAX_TIME, dval) ); break; default: case SCIP_LPPAR_MARKOWITZ: case SCIP_LPPAR_BARRIERCONVTOL: case SCIP_LPPAR_DUALFEASTOL: case SCIP_LPPAR_FEASTOL: return SCIP_PARAMETERUNKNOWN; } /*lint !e788*/ return SCIP_OKAY; } /** sets floating point parameter of LP */ SCIP_RETCODE SCIPlpiSetRealpar( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_LPPARAM type, /**< parameter number */ SCIP_Real dval /**< parameter value */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); SCIPdebugMessage("setting real parameter %d to %g\n", type, dval); switch( type ) { case SCIP_LPPAR_LPTILIM: assert( dval > 0.0 ); /* qso requires dval >= 0 * * However for consistency we assert the timelimit to be strictly positive. */ QS_CONDRET( QSset_param_double(lpi->prob, QS_PARAM_SIMPLEX_MAX_TIME, dval) ); break; case SCIP_LPPAR_OBJLIM: { int sense; QS_CONDRET( QSget_objsense(lpi->prob, &sense) ); if ( sense == QS_MIN ) { QS_CONDRET( QSset_param_double(lpi->prob, QS_PARAM_OBJULIM, dval) ); } else { QS_CONDRET( QSset_param_double(lpi->prob, QS_PARAM_OBJLLIM, dval) ); } break; } case SCIP_LPPAR_FEASTOL: case SCIP_LPPAR_DUALFEASTOL: case SCIP_LPPAR_BARRIERCONVTOL: case SCIP_LPPAR_MARKOWITZ: default: return SCIP_PARAMETERUNKNOWN; } /*lint !e788*/ return SCIP_OKAY; } /**@} */ /* * Numerical Methods */ /**@name Numerical Methods */ /**@{ */ /** returns value treated as infinity in the LP solver */ SCIP_Real SCIPlpiInfinity( SCIP_LPI* lpi /**< LP interface structure */ ) { /*lint --e{715} */ assert(lpi != NULL); return QS_MAXDOUBLE; } /** checks if given value is treated as infinity in the LP solver */ SCIP_Bool SCIPlpiIsInfinity( SCIP_LPI* lpi, /**< LP interface structure */ SCIP_Real val /**< value to be checked for infinity */ ) { /*lint --e{715} */ assert(lpi != NULL); return (val >= QS_MAXDOUBLE); } /**@} */ /* * File Interface Methods */ /**@name File Interface Methods */ /**@{ */ /** reads LP from a file */ SCIP_RETCODE SCIPlpiReadLP( SCIP_LPI* lpi, /**< LP interface structure */ const char* fname /**< file name */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(fname != NULL); SCIPdebugMessage("reading LP from file <%s>\n", fname); if( lpi->prob != NULL ) QSfree_prob(lpi->prob); lpi->solstat = 0; lpi->previt = 0; lpi->prob = QSread_prob(fname, "LP"); if( lpi->prob == 0 ) return SCIP_READERROR; return SCIP_OKAY; } /** writes LP to a file */ SCIP_RETCODE SCIPlpiWriteLP( SCIP_LPI* lpi, /**< LP interface structure */ const char* fname /**< file name */ ) { assert(lpi != NULL); assert(lpi->prob != NULL); assert(fname != NULL); SCIPdebugMessage("writing LP to file <%s>\n", fname); if( QSwrite_prob (lpi->prob, fname, "LP") ) return SCIP_WRITEERROR; return SCIP_OKAY; } /**@} */