PPL  1.2
Parma_Polyhedra_Library::MIP_Problem Class Reference

A Mixed Integer (linear) Programming problem. More...

#include <ppl.hh>

Classes

class  const_iterator
 A read-only iterator on the constraints defining the feasible region. More...
 

Public Types

enum  Control_Parameter_Name { PRICING }
 Names of MIP problems' control parameters. More...
 
enum  Control_Parameter_Value { PRICING_STEEPEST_EDGE_FLOAT, PRICING_STEEPEST_EDGE_EXACT, PRICING_TEXTBOOK }
 Possible values for MIP problem's control parameters. More...
 

Public Member Functions

 MIP_Problem (dimension_type dim=0)
 Builds a trivial MIP problem. More...
 
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)
 Builds an MIP problem having space dimension dim from the sequence of constraints in the range $[\mathrm{first}, \mathrm{last})$, the objective function obj and optimization mode mode; those dimensions whose indices occur in int_vars are constrained to take an integer value. More...
 
template<typename In >
 MIP_Problem (dimension_type dim, In first, In last, const Linear_Expression &obj=Linear_Expression::zero(), Optimization_Mode mode=MAXIMIZATION)
 Builds an MIP problem having space dimension dim from the sequence of constraints in the range $[\mathrm{first}, \mathrm{last})$, the objective function obj and optimization mode mode. More...
 
 MIP_Problem (dimension_type dim, const Constraint_System &cs, const Linear_Expression &obj=Linear_Expression::zero(), Optimization_Mode mode=MAXIMIZATION)
 Builds an MIP problem having space dimension dim from the constraint system cs, the objective function obj and optimization mode mode. More...
 
 MIP_Problem (const MIP_Problem &y)
 Ordinary copy constructor.
 
 ~MIP_Problem ()
 Destructor.
 
MIP_Problemoperator= (const MIP_Problem &y)
 Assignment operator.
 
dimension_type space_dimension () const
 Returns the space dimension of the MIP problem.
 
const Variables_Setinteger_space_dimensions () const
 Returns a set containing all the variables' indexes constrained to be integral.
 
const_iterator constraints_begin () const
 Returns a read-only iterator to the first constraint defining the feasible region.
 
const_iterator constraints_end () const
 Returns a past-the-end read-only iterator to the sequence of constraints defining the feasible region.
 
const Linear_Expressionobjective_function () const
 Returns the objective function.
 
Optimization_Mode optimization_mode () const
 Returns the optimization mode.
 
void clear ()
 Resets *this to be equal to the trivial MIP problem. More...
 
void add_space_dimensions_and_embed (dimension_type m)
 Adds m new space dimensions and embeds the old MIP problem in the new vector space. More...
 
void add_to_integer_space_dimensions (const Variables_Set &i_vars)
 Sets the variables whose indexes are in set i_vars to be integer space dimensions. More...
 
void add_constraint (const Constraint &c)
 Adds a copy of constraint c to the MIP problem. More...
 
void add_constraints (const Constraint_System &cs)
 Adds a copy of the constraints in cs to the MIP problem. More...
 
void set_objective_function (const Linear_Expression &obj)
 Sets the objective function to obj. More...
 
void set_optimization_mode (Optimization_Mode mode)
 Sets the optimization mode to mode.
 
bool is_satisfiable () const
 Checks satisfiability of *this. More...
 
MIP_Problem_Status solve () const
 Optimizes the MIP problem. More...
 
void evaluate_objective_function (const Generator &evaluating_point, Coefficient &numer, Coefficient &denom) const
 Sets num and denom so that $\frac{\mathtt{numer}}{\mathtt{denom}}$ is the result of evaluating the objective function on evaluating_point. More...
 
const Generatorfeasible_point () const
 Returns a feasible point for *this, if it exists. More...
 
const Generatoroptimizing_point () const
 Returns an optimal point for *this, if it exists. More...
 
void optimal_value (Coefficient &numer, Coefficient &denom) const
 Sets numer and denom so that $\frac{\mathtt{numer}}{\mathtt{denom}}$ is the solution of the optimization problem. More...
 
bool OK () const
 Checks if all the invariants are satisfied.
 
void ascii_dump () const
 Writes to std::cerr an ASCII representation of *this.
 
void ascii_dump (std::ostream &s) const
 Writes to s an ASCII representation of *this.
 
void print () const
 Prints *this to std::cerr using operator<<.
 
bool ascii_load (std::istream &s)
 Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.
 
