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_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 $\frac{\mathtt{numer}}{\mathtt{denom}}$ is the result of evaluating the objective function on `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 $\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

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 $[\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 ).
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 $[\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 ).
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 $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 &	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_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 $\frac{\mathtt{numer}}{\mathtt{denom}}$ 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
	)

void swap	(	MIP_Problem &	x,
		MIP_Problem &	y
	)

void swap	(	MIP_Problem &	x,
		MIP_Problem &	y
	)

ppl.hh

Classes

Public Types

Public Member Functions

Static Public Member Functions

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation