CLP User Guide

The COIN Linear Program code or CLP is an open-source simplex solver written in C++. It is primarily meant to be used as a callable library, but a basic, stand-alone executable version is also available.

There are a number of resources available to help new CLP users get started. This document is designed to be used in conjunction with the files in the Samples subdirectory of the main CLP directory (COIN/Clp/Samples). The Samples illustrate how to use CLP and may also serve as useful starting points for user projects. In the rare event that either this document or the available Doxygen content conflicts with the observed behavior of the source code, the comments in the header files, found in COIN/Clp/include, are the ultimate reference.

CLP is written in C++, so it is expected that users of CLP will be writing C++ programs which use CLP as a library. Thus a working knowledge of C++, including basic object-oriented programming terminology is assumed in this document. In addition, the user should be familiar with the fundamental concepts of Linear Programming.

The basic CLP model class hierarchy is simple. The top three levels of the hierarchy are depicted in the figure below. The first two levels (i.e. ClpModel, ClpSimplex, ClpInterior) contain all the problem data which define a model (that is, a problem instance). The third level contains most of the algorithmic aspects of CLP. There is a fourth level (for models with more general objectives than linear ones), but a description of it is beyond the current scope of this document.

Most Simplex users need only concern themselves with the classes ClpModel and ClpSimplex. There are algorithm-specific classes which inherit from ClpSimplex (e.g. ClpSimplexDual and ClpSimplexPrimal), but they have no member data and rarely need be visible to the user. These classes are cast at algorithm time. So, for example, after instantiating an object model of type ClpSimplex, a user only need call model.dual() to invoke the dual simplex method.

Below is our first CLP sample program. It is short enough to present in full (this code can be found in the CLP Samples directory, see Chapter 4, More Samples ). Most of the remaining examples in this Guide will take the form of small code fragments.

    
// Copyright (C) 2002, International Business Machines
// Corporation and others.  All Rights Reserved.

#include "ClpSimplex.hpp"
int main (int argc, const char *argv[])
{
  ClpSimplex  model;
  int status;
  if (argc<2)
    status=model.readMps("../../Mps/Sample/p0033.mps");
  else
    status=model.readMps(argv[1]);
  if (!status) {
    model.primal();
  }
  return 0;
} 
     
  

This sample program creates a ClpSimplex model, reads an MPS file, and if there are no errors, solves it using the primal algorithm. The program is easy to follow, but it is not terribly useful: it does not attempt to inspect the results of the solve. There are two main kinds of results: a "status" describing what happened to the model during the solve, and arrays filled with solution values. Both will be addressed in this chapter.

It is often the case with CLP that there is more than one way to do something. This is a consequence of CLP's mixed heritage as a child of OSL and a cousin of OSI. Finding the status of a model exemplifies this situation.

The OSI way to check for optimality is to call model.isProvenOptimal(). Also available are isProvenPrimalInfeasible(), isProvenDualInfeasible(), isPrimalObjectiveLimitReached(), isDualObjectiveLimitReached(), isIterationLimitReached() or the feared isAbandoned(). Should one prefer the OSL way of doing things, model.status() returns as it would in OSL, so 0 means optimal, 1 means primal infeasible etc.

Similarly, to pick up the solution values, one could inhabit the virtuous world of OSI, or the not-quite-so-virtuous world of OSL and "pure" CLP. By this it is meant that const and non-const forms of arrays are used, respectively. It is easier to deal with the non-const versions, so most of the elaborate algorithms in CLP and its Samples use them.

The reader may have noted a preference for "number" over "num" and "column" over "col". This may be a reaction to when one of the authors was young and 5 or 6 letters was the maximum in FORTRAN for any name or to early days with OSL when seven characters were allowed but the first three had to be "ekk"!

Using the above-listed functions, our initial example might be continued as follows:

    
  int numberRows = model.numberRows();
  double * rowPrimal = model.primalRowSolution();
  double * rowDual = model.dualRowSolution();

  int iRow;

  for (iRow=0;iRow<numberRows;iRow++) 	
    printf("Row %d, primal %g, dual %g\n",iRow,
	rowPrimal[iRow],rowDual[iRow]);
	
  int numberColumns = model.numberColumns();
  double * columnPrimal = model.primalColumnSolution();
  double * columnDual = model.dualColumnSolution();

  int iColumn;

  for (iColumn=0;iColumn<numberColumns;iColumn++) 	
    printf("Column %d, primal %g, dual %g\n",iColumn,
	columnPrimal[iColumn],columnDual[iColumn]);
  
  

This code sample would pretty-print information about the model's primal and dual solutions. How to additionally print row and column names is illustrated in the defaults.cpp file in the "Samples" directory (the Samples are properly addressed in Chapter 4, More Samples ). This sample is also useful as it explicitly performs default actions (e.g. it sets the primal feasiblility tolerance value to the default value).

The remainder of this chapter will show more of the basic CLP tasks a user might wish to perform. Apart from presolve we will only be looking at actions which can be performed when including the single header file COIN/Clp/include/ClpSimplex.hpp.

Rather than reading a model from an MPS file we can load a model from arrays in memory. There are various loadProblem methods which are similar to those in OSI. It is easy to add more such methods to CLP if the need arises.

We can copy in integer information by copyInIntegerInformation(const char * array) where array is 0 or 1 to say integer and we can drop existing information by deleteIntegerInformation(). There are various ways of changing the size of a model. The simplest is by the use of the method resize(newNumberRows,newNumberColumns) - this will either truncate the model or add "default" rows or columns - a default row has lower bound of -infinity and upper bound of +infinity, while a default column has zero cost, zero lower bound and an upper bound of +infinity.

Normally we would use deleteRows, addRows, deleteColumns and addColumns, where the add methods will also add in the elements. A potentially very useful way of modifying a model is strictly a constructor. Given a large model and a list of rows and a list of columns it constructs the model as a subset of the large model. It is possible to change the order of the columns/rows and to duplicate columns/rows. So a list of columns 4,4,1,0 will create a new model where the first two columns are copies of column 4 in original model and the next two are the first two of original model in reverse order. This can be useful to form a model with piecewise linear costs by duplicating columns and then modifying bounds and costs.

There are set and get methods for tolerances, for example, double primalTolerance() and setPrimalTolerance(double). Assuming that one has a minimization problem, an individual variable is deemed primal feasible if it is less than the tolerance referred to by these methods below its lower bound and less than it above its upper bound. Similarly for dual tolerances, a variable is deemed to be dual feasible if its reduced cost is greater than minus the tolerance or its distance to the upper bound is less than primal tolerance and the reduced cost is less than plus the tolerance or the distance to lower bound is less than primal tolerance. In short, this is complementarity conditions adadpted for tolerances and simple lower and upper bounds.(Note that the above was stated as for minimization; signs are reversed for maximization.)

Some of the most commonly-used methods when working with Simplex are listed in the table below.

The header file for the use of CLP's presolve functionality is COIN/Clp/include/Presolve.hpp. The sample program below illustrates some of the possibilities offered by CLP's presolve:

#include "ClpSimplex.hpp"
#include "ClpPresolve.hpp"
int main (int argc, const char *argv[])
{
  ClpSimplex model; 
  model.readMps("../../Mps/Sample/p0033.mps"); // initialized by readMps or whatever 
  ClpPresolve presolveInfo; 
  ClpSimplex * presolvedModel = presolveInfo.presolvedModel(model); 
  // at this point we have original model and a new model.  The  information
  // on the operations done is in presolveInfo 
  if (presolvedModel) { 
    // was not found to be infeasible - so lets solve 
    // if presolvedModel was NULL then it was primal infeasible and ... 
    presolvedModel->dual(); // or whatever else we wish to do 
    presolveInfo.postsolve(true);  // the true updates status arrays in original       
    /* If the presolved model was optimal then so should the 
       original be.           
       We can use checkSolution and test feasibility */ 
    model.checkSolution();         
    if (model.numberDualInfeasibilities()|| 
	model.numberPrimalInfeasibilities()) 
      printf("%g dual %g(%d) Primal %g(%d)\n", 
	     model.objectiveValue(), 
	     model.sumDualInfeasibilities(), 
	     model.numberDualInfeasibilities(), 
	     model.sumPrimalInfeasibilities(), 
	     model.numberPrimalInfeasibilities()); 
    // Due to tolerances we can not guarantee that so you may wish to throw in
    model.primal(1); 
  }
}   
  

