diff options
Diffstat (limited to 'thirdparty/linux/include/coin1/OsiPresolve.hpp')
| -rw-r--r-- | thirdparty/linux/include/coin1/OsiPresolve.hpp | 252 |
1 files changed, 252 insertions, 0 deletions
diff --git a/thirdparty/linux/include/coin1/OsiPresolve.hpp b/thirdparty/linux/include/coin1/OsiPresolve.hpp new file mode 100644 index 0000000..9ec3d2a --- /dev/null +++ b/thirdparty/linux/include/coin1/OsiPresolve.hpp @@ -0,0 +1,252 @@ +// Copyright (C) 2003, International Business Machines +// Corporation and others. All Rights Reserved. +// This code is licensed under the terms of the Eclipse Public License (EPL). + +#ifndef OsiPresolve_H +#define OsiPresolve_H +#include "OsiSolverInterface.hpp" + +class CoinPresolveAction; +#include "CoinPresolveMatrix.hpp" + + +/*! \class OsiPresolve + \brief OSI interface to COIN problem simplification capabilities + + COIN provides a number of classes which implement problem simplification + algorithms (CoinPresolveAction, CoinPrePostsolveMatrix, and derived + classes). The model of operation is as follows: + <ul> + <li> + Create a copy of the original problem. + </li> + <li> + Subject the copy to a series of transformations (the <i>presolve</i> + methods) to produce a presolved model. Each transformation is also + expected to provide a method to reverse the transformation (the + <i>postsolve</i> method). The postsolve methods are collected in a + linked list; the postsolve method for the final presolve transformation + is at the head of the list. + </li> + <li> + Hand the presolved problem to the solver for optimization. + </li> + <li> + Apply the collected postsolve methods to the presolved problem + and solution, restating the solution in terms of the original problem. + </li> + </ul> + + The COIN presolve algorithms are unaware of OSI. The OsiPresolve class takes + care of the interface. Given an OsiSolverInterface \c origModel, it will take + care of creating a clone properly loaded with the presolved problem and ready + for optimization. After optimization, it will apply postsolve + transformations and load the result back into \c origModel. + + Assuming a problem has been loaded into an + \c OsiSolverInterface \c origModel, a bare-bones application looks like this: + \code + OsiPresolve pinfo ; + OsiSolverInterface *presolvedModel ; + // Return an OsiSolverInterface loaded with the presolved problem. + presolvedModel = pinfo.presolvedModel(*origModel,1.0e-8,false,numberPasses) ; + presolvedModel->initialSolve() ; + // Restate the solution and load it back into origModel. + pinfo.postsolve(true) ; + delete presolvedModel ; + \endcode +*/ + + + +class OsiPresolve { +public: + /// Default constructor (empty object) + OsiPresolve(); + + /// Virtual destructor + virtual ~OsiPresolve(); + + /*! \brief Create a new OsiSolverInterface loaded with the presolved problem. + + This method implements the first two steps described in the class + documentation. It clones \c origModel and applies presolve + transformations, storing the resulting list of postsolve + transformations. It returns a pointer to a new OsiSolverInterface loaded + with the presolved problem, or NULL if the problem is infeasible or + unbounded. If \c keepIntegers is true then bounds may be tightened in + the original. Bounds will be moved by up to \c feasibilityTolerance to + try and stay feasible. When \c doStatus is true, the current solution will + be transformed to match the presolved model. + + This should be paired with postsolve(). It is up to the client to + destroy the returned OsiSolverInterface, <i>after</i> calling postsolve(). + + This method is virtual. Override this method if you need to customize + the steps of creating a model to apply presolve transformations. + + In some sense, a wrapper for presolve(CoinPresolveMatrix*). + */ + virtual OsiSolverInterface *presolvedModel(OsiSolverInterface & origModel, + double feasibilityTolerance=0.0, + bool keepIntegers=true, + int numberPasses=5, + const char * prohibited=NULL, + bool doStatus=true, + const char * rowProhibited=NULL); + + /*! \brief Restate the solution to the presolved problem in terms of the + original problem and load it into the original model. + + postsolve() restates the solution in terms of the original problem and + updates the original OsiSolverInterface supplied to presolvedModel(). If + the problem has not been solved to optimality, there are no guarantees. + If you are using an algorithm like simplex that has a concept of a basic + solution, then set updateStatus + + The advantage of going back to the original problem is that it + will be exactly as it was, <i>i.e.</i>, 0.0 will not become 1.0e-19. + + Note that if you modified the original problem after presolving, then you + must ``undo'' these modifications before calling postsolve(). + + In some sense, a wrapper for postsolve(CoinPostsolveMatrix&). + */ + virtual void postsolve(bool updateStatus=true); + + /*! \brief Return a pointer to the presolved model. */ + OsiSolverInterface * model() const; + + /// Return a pointer to the original model + OsiSolverInterface * originalModel() const; + + /// Set the pointer to the original model + void setOriginalModel(OsiSolverInterface *model); + + /// Return a pointer to the original columns + const int * originalColumns() const; + + /// Return a pointer to the original rows + const int * originalRows() const; + + /// Return number of rows in original model + inline int getNumRows() const + { return nrows_;} + + /// Return number of columns in original model + inline int getNumCols() const + { return ncols_;} + + /** "Magic" number. If this is non-zero then any elements with this value + may change and so presolve is very limited in what can be done + to the row and column. This is for non-linear problems. + */ + inline void setNonLinearValue(double value) + { nonLinearValue_ = value;} + inline double nonLinearValue() const + { return nonLinearValue_;} + /*! \brief Fine control over presolve actions + + Set/clear the following bits to allow or suppress actions: + - 0x01 allow duplicate column processing on integer columns + and dual stuff on integers + - 0x02 switch off actions which can change +1 to something else + (doubleton, tripleton, implied free) + - 0x04 allow transfer of costs from singletons and between integer + variables (when advantageous) + - 0x08 do not allow x+y+z=1 transform + - 0x10 allow actions that don't easily unroll + - 0x20 allow dubious gub element reduction + + GUB element reduction is only partially implemented in CoinPresolve (see + gubrow_action) and willl cause an abort at postsolve. It's not clear + what's meant by `dual stuff on integers'. + -- lh, 110605 -- + */ + inline void setPresolveActions(int action) + { presolveActions_ = (presolveActions_&0xffff0000)|(action&0xffff);} + +private: + /*! Original model (solver interface loaded with the original problem). + + Must not be destroyed until after postsolve(). + */ + OsiSolverInterface * originalModel_; + + /*! Presolved model (solver interface loaded with the presolved problem) + + Must be destroyed by the client (using delete) after postsolve(). + */ + OsiSolverInterface * presolvedModel_; + + /*! "Magic" number. If this is non-zero then any elements with this value + may change and so presolve is very limited in what can be done + to the row and column. This is for non-linear problems. + One could also allow for cases where sign of coefficient is known. + */ + double nonLinearValue_; + + /// Original column numbers + int * originalColumn_; + + /// Original row numbers + int * originalRow_; + + /// The list of transformations applied. + const CoinPresolveAction *paction_; + + /*! \brief Number of columns in original model. + + The problem will expand back to its former size as postsolve + transformations are applied. It is efficient to allocate data structures + for the final size of the problem rather than expand them as needed. + */ + int ncols_; + + /*! \brief Number of rows in original model. */ + int nrows_; + + /*! \brief Number of nonzero matrix coefficients in the original model. */ + CoinBigIndex nelems_; + + /** Whether we want to skip dual part of presolve etc. + 1 bit allows duplicate column processing on integer columns + and dual stuff on integers + 4 transfers costs to integer variables + */ + int presolveActions_; + /// Number of major passes + int numberPasses_; + +protected: + /*! \brief Apply presolve transformations to the problem. + + Handles the core activity of applying presolve transformations. + + If you want to apply the individual presolve routines differently, or + perhaps add your own to the mix, define a derived class and override + this method + */ + virtual const CoinPresolveAction *presolve(CoinPresolveMatrix *prob); + + /*! \brief Reverse presolve transformations to recover the solution + to the original problem. + + Handles the core activity of applying postsolve transformations. + + Postsolving is pretty generic; just apply the transformations in reverse + order. You will probably only be interested in overriding this method if + you want to add code to test for consistency while debugging new presolve + techniques. + */ + virtual void postsolve(CoinPostsolveMatrix &prob); + + /*! \brief Destroys queued postsolve actions. + + <i>E.g.</i>, when presolve() determines the problem is infeasible, so that + it will not be necessary to actually solve the presolved problem and + convert the result back to the original problem. + */ + void gutsOfDestroy(); +}; +#endif |