PPL 1.0

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes

- Class List
- Class Hierarchy
- Class Members

Classes | Public Types | Public Member Functions | Static Public Member Functions | Related Functions
Parma_Polyhedra_Library::MIP_Problem Class Reference
C++ Language Interface

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

`#include <ppl.hh>`

List of all members.

## 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.
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 , 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 , 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_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.
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 &numer, Coefficient &denom) const
| Sets `num` and `denom` so that is the result of evaluating the objective function on `evaluating_point`.
const Generator & | feasible_point () const
| Returns a feasible point for `*this`, if it exists.
const Generator & | optimizing_point () const
| Returns an optimal point for `*this`, if it exists.
void | optimal_value (Coefficient &numer, Coefficient &denom) const
| Sets `numer` and `denom` so that 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 | 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.
void | swap (MIP_Problem &x, MIP_Problem &y)
| Swaps `x` with `y`.
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.

## Member Enumeration Documentation

enum Parma_Polyhedra_Library::MIP_Problem::Control_Parameter_Name

Names of MIP problems' control parameters.

Enumerator:

  PRICING | The pricing rule.

enum Parma_Polyhedra_Library::MIP_Problem::Control_Parameter_Value

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

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`
| ) |  |

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.

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

Builds an MIP problem having space dimension `dim` from the sequence of constraints in the range , 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 ).
  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 ).
  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 .

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 & | numer,
|  | Coefficient & | denom
| ) |  | const

Sets `num` and `denom` so that is the result of evaluating the objective function on `evaluating_point`.

Parameters:

  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.

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` 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 is the solution of the optimization problem.

Exceptions:

  std::domain_error | Thrown 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:

- ppl.hh