Presolve has a few more options which can be found in the header file, for example whether to treat as an integer problem or whether to keep row and column names.

The astute reader may have noticed that the status array has been mentioned once or twice. The beginning user will not need to look at it Nevertheless, for completeness the status of a variable can be found and set as shown below. The possible state of a variable are listed in the following table (each may have to be preceded by ClpSimplex::):

To get or set the status of a variable is a simple task:

  // Get row status...
  Status status=model.getRowStatus(sequenceNumber)
  // ... or get column status.
  Status status=model.getColumnStatus(sequenceNumber)
  // Set row status to basic (for example)...
  model.setRowStatus(sequenceNumber,ClpSimplex::basic)
  // ... or column status to basic.
  model.setColumnStatus(sequenceNumber,ClpSimplex::basic)
  

In the dual algorithm, any infeasible basic variable may be chosen to leave the basis. Similarly in the primal algorithm, any non-basic variable with a "bad" reduced cost may be chosen to enter the basis. This choice is probably the most important factor in determining the number of iterations it will take to solve a problem. Clp provides a abstract base class for each case and then instances of each. It is relatively simple for an advanced user to create new instances.

For the dual method the base class is ClpDualRowPivot. The two existing instances are ClpDualRowDantzig and ClpDualRowSteepest. The Dantzig version implements the "standard" pivot rule: choose the most violated basic variable. It is easily dominated by the Steepest instance which should normally be used. The default is to use un-initialized weights where the initial weight for each basic variable is 1.0. If an all-slack basis is being used then these are the correct weights. To use a version which calculates the weights, create an instance and pass it to ClpSimplex model as in the following code fragment:

  ClpDualRowSteepest steep(1); // 0 uninitialized, 1 compute weights
  model.setDualRowPivotAlgorithm(steep);
  

Similarly for the primal method the base class is ClpPrimalColumnPivot. The two existing instances are ClpPrimalColumnDantzig and ClpPrimalColumnSteepest. The Dantzig version implements "standard" pivot rule: choose the most "violated" non-basic variable. It is dominated by the Steepest instance which should normally be used. The default is to use exact Devex where the initial weight for each non-basic variable is 1.0. Unlike for the dual, this is never the same as normal steepest edge. To use a version which does steepest edge create an instance and pass it to ClpSimplex model as in the following code fragment:

  ClpPrimalColumnSteepest steep(1); // 0 devex, 1 steepest
  model.setPrimalColumnPivotAlgorithm(steep);
  

The partial pricing scheme (for long, thin problems) currently does not exist. This could be implemented by anyone who is interested.

The next abstract class of interest is ClpMatrixBase. CLP encapsulates its knowledge of how a matrix is stored in this class. The default instance of this is the ClpPackedMatrix class. This is identical in format to CoinPackedMatrix. Below is a diagram summarizing the hierarchy of the most important matrix classes:

The important new methods implemented are for filling a basis, checking validity of elements and faster "times" and "transposeTimes" when the input array is sparse and/or we have a row copy of the matrix. Advanced users should note that not all methods have to be implemented. In particular, scaling need not be implemented and reverseOrderedCopy can return NULL if a row copy does not make sense.

In addition to the default class, there are two others at present: ClpPlusMinusOneMatrix and ClpNetworkMatrix. As the name implies, the first one is useful when all elements are ±1. In this case multiplies are not needed and more importantly less memory is used and there are fewer cache misses. A class for a matrix where all elements are +1 would be trivial to create. If there were fewer than 64000 rows one could even store row indices as shorts etc.

