IntegerProgram.hh

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
 * Interface of class bande::IntegerProgram.
 */

namespace bande {

  /**
   * Linear program with integer bounds, coefficients and solutions.
   *
   * This class is mainly a wrapper around LinearProgram which changes
   * many of its data types from double to integer. In order to not
   * interfere with the LP, the integral bookkeeping is done using
   * duplicate data structures within this IP.
   *
   * In order to keep these dual structures synchronized, there is no
   * direct access to the protected linear program. All access must be
   * made through the corresponding integer program.
   */
  class IntegerProgram {

  public:
    IntegerProgram();
    virtual ~IntegerProgram();

    void readMps(const char* fileName);
    void setColLower(UndoManager& um, int col, int val);
    void setColUpper(UndoManager& um, int col, int val);
    void mkIntSolution();
    bool checkIntSolution() const;

    /**
     * Get the number of rows.
     * Each row represents zero to two inequalities, depending on the
     * row bounds.
     * @return the number of rows in the problem.
     */
    int getNumRows() const { return lp.getNumRows(); }

    /**
     * Get the number of columns.
     * Each column corresponds to one variable of the solution.
     * @return the number of columns in the problem.
     */
    int getNumCols() const { return lp.getNumCols(); }

    /**
     * Find optimal solution to current linear program.
     * @return whether an optimal solution has been found.
     */
    bool solve() { return lp.solve(); }

    /**
     * Get one variable of the solution.
     * @param index the index of the variable.
     * @return the value of that variable in the current solution.
     */
    double getColSolution(int index) const { return lp.getColSolution(index); }

    /**
     * Dump the current solution for debugging purposes.
     * @param out the output stream to which the solution will be
     *            dumped.
     */
    void dumpSolution(std::ostream& out = std::cerr) const {
      lp.dumpSolution(out);
    }

    /**
     * Get the current lower bound of a column.
     * @param col the index of the column.
     * @return the current lower bound of that column.
     */
    int getColLower(int col) const { return colBounds[col].first; }

    /**
     * Get the current upper bound of a column.
     * @param col the index of the column.
     * @return the current upper bound of that column.
     */
    int getColUpper(int col) const { return colBounds[col].second; }

    /**
     * Get both bounds of a column.
     * @param col the index of the column.
     * @return a pair of the lower (first) and upper (second) bound of
     *         that column.
     */
    const std::pair<int, int>& getColBounds(int col) const {
      return colBounds[col];
    }

    /**
     * Choose a random objective function.
     */
    void randomizeObjective() { lp.randomizeObjective(); }

    /**
     * Get the name of a column.
     * This is also the name of the associated variable.
     * @param col the index of the column.
     * @return the name of that column.
     */
    std::string getColName(int col) const { return lp.getColName(col); }

    /**
     * Get the name of a row.
     * @param row the index of the row.
     * @return the name of that row.
     */
    std::string getRowName(int row) const { return lp.getRowName(row); }

    /**
     * Get one variable of the solution as an integer.
     *
     * This function will only return the current values after
     * mkIntSolution() has been called.
     *
     * @param index the index of the variable.
     * @return the value of that variable in the current solution.
     */
    int getIntSolution(int index) const { return iSol[index]; }

  protected:

    /**
     * The linear program wrapped inside this integer program.
     */
    LinearProgram lp;

    /**
     * The row bounds as integers.
     */
    std::vector< std::pair<int, int> > rowBounds;

    /**
     * The column bounds as integers.
     */
    std::vector< std::pair<int, int> > colBounds;

    /**
     * The matrix elements as integers.
     *
     * The matrix elements are stored in row major mode, and can be
     * accessed through the m() function by giving twodimensional
     * coordinates.
     */
    std::vector<int> matrix;

    /**
     * The solution vector rounded to integers.
     * This vector is not automatically filled in, but only when
     * mkIntSolution() is called.
     */
    std::vector<int> iSol;

    int mkInt(double d);

    /**
     * Provide read-write access to the integral matrix elements.
     * @param row the row index of the matrix element.
     * @param col the column index of the matrix element.
     * @return a writable reference to the addressed matrix element.
     */
    int& m(int row, int col) { return matrix[row*getNumCols() + col]; }
  };

}

---