MIP_Problem_defs.hh

Go to the documentation of this file.

/* MIP_Problem class declaration.
   Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
   Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)

This file is part of the Parma Polyhedra Library (PPL).

The PPL 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.

The PPL 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, write to the Free Software Foundation,
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.

For the most up-to-date information see the Parma Polyhedra Library
site: http://bugseng.com/products/ppl/ . */

#ifndef PPL_MIP_Problem_defs_hh
#define PPL_MIP_Problem_defs_hh 1

#include "MIP_Problem_types.hh"
#include "globals_types.hh"
#include "Matrix_defs.hh"
#include "Linear_Expression_defs.hh"
#include "Constraint_types.hh"
#include "Constraint_System_types.hh"
#include "Generator_defs.hh"
#include "Variables_Set_defs.hh"
#include "Dense_Row_defs.hh"
#include "Sparse_Row_defs.hh"
#include <vector>
#include <deque>
#include <iterator>
#include <iosfwd>

namespace Parma_Polyhedra_Library {

namespace IO_Operators {


std::ostream&
operator<<(std::ostream& s, const MIP_Problem& mip);

} // namespace IO_Operators


void swap(MIP_Problem& x, MIP_Problem& y);

} // namespace Parma_Polyhedra_Library


class Parma_Polyhedra_Library::MIP_Problem {
public:

  explicit MIP_Problem(dimension_type dim = 0);

  template <typename In>
  MIP_Problem(dimension_type dim,
              In first, In last,
              const Variables_Set& int_vars,
              const Linear_Expression& obj = Linear_Expression::zero(),
              Optimization_Mode mode = MAXIMIZATION);

  template <typename In>
  MIP_Problem(dimension_type dim,
              In first, In last,
              const Linear_Expression& obj = Linear_Expression::zero(),
              Optimization_Mode mode = MAXIMIZATION);

  MIP_Problem(dimension_type dim,
              const Constraint_System& cs,
              const Linear_Expression& obj = Linear_Expression::zero(),
              Optimization_Mode mode = MAXIMIZATION);

  MIP_Problem(const MIP_Problem& y);

  ~MIP_Problem();

  MIP_Problem& operator=(const MIP_Problem& y);

  static dimension_type max_space_dimension();

  dimension_type space_dimension() const;

  const Variables_Set& integer_space_dimensions() const;

private:
  typedef std::vector<Constraint*> Constraint_Sequence;

public:
  class const_iterator {
  private:
    typedef Constraint_Sequence::const_iterator Base;
    typedef std::iterator_traits<Base> Base_Traits;

  public:
    typedef Base_Traits::iterator_category iterator_category;
    typedef Base_Traits::difference_type difference_type;
    typedef const Constraint value_type;
    typedef const Constraint* pointer;
    typedef const Constraint& reference;

    difference_type operator-(const const_iterator& y) const;

    const_iterator& operator++();

    const_iterator& operator--();

    const_iterator operator++(int);

    const_iterator operator--(int);

    const_iterator& operator+=(difference_type n);

    const_iterator& operator-=(difference_type n);

    const_iterator operator+(difference_type n) const;

    const_iterator operator-(difference_type n) const;

    reference operator*() const;

    pointer operator->() const;


    bool operator==(const const_iterator& y) const;


    bool operator!=(const const_iterator& y) const;

  private:
    explicit const_iterator(Base b);

    Base itr;

    friend class MIP_Problem;
  };

  const_iterator constraints_begin() const;

  const_iterator constraints_end() const;

  const Linear_Expression& objective_function() const;

  Optimization_Mode optimization_mode() const;


  void clear();

  void add_space_dimensions_and_embed(dimension_type m);

  void add_to_integer_space_dimensions(const Variables_Set& i_vars);

  void add_constraint(const Constraint& c);

  void add_constraints(const Constraint_System& cs);


  void set_objective_function(const Linear_Expression& obj);

  void set_optimization_mode(Optimization_Mode mode);


  bool is_satisfiable() const;


  MIP_Problem_Status solve() const;

  void evaluate_objective_function(const Generator& evaluating_point,
                                   Coefficient& numer,
                                   Coefficient& denom) const;


  const Generator& feasible_point() const;


  const Generator& optimizing_point() const;

  void optimal_value(Coefficient& numer, Coefficient& denom) const;

  bool OK() const;

  PPL_OUTPUT_DECLARATIONS

  bool ascii_load(std::istream& s);

  memory_size_type total_memory_in_bytes() const;

  memory_size_type external_memory_in_bytes() const;

  void m_swap(MIP_Problem& y);

  enum Control_Parameter_Name {
    PRICING
  };

  enum Control_Parameter_Value {
    PRICING_STEEPEST_EDGE_FLOAT,
    PRICING_STEEPEST_EDGE_EXACT,
    PRICING_TEXTBOOK
  };

