/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /* */ /* This file is part of the program and library */ /* SCIP --- Solving Constraint Integer Programs */ /* */ /* Copyright 2002-2022 Zuse Institute Berlin */ /* */ /* Licensed under the Apache License, Version 2.0 (the "License"); */ /* you may not use this file except in compliance with the License. */ /* You may obtain a copy of the License at */ /* */ /* http://www.apache.org/licenses/LICENSE-2.0 */ /* */ /* Unless required by applicable law or agreed to in writing, software */ /* distributed under the License is distributed on an "AS IS" BASIS, */ /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ /* See the License for the specific language governing permissions and */ /* limitations under the License. */ /* */ /* You should have received a copy of the Apache-2.0 license */ /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ /* */ /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ /**@file pub_misc_rowprep.h * @brief preparation of a linear inequality to become a SCIP_ROW * @ingroup PUBLICCOREAPI * @author Stefan Vigerske * @author Benjamin Mueller * @author Felipe Serrano */ /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ #ifndef __SCIP_PUB_MISC_ROWPREP_H__ #define __SCIP_PUB_MISC_ROWPREP_H__ #include "scip/type_misc.h" #include "scip/type_cons.h" #include "scip/type_lp.h" #include "scip/type_sepa.h" #include "scip/type_var.h" #ifdef NDEBUG #include "scip/struct_misc.h" #endif #ifdef __cplusplus extern "C" { #endif /**@defgroup RowPrep Linear Inequality * @ingroup DataStructures * @brief a linear inequality that is prepared to become a SCIP_ROW * * This data structure helps to work around some limitations of SCIP_ROW's, in particular, * that it rounds coefficients or sides close to integral values without the appropriate care. * On the other hand, a SCIP_ROWPREP is limited to inequalities. * *@{ */ /** creates a SCIP_ROWPREP datastructure * * Initial row represents 0 ≤ 0. */ SCIP_EXPORT SCIP_RETCODE SCIPcreateRowprep( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP** rowprep, /**< buffer to store pointer to rowprep */ SCIP_SIDETYPE sidetype, /**< whether cut will be or lower-equal or larger-equal type */ SCIP_Bool local /**< whether cut will be valid only locally */ ); /** frees a SCIP_ROWPREP datastructure */ SCIP_EXPORT void SCIPfreeRowprep( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP** rowprep /**< pointer that stores pointer to rowprep */ ); /** creates a copy of a SCIP_ROWPREP datastructure */ SCIP_EXPORT SCIP_RETCODE SCIPcopyRowprep( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP** target, /**< buffer to store pointer of rowprep copy */ SCIP_ROWPREP* source /**< rowprep to copy */ ); /** gives number of terms in rowprep */ SCIP_EXPORT int SCIProwprepGetNVars( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** gives variables of rowprep (feel free to modify) */ SCIP_EXPORT SCIP_VAR** SCIProwprepGetVars( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** gives coefficients of rowprep (feel free to modify) */ SCIP_EXPORT SCIP_Real* SCIProwprepGetCoefs( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** gives side of rowprep */ SCIP_EXPORT SCIP_Real SCIProwprepGetSide( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** gives kind of inequality of rowprep */ SCIP_EXPORT SCIP_SIDETYPE SCIProwprepGetSidetype( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** returns whether rowprep is locally valid only */ SCIP_EXPORT SCIP_Bool SCIProwprepIsLocal( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** returns name of rowprep (feel free to modify) */ SCIP_EXPORT char* SCIProwprepGetName( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** returns number of variables which coefficients were modified in cleanup */ SCIP_EXPORT int SCIProwprepGetNModifiedVars( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** returns variables which coefficients were modified in cleanup */ SCIP_EXPORT SCIP_VAR** SCIProwprepGetModifiedVars( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** resets rowprep to have 0 terms and side 0.0 */ SCIP_EXPORT void SCIProwprepReset( SCIP_ROWPREP* rowprep /**< rowprep */ ); /** adds constant value to side of rowprep */ SCIP_EXPORT void SCIProwprepAddSide( SCIP_ROWPREP* rowprep, /**< rowprep */ SCIP_Real side /**< constant value to be added to side */ ); /** adds constant term to rowprep * * Substracts constant from side. */ SCIP_EXPORT void SCIProwprepAddConstant( SCIP_ROWPREP* rowprep, /**< rowprep */ SCIP_Real constant /**< constant value to be added */ ); /** sets side type of rowprep */ SCIP_EXPORT void SCIProwprepSetSidetype( SCIP_ROWPREP* rowprep, /**< rowprep */ SCIP_SIDETYPE sidetype /**< new side type */ ); /** sets whether rowprep is local */ SCIP_EXPORT void SCIProwprepSetLocal( SCIP_ROWPREP* rowprep, /**< rowprep */ SCIP_Bool islocal /**< whether rowprep is local */ ); /** enables recording for where modifications were done in cleanup */ SCIP_EXPORT void SCIProwprepRecordModifications( SCIP_ROWPREP* rowprep /**< rowprep */ ); #ifdef NDEBUG /* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and * speed up the algorithms. */ #define SCIProwprepGetNVars(rowprep) (rowprep)->nvars #define SCIProwprepGetVars(rowprep) (rowprep)->vars #define SCIProwprepGetCoefs(rowprep) (rowprep)->coefs #define SCIProwprepGetSide(rowprep) (rowprep)->side #define SCIProwprepGetSidetype(rowprep) (rowprep)->sidetype #define SCIProwprepIsLocal(rowprep) (rowprep)->local #define SCIProwprepGetName(rowprep) (rowprep)->name #define SCIProwprepGetNModifiedVars(rowprep) (rowprep)->nmodifiedvars #define SCIProwprepGetModifiedVars(rowprep) (rowprep)->modifiedvars #define SCIProwprepAddSide(rowprep, sideadd) ((rowprep)->side += (sideadd)) #define SCIProwprepAddConstant(rowprep, constant) SCIProwprepAddSide(rowprep, -(constant)) #define SCIProwprepSetSidetype(rowprep, sidetype_) (rowprep)->sidetype = sidetype_ #define SCIProwprepSetLocal(rowprep, islocal) (rowprep)->local = islocal #define SCIProwprepRecordModifications(rowprep) (rowprep)->recordmodifications = TRUE #endif /** prints a rowprep */ SCIP_EXPORT void SCIPprintRowprep( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep to be printed */ FILE* file /**< file to print to, or NULL for stdout */ ); /** prints a rowprep and values in solution */ SCIP_EXPORT void SCIPprintRowprepSol( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep to be printed */ SCIP_SOL* sol, /**< solution for activity */ FILE* file /**< file to print to, or NULL for stdout */ ); /** ensures that rowprep has space for at least given number of additional terms * * Useful when knowing in advance how many terms will be added. */ SCIP_EXPORT SCIP_RETCODE SCIPensureRowprepSize( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep */ int size /**< number of additional terms for which to alloc space in rowprep */ ); /** adds a term coef*var to a rowprep */ SCIP_EXPORT SCIP_RETCODE SCIPaddRowprepTerm( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep */ SCIP_VAR* var, /**< variable to add */ SCIP_Real coef /**< coefficient to add */ ); /** adds several terms coef*var to a rowprep */ SCIP_EXPORT SCIP_RETCODE SCIPaddRowprepTerms( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep */ int nvars, /**< number of terms to add */ SCIP_VAR** vars, /**< variables to add */ SCIP_Real* coefs /**< coefficients to add */ ); /** computes violation of rowprep in a given solution * * Can return whether the violation value is reliable from a floating-point accuracy point of view. * The value will not be deemed reliable when its calculation involved the subtraction of large numbers. * To be precise, the violation of an inequality \f$ \sum_i a_ix_i \leq b \f$ in a solution \f$x^*\f$ is deemed * reliable if \f$ |\sum_i a_ix^*_i - b| \geq 2^{-50} \max (|b|, \max_i |a_ix^*_i|) \f$. */ SCIP_EXPORT SCIP_Real SCIPgetRowprepViolation( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep */ SCIP_SOL* sol, /**< solution or NULL for LP solution */ SCIP_Bool* reliable /**< buffer to store whether computed violation is reliable (numerically), or NULL if not of interest */ ); /** computes violation of rowprep in a given solution and reports whether that value seem numerically reliable * * @see SCIPgetRowprepViolation() */ SCIP_EXPORT SCIP_Bool SCIPisRowprepViolationReliable( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep */ SCIP_SOL* sol /**< solution or NULL for LP solution */ ); /** Merge terms that use same variable and eliminate zero coefficients. * * Removes a variable if its bounds have a relative difference of below epsilon. * Local bounds are checked for local rows, otherwise global bounds are used. * If the bounds are not absolute equal, the bound that relaxes the row is used. * * Terms are sorted by variable (see SCIPvarComp()) after return. */ SCIP_EXPORT void SCIPmergeRowprepTerms( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep /**< rowprep to be cleaned up */ ); /** Cleans up and attempts to improve rowprep * * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol, * if this can be done by relaxing the row. * Scales coefficients up to reach minimal violation, if possible. * Scaling is omitted if violation is very small (\ref ROWPREP_SCALEUP_VIOLNONZERO) or * maximal coefficient would become huge (\ref ROWPREP_SCALEUP_MAXMAXCOEF). * Scales coefficients and side down if they are large and if the minimal violation is still reached. * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row. * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least. * * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order. * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0). * * `success` is set to TRUE if and only if the rowprep satisfies the following: * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol * - the violation is at least `minviol` * - the violation is reliable or `minviol` = 0 * - the absolute value of coefficients are below SCIPinfinity() * - the absolute value of the side is below SCIPinfinity() */ SCIP_EXPORT SCIP_RETCODE SCIPcleanupRowprep( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */ SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */ SCIP_Real minviol, /**< minimal absolute violation the row should achieve (w.r.t. sol) */ SCIP_Real* viol, /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */ SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */ ); /** Cleans up and attempts to improve rowprep without regard for violation * * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol, * if this can be done by relaxing the row. * Scales coefficients and side to have maximal coefficient in `[1/maxcoefbound,maxcoefbound]`. * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row. * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least. * * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order. * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0). * * `success` is set to TRUE if and only if the rowprep satisfies the following: * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol * - the absolute value of coefficients are below SCIPinfinity() * - the absolute value of the side is below SCIPinfinity() * * In difference to SCIPcleanupRowprep(), this function does not scale up the row to increase the absolute violation. */ SCIP_EXPORT SCIP_RETCODE SCIPcleanupRowprep2( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */ SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */ SCIP_Real maxcoefbound, /**< bound on absolute value of largest coefficient */ SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */ ); /** Scales up a rowprep to increase coefficients/sides that are within epsilon to an integer value, if possible. * * Computes the minimal fractionality of all fractional coefficients and the side of the rowprep. * If this fractionality is below epsilon, the rowprep is scaled up such that the fractionality exceeds epsilon, * if this will not put any coefficient or side above SCIPhugeValue(). * * This function does not relax the rowprep. * * `success` is set to TRUE if the resulting rowprep can be turned into a SCIP_ROW, that is, * all coefs and the side is below SCIPinfinity() and fractionalities are above epsilon. * If `success` is set to FALSE, then the rowprep will not have been modified. * * @return The applied scaling factor, if `success` is set to TRUE. */ SCIP_EXPORT SCIP_Real SCIPscaleupRowprep( SCIP* scip, /**< SCIP data structure */ SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */ SCIP_Real minscaleup, /**< minimal factor by which to scale up row, or <= 1.0 if to be ignored */ SCIP_Bool* success /**< buffer to store whether rowprep could be turned into SCIP_ROW without loss, or NULL if not of interest */ ); /** scales a rowprep by given factor (after some rounding) * * @return Exponent of actually applied scaling factor, if written as \f$2^x\f$. */ SCIP_EXPORT int SCIPscaleRowprep( SCIP_ROWPREP* rowprep, /**< rowprep to be scaled */ SCIP_Real factor /**< suggested scale factor */ ); /** generates a SCIP_ROW from a rowprep, setting its origin to given constraint handler */ SCIP_EXPORT SCIP_RETCODE SCIPgetRowprepRowConshdlr( SCIP* scip, /**< SCIP data structure */ SCIP_ROW** row, /**< buffer to store pointer to new row */ SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ SCIP_CONSHDLR* conshdlr /**< constraint handler */ ); /** generates a SCIP_ROW from a rowprep, setting its origin to given constraint */ SCIP_EXPORT SCIP_RETCODE SCIPgetRowprepRowCons( SCIP* scip, /**< SCIP data structure */ SCIP_ROW** row, /**< buffer to store pointer to new row */ SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ SCIP_CONS* cons /**< constraint */ ); /** generates a SCIP_ROW from a rowprep, setting its origin to given separator */ SCIP_EXPORT SCIP_RETCODE SCIPgetRowprepRowSepa( SCIP* scip, /**< SCIP data structure */ SCIP_ROW** row, /**< buffer to store pointer to new row */ SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */ SCIP_SEPA* sepa /**< separator */ ); /** @} */ #ifdef __cplusplus } #endif #endif /* __SCIP_PUB_MISC_ROWPREP_H__ */