Parma_Polyhedra_Library::MIP_Problem Class Reference
[C++ Language Interface]

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

#include <ppl.hh>

List of all members.

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...
typedef
Constraint_Sequence::const_iterator 
const_iterator
 A type alias for the read-only iterator on the constraints defining the feasible region.

Public Member Functions

 MIP_Problem (dimension_type dim=0)
 Builds a trivial MIP problem.
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.
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.
 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.
 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.
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.
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.
void add_constraint (const Constraint &c)
 Adds a copy of constraint c to the MIP problem.
void add_constraints (const Constraint_System &cs)
 Adds a copy of the constraints in cs to the MIP problem.
void set_objective_function (const Linear_Expression &obj)
 Sets the objective function to obj.
void set_optimization_mode (Optimization_Mode mode)
 Sets the optimization mode to mode.
bool is_satisfiable () const
 Checks satisfiability of *this.
MIP_Problem_Status solve () const
 Optimizes the MIP problem.
void evaluate_objective_function (const Generator &evaluating_point, Coefficient &num, Coefficient &den) const
 Sets num and den so that $\frac{num}{den}$ is the result of evaluating the objective function on evaluating_point.
const Generatorfeasible_point () const
 Returns a feasible point for *this, if it exists.
const Generatoroptimizing_point () const
 Returns an optimal point for *this, if it exists.
void optimal_value (Coefficient &num, Coefficient &den) const
 Sets num and den so that $\frac{num}{den}$ is the solution of the optimization problem.
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 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 &lp)
 Output operator.
void swap (Parma_Polyhedra_Library::MIP_Problem &x, Parma_Polyhedra_Library::MIP_Problem &y)
 Specializes std::swap.

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


Member Enumeration Documentation

Names of MIP problems' control parameters.

Enumerator:
PRICING 

The pricing rule.

Possible values for MIP problem's control parameters.

Enumerator:
PRICING_STEEPEST_EDGE_FLOAT 

Steepest edge pricing method, using floating points (default).

PRICING_STEEPEST_EDGE_EXACT 

Steepest edge pricing method, using Coefficient.

PRICING_TEXTBOOK 

Textbook pricing method.


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:
dim The dimension of the vector space enclosing *this (optional argument with default value $0$).
Exceptions:
std::length_error Thrown 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 
) [inline]

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:
dim The dimension of the vector space enclosing *this.
first An input iterator to the start of the sequence of constraints.
last A past-the-end input iterator to the sequence of constraints.
int_vars The set of variables' indexes that are constrained to take integer values.
obj The objective function (optional argument with default value $0$).
mode The optimization mode (optional argument with default value MAXIMIZATION).
Exceptions:
std::length_error Thrown if dim exceeds max_space_dimension().
std::invalid_argument Thrown 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 
) [inline]

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:
dim The dimension of the vector space enclosing *this.
first An input iterator to the start of the sequence of constraints.
last A past-the-end input iterator to the sequence of constraints.
obj The objective function (optional argument with default value $0$).
mode The optimization mode (optional argument with default value MAXIMIZATION).
Exceptions:
std::length_error Thrown if dim exceeds max_space_dimension().
std::invalid_argument Thrown 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:
dim The dimension of the vector space enclosing *this.
cs The constraint system defining the feasible region.
obj The objective function (optional argument with default value $0$).
mode The optimization mode (optional argument with default value MAXIMIZATION).
Exceptions:
std::length_error Thrown if dim exceeds max_space_dimension().
std::invalid_argument Thrown 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:
m The number of dimensions to add.
Exceptions:
std::length_error Thrown 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_argument Thrown 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_argument Thrown 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_argument Thrown 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_argument Thrown 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 num,
Coefficient den 
) const

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

Parameters:
evaluating_point The point on which the objective function will be evaluated.
num On exit will contain the numerator of the evaluated value.
den On exit will contain the denominator of the evaluated value.
Exceptions:
std::invalid_argument Thrown 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_error Thrown 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_error Thrown if *this doesn't 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 num,
Coefficient den 
) const [inline]

Sets num and den so that $\frac{num}{den}$ is the solution of the optimization problem.

Exceptions:
std::domain_error Thrown if *this doesn't 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 lp 
) [related]

Output operator.

Specializes std::swap.


The documentation for this class was generated from the following file:
Generated on Sun Feb 27 10:10:57 2011 for PPL by  doxygen 1.6.3