  Control_Parameter_Value
  get_control_parameter(Control_Parameter_Name name) const;

  void set_control_parameter(Control_Parameter_Value value);

private:
  dimension_type external_space_dim;

  dimension_type internal_space_dim;

#if PPL_USE_SPARSE_MATRIX
  typedef Sparse_Row Row;
#else
  typedef Dense_Row Row;
#endif

  Matrix<Row> tableau;

  typedef Row working_cost_type;

  working_cost_type working_cost;


  std::vector<std::pair<dimension_type, dimension_type> > mapping;

  std::vector<dimension_type> base;

  enum Status {
    UNSATISFIABLE,
    SATISFIABLE,
    UNBOUNDED,
    OPTIMIZED,
    PARTIALLY_SATISFIABLE
  };

  Status status;

  // TODO: merge `status', `initialized', `pricing' and (maybe) `opt_mode'
  // into a single bitset status word, so as to save space and allow
  // for other control parameters.

  Control_Parameter_Value pricing;

  bool initialized;

  std::vector<Constraint*> input_cs;

  dimension_type inherited_constraints;

  dimension_type first_pending_constraint;

  Linear_Expression input_obj_function;

  Optimization_Mode opt_mode;

  Generator last_generator;

  Variables_Set i_variables;

  struct RAII_Temporary_Real_Relaxation {
    MIP_Problem& lp;
    Variables_Set i_vars;

    RAII_Temporary_Real_Relaxation(MIP_Problem& mip)
      : lp(mip), i_vars() {
      // Turn mip into an LP problem (saving i_variables in i_vars).
      using std::swap;
      swap(i_vars, lp.i_variables);
    }

    ~RAII_Temporary_Real_Relaxation() {
      // Restore the original set of integer variables.
      using std::swap;
      swap(i_vars, lp.i_variables);
    }
  };
  friend struct RAII_Temporary_Real_Relaxation;

  struct Inherit_Constraints {};

  MIP_Problem(const MIP_Problem& y, Inherit_Constraints);

  void add_constraint_helper(const Constraint& c);

  void process_pending_constraints();

  void second_phase();

  MIP_Problem_Status
  compute_tableau(std::vector<dimension_type>& worked_out_row);

  bool parse_constraints(dimension_type& additional_tableau_rows,
                         dimension_type& additional_slack_variables,
                         std::deque<bool>& is_tableau_constraint,
                         std::deque<bool>& is_satisfied_inequality,
                         std::deque<bool>& is_nonnegative_variable,
                         std::deque<bool>& is_remergeable_variable) const;

  dimension_type
  get_exiting_base_index(dimension_type entering_var_index) const;


  static void linear_combine(Row& x, const Row& y, const dimension_type k);

  // TODO: Remove this when the sparse working cost has been tested enough.
#if PPL_USE_SPARSE_MATRIX


  static void linear_combine(Dense_Row& x, const Sparse_Row& y,
                             const dimension_type k);

#endif // defined(PPL_USE_SPARSE_MATRIX)

  static bool is_unbounded_obj_function(
    const Linear_Expression& obj_function,
    const std::vector<std::pair<dimension_type, dimension_type> >& mapping,
    Optimization_Mode optimization_mode);

  void pivot(dimension_type entering_var_index,
             dimension_type exiting_base_index);

  dimension_type textbook_entering_index() const;

  dimension_type steepest_edge_exact_entering_index() const;

  dimension_type steepest_edge_float_entering_index() const;

  bool compute_simplex_using_exact_pricing();

  bool compute_simplex_using_steepest_edge_float();

  void erase_artificials(dimension_type begin_artificials,
                         dimension_type end_artificials);

  bool is_in_base(dimension_type var_index,
                  dimension_type& row_index) const;

  void compute_generator() const;

  dimension_type merge_split_variable(dimension_type var_index);

  static bool is_satisfied(const Constraint& c, const Generator& g);

  static bool is_saturated(const Constraint& c, const Generator& g);

  static MIP_Problem_Status solve_mip(bool& have_incumbent_solution,
                                      mpq_class& incumbent_solution_value,
                                      Generator& incumbent_solution_point,
                                      MIP_Problem& mip,
                                      const Variables_Set& i_vars);

  bool is_lp_satisfiable() const;

  static bool is_mip_satisfiable(MIP_Problem& mip,
                                 const Variables_Set& i_vars,
                                 Generator& p);

  static bool choose_branching_variable(const MIP_Problem& mip,
                                        const Variables_Set& i_vars,
                                        dimension_type& branching_index);
};

#include "MIP_Problem_inlines.hh"
#include "MIP_Problem_templates.hh"

#endif // !defined(PPL_MIP_Problem_defs_hh)