[Coin-discuss] Implementation of the pivot-based interface for simplex solvers

[Mikhail Nediak]

Greetings to the COIN community!

Some time ago we have posted a proposal on addition of the pivot-based
functionality to the solver interface in COIN/OSI. We would like to report
a recent development in its implementation.

We have implemented a simplified version of the OsiSimplexInterface
(header file attached, please see a couple of previous postings for
the proposed full version) for the CPLEX and the extended version of SIMPO
(an open source simplex solver for the LP textbook by Robert Vanderbei).

The current set of functions allows us to use both solvers with a new
version of our Pivot, Cut and Dive heuristic for the general 0-1 MIP.

We wanted to implement the new methods in a way that would require only
superficial modifications to the existing code. Thus, for CPLEX, we
have implemented an extended class

class OsiCpxSimplexInterface : public OsiSimplexInterface,
	public OsiCpxSolverInterface
{
public:
///...
};

which is a descendant of the existing class OsiCpxSolverInterface.
We had to make
  static CPXENVptr getEnvironmentPtr();
a protected method to allow extension. No additional modifications were
necessary.

The class OsiSimplexInterface is purely abstract. One can test whether
a generic solver passed as a pointer ptr to OsiSolverInterface implements
its methods by comparing dynamic_cast<OsiSimplexInterface*>(ptr) to NULL.

We welcome any questions and comments.

Best regards,
Mikhail Nediak

-------------- next part --------------
#ifndef OSI_SIMPLEX_INTERFACE
#define OSI_SIMPLEX_INTERFACE

#include <string>
#include <vector>

#include "OsiCollections.hpp"
#include "OsiPackedVectorBase.hpp"

#include "OsiSolverParameters.hpp"

class OsiPackedMatrix;

class OsiSimplexInterface {
 public:
  ///Set presolve status
  virtual void setPresolve(bool on) = 0;

  ///Enables normal operation of subsequent functions
  virtual void enableSimplexInterface() = 0;

  ///Returns true if the basis is available
  virtual bool basisIsAvailable() = 0;

  ///Returns a basis status of the structural/artificial variables
  virtual void getBasisStatus(int* cstat, int* rstat) = 0;

  ///Set the status of structural/artificial variables
  virtual int setBasisStatus(const int* cstat, const int* rstat) = 0;

  ///Perform a pivot by substituting a colOut for colIn in the basis. 
  ///The status of the leaving variable is given in statOut 
  virtual int pivot(int colIn, int colOut, int outStatus) = 0;

  ///Obtain the result of the pivot (leaving column and status,
  ///step size, and if dx!=NULL edge direction)
  virtual int primalPivotResult(int colIn, int sign, 
								int& colOut, int& outStatus, 
								double& t, OsiPackedVector* dx) = 0;

  //Get the reduced gradient for the cost vector c
  virtual void getReducedGradient(double* z, const double * c) = 0;

  ///Set new objective, while keeping the old basis
  virtual void setObjective(double* c) = 0;
};

#endif