The use of ClpPlusMinusOneMatrix involves some work as one cannot simply read-in an MPS file. The key is to use loadProblem to pass in a matrix. So if matrix was a CoinPackedMatrix one could do the following:

  ClpPlusMinusOneMatrix plusMinus(matrix);
  assert (plusMinus.getIndices()); // would be zero if not +- one
  model.loadProblem(plusMinus,
    lowerColumn,upperColumn,objective,
    lower,upper);
  

ClpNetworkMatrix is similar, but represents a network, thus may only have one element per column. Fortunately, using is is very easy. Given head and tail, one could do the following:

  ClpNetworkMatrix network(numberColumns,head,tail);
  model.loadProblem(network,
    lowerColumn,upperColumn,objective,
    lower,upper);
  

Actual code is in COIN/Clp/Test/unitTest.cpp. A quick glance at the output of this program shows that use of ClpNetworkMatrix gives much faster run times. This is not because of storage issues, but because CLP recognizes the network and uses a network basis factorization which is much faster. However, in this mode CLP is not a genuine network code as it does not take full advantage of the structure by combining operations but it does have the advantage of flexibility.

Other instances are possible. In particular, it should be possible to use the abstract class for column generation or for dynamic matrices which change over time. Minor modifications may be needed but it should work quite smoothly (there is already a dummy "refresh" method which would be used).

Strictly speaking, message handling is a general COIN topic, but it won't hurt to repeat a few important things here.

A simple user you may wish to turn off some output. This is done with model.setLogLevel(int value) where 0 gives nothing and each increase in value switches on more messages. See ClpMessage.cpp, CoinMessage.cpp and Chapter 6, Messages to see which messages are at which level. A more sophisticated user may wish to handle messages in a different way. This is done using passInMessageHandler with a pointer to a handler of the user's own design. The simplest case would be to use the default handler but use a constructor which writes to file. The code would be:

  FILE * fp; // assumed open
  CoinMessageHandler handler(fp);
  model.passInMessageHandler(&handler);
  

A still more sophisticated use would be to write a class derived from CoinMessageHandler and then override the print method. Below follows an example which would print only a message for optimality (or infeasibility):

  class DerivedHandler :
   public CoinMessageHandler {
   public:
     virtual int print() ;
   };


   int DerivedHandler::print()
   {
     if (currentSource()=="Clp") {
       if (currentMessage().externalNumber()>=0
       && currentMessage().externalNumber()<4) { 
         // finished
         return CoinMessageHandler::print(); // print
       }
     }
     return 0;
   }
  

The CLP dsitribution includes a number of .cpp sample files. Users are encouraged to use them as starting points for their own CLP projects. The files can be found in the COIN/Clp/Samples/ directory. For the latest information on compiling and running these samples, please see the file COIN/Clp/Samples/INSTALL. Below is a list of some of the most useful sample files with a short description for each file.

The remaining Samples listed here are considered unsupported in that they are of a more esoteric nature and are sometimes contributed as a result of an individual's request. The are to be found in COIN/Clp/Samples/Contributed.

Below is a listing of a number of common CLP tasks, such as loading a problem from an MPS file, matched with a list of each Sample file which illustrates the performance of a given task.

The result of make unitTest (executed in COIN/Clp) is an executable clp as well as the CLP and COIN libraries. The executable can be used to perform various unit tests, but can also be used as a standalone solver. As the executable has a very simple solution file format, the user may wish to modify COIN/Clp/Test/ClpMain.cpp, which contains the source of the executable (modifications could even be offered as a contribution to CLP).

The clp executable operates in command line mode or prompted mode. Entering clp will invoke the prompted mode, while clp <filename> will import a problem in MPS format from filename, solve it using the dual simplex method and exit. The command clp <filename> -primalsimplex instructs the executable tp import a file and solve using the primal simplex method. An additional solitary dash ("-") starts the prompt mode once the execution of the initial command has been completed. The "-" is necessary as part of the command; invoking prompt mode as a separate command will result in the loss of problem information related to the initial command. So, the following sequences of commands are equivalent in the sense that both maximize a problem using the dual simplex method and write a solution to file: solfile:

The executable is at a very early stage of development. Comments and suggestions would be appreciated.

The executable has some command-completion functionality as well as some online help. Below is a table with some examples which summarize these capabilities.

In addition, matching a name without a ? will either execute the command or give the value of the corresponding parameter as follows: primalw will give the current value of the primalWeight parameter while primalw 1.0e7 will change it to 1.0e7.

Below is a sample CLP executable prompt-mode session. A small problem is loaded and solved under various conditions with the primal and dual simplex methods. Note the use of the allslack command; it sets the basis to all slacks and resets the solution.

    $clp
    Coin LP version 0.99.9, build Sep 14 2004
    Clp takes input from arguments ( - switches to stdin)
    Enter ? for list of commands or help
    Clp:import../Mps/Sample/p0033.mps
    At line 15 NAME          P0033
    At line 16 ROWS
    At line 34 COLUMNS
    At line 109 RHS
    At line 118 BOUNDS
    At line 152 ENDATA
    Problem P0033 has 16 rows, 33 columns and 98 elements
    Model was imported from ./../Mps/Sample/p0033.mps in 0 seconds
    Clp:primals
    Presolve 15 (-1) rows, 32 (-1) columns and 97 (-1) elements
    0  Obj 0 Primal inf 27.2175 (10) Dual inf 6.42094e+11 (32)
    32  Obj 2520.57
    Optimal - objective value 2520.57
    After Postsolve, objective 2520.57, infeasibilities - dual 0 (0), primal 0 (0)
    Optimal objective 2520.571739 - 32 iterations time 0.012, Presolve 0.01
    Clp:max
    Clp:primals
    Presolve 11 (-5) rows, 25 (-8) columns and 84 (-14) elements
    0  Obj 4807.92 Dual inf 1700.71 (15)
    End of values pass after 2 iterations
    2  Obj 4921.7 Dual inf 580.637 (5)
    9  Obj 5299.7
    Optimal - objective value 5299.7
    After Postsolve, objective 5299.7, infeasibilities - dual 643.608 (9), primal 27.0826 (10)
    Presolved model was optimal, full model needs cleaning up
    0  Obj 5299.7
    0  Obj 5299.7
    Optimal - objective value 5299.7
    Optimal objective 5299.698868 - 9 iterations time 0.022, Presolve 0.02
    Clp:allslack
    Clp:duals
    Presolve 11 (-5) rows, 25 (-8) columns and 84 (-14) elements
    0  Obj 2752 Primal inf 24.4867 (6) Dual inf 4280.55 (25)
    8  Obj 5299.7
    Optimal - objective value 5299.7
    After Postsolve, objective 5299.7, infeasibilities - dual 704.58 (8), primal 27.0792 (10)
    Presolved model was optimal, full model needs cleaning up
    0  Obj 5299.7
    0  Obj 5299.7
    Optimal - objective value 5299.7
    Optimal objective 5299.698868 - 8 iterations time 0.032, Presolve 0.01
    Clp:min
    Clp:duals
    Presolve 15 (-1) rows, 32 (-1) columns and 97 (-1) elements
    0  Obj 5299.7 Dual inf 4632.26 (28)
    16  Obj 2520.57
    Optimal - objective value 2520.57
    After Postsolve, objective 2520.57, infeasibilities - dual 2052.5 (13), primal 27.1143 (10)
    Presolved model was optimal, full model needs cleaning up
    0  Obj 2520.57
    0  Obj 2520.57
    Optimal - objective value 2520.57
    Optimal objective 2520.571739 - 16 iterations time 0.012, Presolve 0.01
    Clp:allslack
    Clp:presolve off
    Clp:primals
    0  Obj 0 Primal inf 27.2175 (10) Dual inf 6.39167e+11 (32)
    32  Obj 2520.57
    Optimal - objective value 2520.57
    Optimal objective 2520.571739 - 32 iterations time 0.002
    Clp:allslack
    Clp:maxIt 10
    maxIterations was changed from 99999999 to 10
    Clp:primals
    0  Obj 0 Primal inf 27.2175 (10) Dual inf 6.39167e+11 (32)
    Stopped - objective value 4.24664e+10
    Stopped objective 4.246637759e+10 - 10 iterations time 0.002
    Clp:quit