memory_size_type total_memory_in_bytes () const
 Returns the total size in bytes of the memory occupied by *this.
 
memory_size_type external_memory_in_bytes () const
 Returns the size in bytes of the memory managed by *this.
 
void m_swap (MIP_Problem &y)
 Swaps *this with y.
 
Control_Parameter_Value get_control_parameter (Control_Parameter_Name name) const
 Returns the value of the control parameter name.
 
void set_control_parameter (Control_Parameter_Value value)
 Sets control parameter value.
 

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension an MIP_Problem can handle.
 

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &s, const MIP_Problem &mip)
 Output operator. More...
 
void swap (MIP_Problem &x, MIP_Problem &y)
 Swaps x with y. More...
 
void swap (MIP_Problem &x, MIP_Problem &y)
 

Detailed Description

A Mixed Integer (linear) Programming problem.

An object of this class encodes a mixed integer (linear) programming problem. The MIP problem is specified by providing:

  • the dimension of the vector space;
  • the feasible region, by means of a finite set of linear equality and non-strict inequality constraints;
  • the subset of the unknown variables that range over the integers (the other variables implicitly ranging over the reals);
  • the objective function, described by a Linear_Expression;
  • the optimization mode (either maximization or minimization).

The class provides support for the (incremental) solution of the MIP problem based on variations of the revised simplex method and on branch-and-bound techniques. The result of the resolution process is expressed in terms of an enumeration, encoding the feasibility and the unboundedness of the optimization problem. The class supports simple feasibility tests (i.e., no optimization), as well as the extraction of an optimal (resp., feasible) point, provided the MIP_Problem is optimizable (resp., feasible).

By exploiting the incremental nature of the solver, it is possible to reuse part of the computational work already done when solving variants of a given MIP_Problem: currently, incremental resolution supports the addition of space dimensions, the addition of constraints, the change of objective function and the change of optimization mode.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::MIP_Problem::MIP_Problem ( dimension_type  dim = 0)
explicit

Builds a trivial MIP problem.

A trivial MIP problem requires to maximize the objective function $0$ on a vector space under no constraints at all: the origin of the vector space is an optimal solution.

Parameters
dimThe dimension of the vector space enclosing *this (optional argument with default value $0$).
Exceptions
std::length_errorThrown if dim exceeds max_space_dimension().
template<typename In >
Parma_Polyhedra_Library::MIP_Problem::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 
)

Builds an MIP problem having space dimension dim from the sequence of constraints in the range $[\mathrm{first}, \mathrm{last})$, the objective function obj and optimization mode mode; those dimensions whose indices occur in int_vars are constrained to take an integer value.

Parameters
dimThe dimension of the vector space enclosing *this.
firstAn input iterator to the start of the sequence of constraints.
lastA past-the-end input iterator to the sequence of constraints.
int_varsThe set of variables' indexes that are constrained to take integer values.
objThe objective function (optional argument with default value $0$).
modeThe optimization mode (optional argument with default value MAXIMIZATION).
Exceptions
std::length_errorThrown if dim exceeds max_space_dimension().
std::invalid_argumentThrown if a constraint in the sequence is a strict inequality, if the space dimension of a constraint (resp., of the objective function or of the integer variables) or the space dimension of the integer variable set is strictly greater than dim.
template<typename In >
Parma_Polyhedra_Library::MIP_Problem::MIP_Problem ( dimension_type  dim,
In  first,
In  last,
const Linear_Expression obj = Linear_Expression::zero(),
Optimization_Mode  mode = MAXIMIZATION 
)

Builds an MIP problem having space dimension dim from the sequence of constraints in the range $[\mathrm{first}, \mathrm{last})$, the objective function obj and optimization mode mode.

Parameters
dimThe dimension of the vector space enclosing *this.
firstAn input iterator to the start of the sequence of constraints.
lastA past-the-end input iterator to the sequence of constraints.
objThe objective function (optional argument with default value $0$).
modeThe optimization mode (optional argument with default value MAXIMIZATION).
Exceptions
std::length_errorThrown if dim exceeds max_space_dimension().
std::invalid_argumentThrown if a constraint in the sequence is a strict inequality or if the space dimension of a constraint (resp., of the objective function or of the integer variables) is strictly greater than dim.
Parma_Polyhedra_Library::MIP_Problem::MIP_Problem ( dimension_type  dim,
const Constraint_System cs,
const Linear_Expression obj = Linear_Expression::zero(),
Optimization_Mode  mode = MAXIMIZATION 
)

Builds an MIP problem having space dimension dim from the constraint system cs, the objective function obj and optimization mode mode.

