LinearProgram.cc

Go to the documentation of this file.

/*
 *  Copyright 2007 Martin von Gagern
 *
 *
 *  This file is part of bande.
 *
 *  bande is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  bande is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */


/**
 * @file
 * Implementation of class bande::LinearProgram.
 */

#include "bande.hh"

namespace bande {

  /**
   * Constructor.
   * The current implementation uses OsiClpSolverInterface as the
   * backend behind this wrapper. The model will be uninitialized,
   * waiting to be read by readMps().
   */
  LinearProgram::LinearProgram() {
    solver = new OsiClpSolverInterface;
    hasSolution = false;
    rows = cols = 0;
  }

  /**
   * Destructor.
   */
  LinearProgram::~LinearProgram() {
    if (solver) delete solver;
  }

  /**
   * Read the problem instance from an MPS file.
   * If a different interface than OsiClpSolverInterface is used, then
   * the file will be read twice, to provide names because access to
   * names is not part of the generic OsiSolverInterface.
   * In case of an error the program will exit with EXIT_FAILURE.
   *
   * @param fileName the name of the file to be read in.
   */
  void LinearProgram::readMps(const char* fileName) {
    if (solver->readMps(fileName))
      exit(EXIT_FAILURE);
    solver->messageHandler()->setLogLevel(0);
    rows = solver->getNumRows();
    cols = solver->getNumCols();
    rowNames.resize(rows);
    colNames.resize(cols);
    OsiClpSolverInterface* nameModel;
    nameModel = dynamic_cast<OsiClpSolverInterface*>(solver);
    if (!nameModel) {
      nameModel = new OsiClpSolverInterface;
      nameModel->messageHandler()->setLogLevel(0);
      if (nameModel->readMps(fileName))
        exit(EXIT_FAILURE);
    }
    for (int row = 0; row < rows; ++row)
      rowNames[row] = nameModel->getRowName(row);
    for (int col = 0; col < cols; ++col)
      colNames[col] = nameModel->getColName(col);
    if (nameModel != solver) delete nameModel;
  }

  /**
   * Find optimal solution to current linear program.
   * @return whether an optimal solution has been found.
   */
  bool LinearProgram::solve() {
    if (hasSolution) solver->resolve();
    else solver->initialSolve();
    solution = solver->getColSolution();
    hasSolution = true;
    return solver->isProvenOptimal();
  }

  /**
   * Dump the current solution for debugging purposes.
   * @param out the output stream to which the solution will be
   *            dumped.
   */
  void LinearProgram::dumpSolution(std::ostream& out) const {
    out << "BEGIN DUMP" << std::endl;
    for (int col = 0; col < getNumCols(); ++col) {
      double v = getColSolution(col);
      static const double eps = 1e-15;
      if (v > -eps && v < eps) continue;
      out << getColName(col) << " [" << col << "] = " << v << std::endl;
    }
    out << "END DUMP" << std::endl;
  }

  /**
   * Set lower bound of a column.
   * This modification is registered with an undo manager so it can be
   * rewound when switching to a different branch.
   * @param um the undo manager to track the modification.
   * @param col the index of the column to adjust.
   * @param val the new lower bound on the specified column.
   */
  void LinearProgram::setColLower(UndoManager& um, int col, double val) {
    typedef UndoColAction<&OsiSolverInterface::setColLower> U;
    um.record(new U(solver, col, solver->getColLower()[col]));
    solver->setColLower(col, val);
  }

  /**
   * Set upper bound of a column.
   * This modification is registered with an undo manager so it can be
   * rewound when switching to a different branch.
   * @param um the undo manager to track the modification.
   * @param col the index of the column to adjust.
   * @param val the new upper bound on the specified column.
   */
  void LinearProgram::setColUpper(UndoManager& um, int col, double val) {
    typedef UndoColAction<&OsiSolverInterface::setColUpper> U;
    um.record(new U(solver, col, solver->getColUpper()[col]));
    solver->setColUpper(col, val);
  }

  /**
   * Choose a random objective function.
   *
   * For enumeration purposes, the actual value of the objective
   * function is irrelevant. However, a random objective function
   * which most probably assigns different objective values to all
   * feasible integral solutions will enhance numeric stability.
   *
   * The implementation uses CoinDrand48() as randum number
   * generator. As that generator is seeded to a fixed value in
   * Settings::run(), consecutive runs of this program will yield the
   * same results in the same order, making the process
   * deterministic and any possible bugs reproducible.
   */
  void LinearProgram::randomizeObjective() {
    for (int col = 0; col < getNumCols(); ++col) {
      solver->setObjCoeff(col, CoinDrand48());
    }
  }

}

---