PPL
1.2
|
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 ![]() 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 ![]() 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_Problem & | operator= (const MIP_Problem &y) |
Assignment operator. | |
dimension_type | space_dimension () const |
Returns the space dimension of the MIP problem. | |
const Variables_Set & | integer_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_Expression & | objective_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 ![]() evaluating_point . More... | |
const Generator & | feasible_point () const |
Returns a feasible point for *this , if it exists. More... | |
const Generator & | optimizing_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 ![]() | |
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) |
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.
|
explicit |
Builds a trivial MIP problem.
A trivial MIP problem requires to maximize the objective function on a vector space under no constraints at all: the origin of the vector space is an optimal solution.
dim | The dimension of the vector space enclosing *this (optional argument with default value ![]() |
std::length_error | Thrown if dim exceeds max_space_dimension() . |
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 , the objective function
obj
and optimization mode mode
; those dimensions whose indices occur in int_vars
are constrained to take an integer value.
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 ![]() |
mode | The optimization mode (optional argument with default value MAXIMIZATION ). |
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 . |
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 , the objective function
obj
and optimization mode mode
.
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 ![]() |
mode | The optimization mode (optional argument with default value MAXIMIZATION ). |
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
.
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 ![]() |
mode | The optimization mode (optional argument with default value MAXIMIZATION ). |
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 . |
|
inline |
Resets *this
to be equal to the trivial MIP problem.
The space dimension is reset to .
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.
m | The number of dimensions to add. |
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.
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.
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.
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
.
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
.
true
if and only if the MIP problem is satisfiable. MIP_Problem_Status Parma_Polyhedra_Library::MIP_Problem::solve | ( | ) | const |
Optimizes the MIP 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 is the result of evaluating the objective function on
evaluating_point
.
evaluating_point | The point on which the objective function will be evaluated. |
numer | On exit will contain the numerator of the evaluated value. |
denom | On exit will contain the denominator of the evaluated value. |
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.
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.
std::domain_error | Thrown if *this does not not have an optimizing point, i.e., if the MIP problem is unbounded or not satisfiable. |
|
inline |
Sets numer
and denom
so that is the solution of the optimization problem.
std::domain_error | Thrown if *this does not not have an optimizing point, i.e., if the MIP problem is unbounded or not satisfiable. |
|
related |
Output operator.
|
related |
Swaps x
with y
.
|
related |