Parameters
dimThe dimension of the vector space enclosing *this.
csThe constraint system defining the feasible region.
objThe objective function (optional argument with default value $0$).
modeThe optimization mode (optional argument with default value MAXIMIZATION).
Exceptions
std::length_errorThrown if dim exceeds max_space_dimension().
std::invalid_argumentThrown if the constraint system contains any strict inequality or if the space dimension of the constraint system (resp., the objective function) is strictly greater than dim.

Member Function Documentation

void Parma_Polyhedra_Library::MIP_Problem::clear ( )
inline

Resets *this to be equal to the trivial MIP problem.

The space dimension is reset to $0$.

void Parma_Polyhedra_Library::MIP_Problem::add_space_dimensions_and_embed ( dimension_type  m)

Adds m new space dimensions and embeds the old MIP problem in the new vector space.

Parameters
mThe number of dimensions to add.
Exceptions
std::length_errorThrown if adding m new space dimensions would cause the vector space to exceed dimension max_space_dimension().

The new space dimensions will be those having the highest indexes in the new MIP problem; they are initially unconstrained.

void Parma_Polyhedra_Library::MIP_Problem::add_to_integer_space_dimensions ( const Variables_Set i_vars)

Sets the variables whose indexes are in set i_vars to be integer space dimensions.

Exceptions
std::invalid_argumentThrown if some index in i_vars does not correspond to a space dimension in *this.
void Parma_Polyhedra_Library::MIP_Problem::add_constraint ( const Constraint c)

Adds a copy of constraint c to the MIP problem.

Exceptions
std::invalid_argumentThrown if the constraint c is a strict inequality or if its space dimension is strictly greater than the space dimension of *this.
void Parma_Polyhedra_Library::MIP_Problem::add_constraints ( const Constraint_System cs)

Adds a copy of the constraints in cs to the MIP problem.

Exceptions
std::invalid_argumentThrown if the constraint system cs contains any strict inequality or if its space dimension is strictly greater than the space dimension of *this.
void Parma_Polyhedra_Library::MIP_Problem::set_objective_function ( const Linear_Expression obj)

Sets the objective function to obj.

Exceptions
std::invalid_argumentThrown if the space dimension of obj is strictly greater than the space dimension of *this.
bool Parma_Polyhedra_Library::MIP_Problem::is_satisfiable ( ) const

Checks satisfiability of *this.

Returns
true if and only if the MIP problem is satisfiable.
MIP_Problem_Status Parma_Polyhedra_Library::MIP_Problem::solve ( ) const

Optimizes the MIP problem.

Returns
An MIP_Problem_Status flag indicating the outcome of the optimization attempt (unfeasible, unbounded or optimized problem).
void Parma_Polyhedra_Library::MIP_Problem::evaluate_objective_function ( const Generator evaluating_point,
Coefficient numer,
Coefficient denom 
) const

Sets num and denom so that $\frac{\mathtt{numer}}{\mathtt{denom}}$ is the result of evaluating the objective function on evaluating_point.

Parameters
evaluating_pointThe point on which the objective function will be evaluated.
numerOn exit will contain the numerator of the evaluated value.
denomOn exit will contain the denominator of the evaluated value.
Exceptions
std::invalid_argumentThrown if *this and evaluating_point are dimension-incompatible or if the generator evaluating_point is not a point.
const Generator& Parma_Polyhedra_Library::MIP_Problem::feasible_point ( ) const

Returns a feasible point for *this, if it exists.

Exceptions
std::domain_errorThrown if the MIP problem is not satisfiable.
const Generator& Parma_Polyhedra_Library::MIP_Problem::optimizing_point ( ) const

Returns an optimal point for *this, if it exists.

Exceptions
std::domain_errorThrown if *this does not not have an optimizing point, i.e., if the MIP problem is unbounded or not satisfiable.
void Parma_Polyhedra_Library::MIP_Problem::optimal_value ( Coefficient numer,
Coefficient denom 
) const
inline

Sets numer and denom so that $\frac{\mathtt{numer}}{\mathtt{denom}}$ is the solution of the optimization problem.

Exceptions
std::domain_errorThrown if *this does not not have an optimizing point, i.e., if the MIP problem is unbounded or not satisfiable.

Friends And Related Function Documentation

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

Output operator.

void swap ( MIP_Problem x,
MIP_Problem y 
)
related

Swaps x with y.

void swap ( MIP_Problem x,
MIP_Problem y 
)
related

The documentation for this class was generated from the following file: