IntegerProgram.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::IntegerProgram.
 */

#include "bande.hh"

namespace bande {

  /**
   * Constructor.
   */
  IntegerProgram::IntegerProgram() {
  }

  /**
   * Destructor.
   */
  IntegerProgram::~IntegerProgram() {
  }

  /**
   * Cast to integer by rounding.
   *
   * The argument is assumed to be conceptually integral, so there is
   * no check to ensure that the value is really integral or anywhere
   * close to an integer. What is checked, however, is the range. The
   * valid output range of this method is almost the whole range of
   * int, with only a little bit removed as a safety margin. Values
   * exceeding this range will be clipped to the neares range
   * boundary. Values *.5 are always rounded up by this method.
   *
   * @param d the double value to be converted to an integer.
   * @return the nearest integer to d inside the result range.
   */
  int IntegerProgram::mkInt(double d) {
    static const int max = std::numeric_limits<int>::max() - 100;
    static const int min = std::numeric_limits<int>::min() + 100;
    if (d > max) return max;
    if (d < min) return min;
    return (int)floor(d + 0.5);
  }

  /**
   * Read the problem instance from an MPS file.
   * After reading the linear program using LinearProgram::readMps(),
   * the internal integer-based data structures are filled from that
   * problem instance.
   *
   * @param fileName the name of the file to be read in.
   *
   * @bug there is no check that the columns are constrained to
   * integer values. Neither are there checks to ensure that all
   * bounds and matrix elements are integral. A non-integral input
   * file may lead to strange behaviour without a warning.
   */
  void IntegerProgram::readMps(const char* fileName) {
    lp.readMps(fileName);
    rowBounds.resize(getNumRows());
    colBounds.resize(getNumCols());
    iSol.resize(getNumCols());
    matrix.clear();
    matrix.resize(getNumRows() * getNumCols());
    for (int row = 0; row < getNumRows(); ++row) {
      rowBounds[row].first = mkInt(lp.getRowLower(row));
      rowBounds[row].second = mkInt(lp.getRowUpper(row));
    }
    for (int col = 0; col < getNumCols(); ++col) {
      colBounds[col].first = mkInt(lp.getColLower(col));
      colBounds[col].second = mkInt(lp.getColUpper(col));
    }
    const CoinPackedMatrix* cpm = lp.getSolver()->getMatrixByRow();
    const double* elements = cpm->getElements();
    const int* indices = cpm->getIndices();
    for (int row = 0; row < getNumRows(); ++row) {
      for (CoinBigIndex i = cpm->getVectorFirst(row),
             e = cpm->getVectorLast(row); i != e; ++i) {
        m(row, indices[i]) = mkInt(elements[i]);
      }
    }
  }

  /**
   * 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. The bounds may only
   * be tightened, never loosened except through an undo.
   * @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 IntegerProgram::setColLower(UndoManager& um, int col, int val) {
    int& ref = colBounds[col].first;
    if (val <= ref) {
      std::cerr << "Invalid change of lower bound from "
                << ref << " to " << val << std::endl;
      exit(EXIT_FAILURE);
    }
    um.record(new UndoInt(ref));
    ref = val;
    lp.setColLower(um, 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. The bounds may only
   * be tightened, never loosened except through an undo.
   * @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 IntegerProgram::setColUpper(UndoManager& um, int col, int val) {
    int& ref = colBounds[col].second;
    if (val >= ref) {
      std::cerr << "Invalid change of upper bound from "
                << ref << " to " << val << std::endl;
      exit(EXIT_FAILURE);
    }
    um.record(new UndoInt(ref));
    ref = val;
    lp.setColUpper(um, col, val);
  }

  /**
   * Convert solution values to integers.
   * The solution is assumed to be integral already. After this method
   * has been invoked, getIntSolution() will return the requested
   * integral solution without casting for every call.
   */
  void IntegerProgram::mkIntSolution() {
    for (int col = 0; col < getNumCols(); ++col) {
      iSol[col] = mkInt(getColSolution(col));
    }
  }

  /**
   * Check the current integral solution.
   *
   * After mkIntSolutions() has been invoked, there should be a
   * solution to the all-integer problem. This method checks that
   * assumption by verifying each bound using only integer arithmetic,
   * with never a chance for rounding issues.
   *
   * @return whether the current solution is a valid integral
   *         solution.
   */
  bool IntegerProgram::checkIntSolution() const {
    for (int col = 0; col < getNumCols(); ++col) {
      if (iSol[col] < colBounds[col].first ||
          iSol[col] > colBounds[col].second) {
        std::cerr << "col " << col << " (" << getColName(col) << "): "
                  << colBounds[col].first << "<=" << iSol[col] << "<="
                  << colBounds[col].second << std::endl;
        return false;
      }
    }
    for (int row = 0, mi = 0; row < getNumRows(); ++row) {
      int sum = 0;
      for (int col = 0; col < getNumCols(); ++col)
        sum += matrix[mi++] * iSol[col];
      if (sum < rowBounds[row].first || sum > rowBounds[row].second) {
        std::cerr << "row " << row << " (" << getRowName(row) << "): "
                  << rowBounds[row].first << "<=" << iSol[row] << "<="
                  << rowBounds[row].second << std::endl;
        return false;
      }
    }
    return true;
  }

}

---