Changeset 2411


Ignore:
Timestamp:
Mar 6, 2019 7:13:19 PM (8 months ago)
Author:
stefan
Message:

cleaned up basicmodelclasses

Location:
branches/gh-pages
Files:
2 added
1 edited

Legend:

Unmodified
Added
Removed
  • branches/gh-pages/basicmodelclasses.md

    r2410 r2411  
    1 Basic Model Classes {#basicmodelclasses}
     1Basic Model Classes
    22===================
    33
     
    2323user only need call `model.dual()` to invoke the dual simplex method.
    2424
    25 First Example {#firstexample}
     25First Example
    2626=============
    2727
    2828Below is our first CLP sample program. It is short enough to present in
    2929full (this code can be found in the CLP Samples directory, see
    30 [???](#moreexamples)). Most of the remaining examples in this Guide will
     30[here](./moresamples)). Most of the remaining examples in this Guide will
    3131take the form of small code fragments.
    3232
    33        
    34     // Copyright (C) 2002, International Business Machines
    35     // Corporation and others.  All Rights Reserved.
    36 
    37     #include "ClpSimplex.hpp"
    38     int main (int argc, const char *argv[])
    39     {
    40       ClpSimplex  model;
    41       int status;
    42       if (argc<2)
    43         status=model.readMps("../../Mps/Sample/p0033.mps");
    44       else
    45         status=model.readMps(argv[1]);
    46       if (!status) {
    47         model.primal();
    48       }
    49       return 0;
    50     }
    51          
    52      
     33```
     34// Copyright (C) 2002, International Business Machines
     35// Corporation and others.  All Rights Reserved.
     36
     37#include "ClpSimplex.hpp"
     38int main (int argc, const char *argv[])
     39{
     40  ClpSimplex  model;
     41  int status;
     42  if (argc<2)
     43    status=model.readMps("../../Mps/Sample/p0033.mps");
     44  else
     45    status=model.readMps(argv[1]);
     46  if (!status) {
     47    model.primal();
     48  }
     49  return 0;
     50}
     51```
    5352
    5453This sample program creates a `ClpSimplex` model, reads an MPS file, and
     
    5655program is easy to follow, but it is not terribly useful: it does not
    5756attempt to inspect the results of the solve. There are two main kinds of
    58 results: a \"status\" describing what happened to the model during the
     57results: a "status" describing what happened to the model during the
    5958solve, and arrays filled with solution values. Both will be addressed in
    6059this chapter.
    6160
    62 Getting at the Solution {#gettingsolution}
     61Getting at the Solution
    6362=======================
    6463
    6564It is often the case with CLP that there is more than one way to do
    66 something. This is a consequence of CLP\'s mixed heritage as a child of
     65something. This is a consequence of CLP's mixed heritage as a child of
    6766[OSL](http://www-306.ibm.com/software/data/bi/osl/) and a cousin of
    68 [OSI](http://www.coin-or.org/faqs.html#OSI). Finding the status of a
     67[OSI](http://www.github.com/coin-or/OSI). Finding the status of a
    6968model exemplifies this situation.
    7069
    71 The OSI way to check for optimality is to call model.isProvenOptimal().
     70The OSI way to check for optimality is to call `model.isProvenOptimal()`.
    7271Also available are `isProvenPrimalInfeasible()`,
    7372`isProvenDualInfeasible()`, `isPrimalObjectiveLimitReached()`,
     
    7978Similarly, to pick up the solution values, one could inhabit the
    8079virtuous world of OSI, or the not-quite-so-virtuous world of OSL and
    81 \"pure\" CLP. By this it is meant that const and non-const forms of
     80"pure" CLP. By this it is meant that const and non-const forms of
    8281arrays are used, respectively. It is easier to deal with the non-const
    8382versions, so most of the elaborate algorithms in CLP and its
    84 [Samples](#moresamples) use them.
    85 
    86   Purpose                      OSI-style (virtuous)                CLP-style (less virtuous)
    87   ---------------------------- ----------------------------------- -----------------------------------
    88   Primal column solution       `const double * getColSolution()`   `double * primalColumnSolution()`
    89   Dual row solution            `const double * getRowPrice()`      `double * dualColumnSolution()`
    90   Primal row solution          `const double * getRowActivity()`   `double * primalRowSolution()`
    91   Dual row solution            `const double * getReducedCost()`   `double * dualColumnSolution()`
    92   Number of rows in model      `int getNumRows()`                  `int numberRows()`
    93   Number of columns in model   `int getNumCols()`                  `int numberColumns()`
    94 
    95   : Methods for getting solution information
    96 
    97 The reader may have noted a preference for \"number\" over \"num\" and
    98 \"column\" over \"col\". This may be a reaction to when one of the
     83[Samples](./moresamples) use them.
     84
     85Methods for getting solution information:
     86
     87|Purpose                    | OSI-style (virtuous)               | CLP-style (less virtuous) |
     88|---------------------------|------------------------------------|-----------------------------------|
     89|Primal column solution     | `const double * getColSolution()`  | `double * primalColumnSolution()` |
     90|Dual row solution          | `const double * getRowPrice()`     | `double * dualColumnSolution()`   |
     91|Primal row solution        | `const double * getRowActivity()`  | `double * primalRowSolution()`    |
     92|Dual row solution          | `const double * getReducedCost()`  | `double * dualColumnSolution()`   |
     93|Number of rows in model    | `int getNumRows()`                 | `int numberRows()`                |
     94|Number of columns in model | `int getNumCols()`                 | `int numberColumns()`             |
     95
     96The reader may have noted a preference for "number" over "num" and
     97"column" over "col". This may be a reaction to when one of the
    9998authors was young and 5 or 6 letters was the maximum in FORTRAN for any
    10099name or to early days with OSL when seven characters were allowed but
    101 the first three had to be \"ekk\"!
    102 
    103 Using the above-listed functions, our [initial example](#firstexample)
     100the first three had to be "ekk"!
     101
     102Using the above-listed functions, our initial example
    104103might be continued as follows:
    105 
    106        
    107       int numberRows = model.numberRows();
    108       double * rowPrimal = model.primalRowSolution();
    109       double * rowDual = model.dualRowSolution();
    110 
    111       int iRow;
    112 
    113       for (iRow=0;iRow<numberRows;iRow++)   
    114         printf("Row %d, primal %g, dual %g\n",iRow,
    115         rowPrimal[iRow],rowDual[iRow]);
    116        
    117       int numberColumns = model.numberColumns();
    118       double * columnPrimal = model.primalColumnSolution();
    119       double * columnDual = model.dualColumnSolution();
    120 
    121       int iColumn;
    122 
    123       for (iColumn=0;iColumn<numberColumns;iColumn++)   
    124         printf("Column %d, primal %g, dual %g\n",iColumn,
    125         columnPrimal[iColumn],columnDual[iColumn]);
    126      
    127      
    128 
    129 This code sample would pretty-print information about the model\'s
     104```
     105int numberRows = model.numberRows();
     106double * rowPrimal = model.primalRowSolution();
     107double * rowDual = model.dualRowSolution();
     108
     109int iRow;
     110
     111for (iRow=0;iRow<numberRows;iRow++)
     112  printf("Row %d, primal %g, dual %g\n",iRow,rowPrimal[iRow],rowDual[iRow]);
     113
     114int numberColumns = model.numberColumns();
     115double * columnPrimal = model.primalColumnSolution();
     116double * columnDual = model.dualColumnSolution();
     117
     118int iColumn;
     119
     120for (iColumn=0;iColumn<numberColumns;iColumn++)
     121  printf("Column %d, primal %g, dual %g\n",iColumn,
     122  columnPrimal[iColumn],columnDual[iColumn]);
     123```
     124
     125This code sample would pretty-print information about the model's
    130126primal and dual solutions. How to additionally print row and column
    131 names is illustrated in the `defaults.cpp` file in the \"Samples\"
    132 directory (the Samples are properly addressed in [???](#moreexamples)).
     127names is illustrated in the `defaults.cpp` file in the "Samples"
     128directory (the Samples are properly addressed [here](./moresamples)).
    133129This sample is also useful as it explicitly performs default actions
    134130(e.g. it sets the primal feasiblility tolerance value to the default
     
    138134user might wish to perform. Apart from presolve we will only be looking
    139135at actions which can be performed when including the single header file
    140 `COIN/Clp/include/ClpSimplex.hpp`.
    141 
    142 Building and Modifying a Model {#buildandmodify}
     136`ClpSimplex.hpp`.
     137
     138Building and Modifying a Model
    143139==============================
    144140
     
    154150size of a model. The simplest is by the use of the method
    155151`resize(newNumberRows,newNumberColumns)` - this will either truncate the
    156 model or add \"default\" rows or columns - a default row has lower bound
     152model or add "default" rows or columns - a default row has lower bound
    157153of -infinity and upper bound of +infinity, while a default column has
    158154zero cost, zero lower bound and an upper bound of +infinity.
     
    186182was stated as for minimization; signs are reversed for maximization.)
    187183
    188 Some Useful Set and Get Methods {#setsandgets}
     184Some Useful Set and Get Methods
    189185===============================
    190186
    191   Method(s)                                                                                                                                                                                                                   Description
    192   --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    193   `setMaximumIterations(int value)` `int maximumIterations()` `setMaximumSeconds(double value)` `double maximumIterations()`                                                                                                  These methods tell CLP to stop after a given number of iterations or seconds (and returns these values).
    194   `double objectiveValue()`                                                                                                                                                                                                   This method returns the objective value.
    195   `const double * getObjCoefficients()` `double * objective()`                                                                                                                                                                These methods return the objective coefficients.
    196   `const double * getRowLower()` `double * rowLower()` `const double * getRowUpper()` `double * rowUpper()` `const double * getColLower()` `double * columnLower()` `const double * getColUpper()` `double * columnUpper()`   These methods give lower and upper bounds on row and column activities.
    197   `double * infeasibilityRay()` `double * unboundedRay()`                                                                                                                                                                     If the problem was primal or dual infeasible, these methods will give a pointer to a ray proving infeasibility.
    198   `CoinPackMatrix * matrix()`                                                                                                                                                                                                 There are more options as the user has great flexibility in how the problem matrix is stored, but the default matrix class is `CoinPackedMatrix` (see [???](#matrixclasses)). So we have that this method returns a pointer to a `CoinPackedMatrix` which can be further manipulated.
    199   `CoinBigIndex getNumElements()` [^1]                                                                                                                                                                                        Returns the number of elements in the problem matrix.
    200   `void setOptimizationDirection(double value)` `double optimizationDirection()`                                                                                                                                              These methods set and get the objective sense. The parameter `value` should be +1 to minimize, -1 to maximize, and 0 to ignore.
    201 
    202   : Some Useful Set and Get Methods
    203 
    204 Simplex-specific Methods {#simplexspecific}
     187| Method(s)                                                                                                                                                                                                                 | Description |
     188|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
     189| `setMaximumIterations(int value)` `int maximumIterations()` `setMaximumSeconds(double value)` `double maximumIterations()`                                                                                                | These methods tell CLP to stop after a given number of iterations or seconds (and returns these values). |
     190| `double objectiveValue()`                                                                                                                                                                                                 | This method returns the objective value. |
     191| `const double * getObjCoefficients()` `double * objective()`                                                                                                                                                              | These methods return the objective coefficients. |
     192| `const double * getRowLower()` `double * rowLower()` `const double * getRowUpper()` `double * rowUpper()` `const double * getColLower()` `double * columnLower()` `const double * getColUpper()` `double * columnUpper()` | These methods give lower and upper bounds on row and column activities. |
     193| `double * infeasibilityRay()` `double * unboundedRay()`                                                                                                                                                                   | If the problem was primal or dual infeasible, these methods will give a pointer to a ray proving infeasibility. |
     194| `CoinPackMatrix * matrix()`                                                                                                                                                                                               | There are more options as the user has great flexibility in how the problem matrix is stored, but the default matrix class is `CoinPackedMatrix` (see Matrix Classes [here](./notsobasic)). So we have that this method returns a pointer to a `CoinPackedMatrix` which can be further manipulated. |
     195| `CoinBigIndex getNumElements()`                                                                                                                                                                                           | Returns the number of elements in the problem matrix. `CoinBigIndex` is a `typedef` which in most cases is the same as `int`. |
     196| `void setOptimizationDirection(double value)` `double optimizationDirection()`                                                                                                                                            | These methods set and get the objective sense. The parameter `value` should be +1 to minimize, -1 to maximize, and 0 to ignore. |
     197
     198Simplex-specific Methods
    205199========================
    206200
    207201Some of the most commonly-used methods when working with Simplex are
    208 listed in the table below.
    209 
    210   Method(s)                                                           Description
    211   ------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
    212   `primal(int mode=0)`                                                This applies the primal algorithm. If `mode` is set to the default of 0, then the method uses the status variables to determine basis and solution. If `mode` is 1 then the method does a values pass so variables not in basis are given their current values and one pass of variables is done to clean up the basis with an equal or better objective value.
    213   `dual(int mode=0)`                                                  This applies the dual algorithm. if `mode` is set to the default of 0, then the method uses the status variables to determine basis and solution. If `mode` is 1 then the method uses input duals and does a values pass so one pass of basic variables is done to clean up the duals with an equal or better objective value.
    214   `scaling(int mode=1)`                                               This method toggles scaling on (`mode` set to 1) and off (`mode` set to 0).
    215   `int crash(double gap,int mode)`                                    This method attemps to improve on an all slack basis. For dual this will move variables to the dual feasible bound if the gap between bounds is less than `gap`. Setting `mode` to 0 guesses which algorithm is better, while a value of 1 or 2 will result in more work being done. The return code is 0 if the basis was not slacks in first case, it is negative if dual is preferred or positive if primal. ±1 means an all slack basis seemed best, while ±2 means some work was done.
    216   `perturb(int mode)`                                                 This method toggles perturbation on (`mode` set to 1) and off (`mode` set to 0). It should be considered a work in progress, although on some problems it gives very good results.
    217   `factorizationFrequency()` `setFactorizationFrequency(int value)`   These are \"get\" and \"set\" methods for the basis matrix factorization frequency. The default is to refactor every 200 iterations, but it may make more sense to use something such as 100 + the number of rows divided by 50.
    218   `dualBound()` `setDualBound(double value)`                          These are \"get\" and \"set\" methods for the \"dual bound\". The CLP dual algorithm declares all problems to be dual feasible by putting non-basic variables to correct bounds for the reduced cost. If the gap between the bounds is too big then it pretends the gap is only the value specified by this set method. In essence, this gives a composite dual rather than a pure Phase I- Phase II method.
    219   `infeasibilityCost()` `setInfeasibilityCost(double value)`          These are the primal analogs to the \"dual bound\" methods.
    220   `numberPrimalInfeasibilities()` `sumPrimalInfeasibilities()`        After a solve, there may be infeasibilities. These methods serve to check for said infeasibilities. One could check the solution explicitly as well. For a code fragement illustrating this, see [example\_title](#presolveexample).
    221 
    222   : Common Simplex-specific methods
     202listed in the following table:
     203
     204| Method(s)                                                          | Description
     205| -------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
     206| `primal(int mode=0)`                                               | This applies the primal algorithm. If `mode` is set to the default of 0, then the method uses the status variables to determine basis and solution. If `mode` is 1 then the method does a values pass so variables not in basis are given their current values and one pass of variables is done to clean up the basis with an equal or better objective value.
     207| `dual(int mode=0)`                                                 | This applies the dual algorithm. if `mode` is set to the default of 0, then the method uses the status variables to determine basis and solution. If `mode` is 1 then the method uses input duals and does a values pass so one pass of basic variables is done to clean up the duals with an equal or better objective value.
     208| `scaling(int mode=1)`                                              | This method toggles scaling on (`mode` set to 1) and off (`mode` set to 0).
     209| `int crash(double gap,int mode)`                                   | This method attemps to improve on an all slack basis. For dual this will move variables to the dual feasible bound if the gap between bounds is less than `gap`. Setting `mode` to 0 guesses which algorithm is better, while a value of 1 or 2 will result in more work being done. The return code is 0 if the basis was not slacks in first case, it is negative if dual is preferred or positive if primal. ±1 means an all slack basis seemed best, while ±2 means some work was done.
     210| `perturb(int mode)`                                                | This method toggles perturbation on (`mode` set to 1) and off (`mode` set to 0). It should be considered a work in progress, although on some problems it gives very good results.
     211| `factorizationFrequency()` `setFactorizationFrequency(int value)`  | These are "get" and "set" methods for the basis matrix factorization frequency. The default is to refactor every 200 iterations, but it may make more sense to use something such as 100 + the number of rows divided by 50.
     212| `dualBound()` `setDualBound(double value)`                         | These are "get" and "set" methods for the "dual bound". The CLP dual algorithm declares all problems to be dual feasible by putting non-basic variables to correct bounds for the reduced cost. If the gap between the bounds is too big then it pretends the gap is only the value specified by this set method. In essence, this gives a composite dual rather than a pure Phase I- Phase II method.
     213| `infeasibilityCost()` `setInfeasibilityCost(double value)`         | These are the primal analogs to the "dual bound" methods.
     214| `numberPrimalInfeasibilities()` `sumPrimalInfeasibilities()`       | After a solve, there may be infeasibilities. These methods serve to check for said infeasibilities. One could check the solution explicitly as well. For a code fragement illustrating this, see the following example. |
    223215
    224216Presolve
    225217========
    226218
    227 The header file for the use of CLP\'s presolve functionality is
    228 `COIN/Clp/include/Presolve.hpp`. The sample program below illustrates
    229 some of the possibilities offered by CLP\'s presolve:
    230 
    231     #include "ClpSimplex.hpp"
    232     #include "ClpPresolve.hpp"
    233     int main (int argc, const char *argv[])
    234     {
    235       ClpSimplex model;
    236       model.readMps("../../Mps/Sample/p0033.mps"); // initialized by readMps or whatever
    237       ClpPresolve presolveInfo;
    238       ClpSimplex * presolvedModel = presolveInfo.presolvedModel(model);
    239       // at this point we have original model and a new model.  The  information
    240       // on the operations done is in presolveInfo
    241       if (presolvedModel) {
    242         // was not found to be infeasible - so lets solve
    243         // if presolvedModel was NULL then it was primal infeasible and ...
    244         presolvedModel->dual(); // or whatever else we wish to do
    245         presolveInfo.postsolve(true);  // the true updates status arrays in original       
    246         /* If the presolved model was optimal then so should the
    247            original be.           
    248            We can use checkSolution and test feasibility */
    249         model.checkSolution();         
    250         if (model.numberDualInfeasibilities()||
    251         model.numberPrimalInfeasibilities())
    252           printf("%g dual %g(%d) Primal %g(%d)\n",
    253              model.objectiveValue(),
    254              model.sumDualInfeasibilities(),
    255              model.numberDualInfeasibilities(),
    256              model.sumPrimalInfeasibilities(),
    257              model.numberPrimalInfeasibilities());
    258         // Due to tolerances we can not guarantee that so you may wish to throw in
    259         model.primal(1);
    260       }
    261     }   
    262      
     219The header file for the use of CLP's presolve functionality is
     220`Presolve.hpp`. The sample program below illustrates
     221some of the possibilities offered by CLP's presolve:
     222```
     223#include "ClpSimplex.hpp"
     224#include "ClpPresolve.hpp"
     225
     226int main (int argc, const char *argv[])
     227{
     228  ClpSimplex model;
     229  model.readMps("../../Data/Sample/p0033.mps"); // initialized by readMps or whatever
     230  ClpPresolve presolveInfo;
     231  ClpSimplex * presolvedModel = presolveInfo.presolvedModel(model);
     232  // at this point we have original model and a new model.  The  information
     233  // on the operations done is in presolveInfo
     234  if (presolvedModel) {
     235    // was not found to be infeasible - so lets solve
     236    // if presolvedModel was NULL then it was primal infeasible and ...
     237    presolvedModel->dual(); // or whatever else we wish to do
     238    presolveInfo.postsolve(true);  // the true updates status arrays in original
     239    /* If the presolved model was optimal then so should the original be.
     240       We can use checkSolution and test feasibility */
     241    model.checkSolution();
     242    if (model.numberDualInfeasibilities()|| model.numberPrimalInfeasibilities())
     243      printf("%g dual %g(%d) Primal %g(%d)\n",
     244        model.objectiveValue(),
     245        model.sumDualInfeasibilities(),
     246        model.numberDualInfeasibilities(),
     247        model.sumPrimalInfeasibilities(),
     248        model.numberPrimalInfeasibilities());
     249    // Due to tolerances we can not guarantee that so you may wish to throw in
     250    model.primal(1);
     251  }
     252}
     253```
    263254
    264255Presolve has a few more options which can be found in the header file,
     
    266257row and column names.
    267258
    268 Status Array {#statusarray}
     259Status Array
    269260============
    270261
     
    273264Nevertheless, for completeness the status of a variable can be found and
    274265set as shown below. The possible state of a variable are listed in the
    275 following table (each may have to be preceded by ClpSimplex::):
    276 
    277   `Status`[^2]     Description
    278   ---------------- ---------------------------------------
    279   `basic`          In basis
    280   `isFree`         Not in basis, has infinite bounds
    281   `isFixed`        Not in basis, bounds are equal
    282   `atUpperBound`   At upper bound, not in basis
    283   `atLowerBound`   At lower bound, not in basis
    284   `superBasic`     Between bounds, but not basic or free
    285 
    286   : Possible states of a variable
     266following table (each may have to be preceded by `ClpSimplex::`):
     267
     268| Status          | Description |
     269|-----------------|--------------------------------------- |
     270| `basic`         | In basis |
     271| `isFree`        | Not in basis, has infinite bounds |
     272| `isFixed`       | Not in basis, bounds are equal |
     273| `atUpperBound`  | At upper bound, not in basis |
     274| `atLowerBound`  | At lower bound, not in basis |
     275| `superBasic`    | Between bounds, but not basic or free |
    287276
    288277To get or set the status of a variable is a simple task:
    289 
    290       // Get row status...
    291       Status status=model.getRowStatus(sequenceNumber)
    292       // ... or get column status.
    293       Status status=model.getColumnStatus(sequenceNumber)
    294       // Set row status to basic (for example)...
    295       model.setRowStatus(sequenceNumber,ClpSimplex::basic)
    296       // ... or column status to basic.
    297       model.setColumnStatus(sequenceNumber,ClpSimplex::basic)
    298      
    299 
    300 [^1]: `CoinBigIndex` is a `typedef` which in most cases is the same as
    301     `int`.
    302 
    303 [^2]: `Status` is an enumeration.
     278```
     279// Get row status...
     280Status status=model.getRowStatus(sequenceNumber)
     281// ... or get column status.
     282Status status=model.getColumnStatus(sequenceNumber)
     283// Set row status to basic (for example)...
     284model.setRowStatus(sequenceNumber,ClpSimplex::basic)
     285// ... or column status to basic.
     286model.setColumnStatus(sequenceNumber,ClpSimplex::basic)
     287```
Note: See TracChangeset for help on using the changeset viewer.