Parma_Polyhedra_Library::PIP_Problem Class Reference

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

#include <ppl.hh>

Public Types
enum	Control_Parameter_Name { CUTTING_STRATEGY, PIVOT_ROW_STRATEGY }
	Possible names for PIP_Problem control parameters. More...
enum	Control_Parameter_Value {   CUTTING_STRATEGY_FIRST, CUTTING_STRATEGY_DEEPEST, CUTTING_STRATEGY_ALL, PIVOT_ROW_STRATEGY_FIRST,   PIVOT_ROW_STRATEGY_MAX_COLUMN }
	Possible values for PIP_Problem 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
	PIP_Problem (dimension_type dim=0)
	Builds a trivial PIP problem. More...
template<typename In >
	PIP_Problem (dimension_type dim, In first, In last, const Variables_Set &p_vars)
	Builds a PIP problem having space dimension dim from the sequence of constraints in the range ; those dimensions whose indices occur in p_vars are interpreted as parameters. More...
	PIP_Problem (const PIP_Problem &y)
	Ordinary copy-constructor.
	~PIP_Problem ()
	Destructor.
PIP_Problem &	operator= (const PIP_Problem &y)
	Assignment operator.
dimension_type	space_dimension () const
	Returns the space dimension of the PIP problem.
const Variables_Set &	parameter_space_dimensions () const
	Returns a set containing all the variables' indexes representing the parameters of the PIP problem.
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.
void	clear ()
	Resets *this to be equal to the trivial PIP problem. More...
void	add_space_dimensions_and_embed (dimension_type m_vars, dimension_type m_params)
	Adds m_vars + m_params new space dimensions and embeds the old PIP problem in the new vector space. More...
void	add_to_parameter_space_dimensions (const Variables_Set &p_vars)
	Sets the space dimensions whose indexes which are in set p_vars to be parameter space dimensions. More...
void	add_constraint (const Constraint &c)
	Adds a copy of constraint c to the PIP problem. More...
void	add_constraints (const Constraint_System &cs)
	Adds a copy of the constraints in cs to the PIP problem. More...
bool	is_satisfiable () const
	Checks satisfiability of *this. More...
PIP_Problem_Status	solve () const
	Optimizes the PIP problem. More...
PIP_Tree	solution () const
	Returns a feasible solution for *this, if it exists. More...
PIP_Tree	optimizing_solution () const
	Returns an optimizing solution for *this, if it exists. More...
bool	OK () const
	Checks if all the invariants are satisfied.
void	print_solution (std::ostream &s, int indent=0) const
	Prints on s the solution computed for *this. More...
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 (PIP_Problem &y)
	Swaps *this with y.
Control_Parameter_Value	get_control_parameter (Control_Parameter_Name name) const
	Returns the value of control parameter name.
void	set_control_parameter (Control_Parameter_Value value)
	Sets control parameter value.
void	set_big_parameter_dimension (dimension_type big_dim)
	Sets the dimension for the big parameter to big_dim.
dimension_type	get_big_parameter_dimension () const
	Returns the space dimension for the big parameter. More...

Static Public Member Functions
static dimension_type	max_space_dimension ()
	Returns the maximum space dimension a PIP_Problem can handle.

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &s, const PIP_Problem &pip)
	Output operator. More...
void	swap (PIP_Problem &x, PIP_Problem &y)
	Swaps x with y. More...
void	swap (PIP_Problem &x, PIP_Problem &y)

Detailed Description

A Parametric Integer (linear) Programming problem.

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

• the dimension of the vector space;
• the subset of those dimensions of the vector space that are interpreted as integer parameters (the other space dimensions are interpreted as non-parameter integer variables);
• a finite set of linear equality and (strict or non-strict) inequality constraints involving variables and/or parameters; these constraints are used to define:
  • the feasible region, if they involve one or more problem variable (and maybe some parameters);
  • the initial context, if they only involve the parameters;
• optionally, the so-called big parameter, i.e., a problem parameter to be considered arbitrarily big.

Note that all problem variables and problem parameters are assumed to take non-negative integer values, so that there is no need to specify non-negativity constraints.

The class provides support for the (incremental) solution of the PIP problem based on variations of the revised simplex method and on Gomory cut generation techniques.

The solution for a PIP problem is the lexicographic minimum of the integer points of the feasible region, expressed in terms of the parameters. As the problem to be solved only involves non-negative variables and parameters, the problem will always be either unfeasible or optimizable.

As the feasibility and the solution value of a PIP problem depend on the values of the parameters, the solution is a binary decision tree, dividing the context parameter set into subsets. The tree nodes are of two kinds:

• Decision nodes. These are internal tree nodes encoding one or more linear tests on the parameters; if all the tests are satisfied, then the solution is the node's true child; otherwise, the solution is the node's false child;
• Solution nodes. These are leaf nodes in the tree, encoding the solution of the problem in the current context subset, where each variable is defined in terms of a linear expression of the parameters. Solution nodes also optionally embed a set of parameter constraints: if all these constraints are satisfied, the solution is described by the node, otherwise the problem has no solution.

It may happen that a decision node has no false child. This means that there is no solution if at least one of the corresponding constraints is not satisfied. Decision nodes having two or more linear tests on the parameters cannot have a false child. Decision nodes always have a true child.

Both kinds of tree nodes may also contain the definition of extra parameters which are artificially introduced by the solver to enforce an integral solution. Such artificial parameters are defined by the integer division of a linear expression on the parameters by an integer coefficient.

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 PIP_Problem: currently, incremental resolution supports the addition of space dimensions, the addition of parameters and the addition of constraints.

Example problem

An example PIP problem can be defined the following:

3*j >= -2*i+8
j <= 4*i - 4
i <= n
j <= m

where i and j are the problem variables and n and m are the problem parameters. This problem can be optimized; the resulting solution tree may be represented as follows:

if 7*n >= 10 then
  if 7*m >= 12 then
    {i = 2 ; j = 2}
  else
    Parameter P = (m) div 2
    if 2*n + 3*m >= 8 then
      {i = -m - P + 4 ; j = m}
    else
      _|_
else
  _|_

The solution tree starts with a decision node depending on the context constraint 7*n >= 10. If this constraint is satisfied by the values assigned to the problem parameters, then the (textually first) then branch is taken, reaching the true child of the root node (which in this case is another decision node); otherwise, the (textually last) else branch is taken, for which there is no corresponding false child.

The notation, also called bottom, denotes the lexicographic minimum of an empty set of solutions, here meaning the corresponding subproblem is unfeasible.

Notice that a tree node may introduce new (non-problem) parameters, as is the case for parameter P in the (textually first) else branch above. These artificial parameters are only meaningful inside the subtree where they are defined and are used to define the parametric values of the problem variables in solution nodes (e.g., the {i,j} vector in the textually third then branch).

Context restriction

The above solution is correct in an unrestricted initial context, meaning all possible values are allowed for the parameters. If we restrict the context with the following parameter inequalities:

m >= n
n >= 5

then the resulting optimizing tree will be a simple solution node:

{i = 2 ; j = 2}

Creating the PIP_Problem object

The PIP_Problem object corresponding to the above example can be created as follows:

Variable i(0);
Variable j(1);
Variable n(2);
Variable m(3);
Variables_Set params(n, m);
Constraint_System cs;
cs.insert(3*j >= -2*i+8);
cs.insert(j <= 4*i - 4);
cs.insert(j <= m);
cs.insert(i <= n);
PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);

If you want to restrict the initial context, simply add the parameter constraints the same way as for normal constraints.

cs.insert(m >= n);
cs.insert(n >= 5);

Solving the problem

Once the PIP_Problem object has been created, you can start the resolution of the problem by calling the solve() method:

PIP_Problem_Status status = pip.solve();

where the returned status indicates if the problem has been optimized or if it is unfeasible for any possible configuration of the parameter values. The resolution process is also started if an attempt is made to get its solution, as follows:

const PIP_Tree_Node* node = pip.solution();

In this case, an unfeasible problem will result in an empty solution tree, i.e., assigning a null pointer to node.

Printing the solution tree

A previously computed solution tree may be printed as follows:

pip.print_solution(std::cout);

This will produce the following output (note: variables and parameters are printed according to the default output function; see Variable::set_output_function):

if 7*C >= 10 then
  if 7*D >= 12 then
    {2 ; 2}
  else
    Parameter E = (D) div 2
    if 2*C + 3*D >= 8 then
      {-D - E + 4 ; D}
    else
      _|_
else
  _|_

Spanning the solution tree

A parameter assignment for a PIP problem binds each of the problem parameters to a non-negative integer value. After fixing a parameter assignment, the ``spanning'' of the PIP problem solution tree refers to the process whereby the solution tree is navigated, starting from the root node: the value of artificial parameters is computed according to the parameter assignment and the node's constraints are evaluated, thereby descending in either the true or the false subtree of decision nodes and eventually reaching a solution node or a bottom node. If a solution node is found, each of the problem variables is provided with a parametric expression, which can be evaluated to a fixed value using the given parameter assignment and the computed values for artificial parameters.

The coding of the spanning process can be done as follows. First, the root of the PIP solution tree is retrieved:

const PIP_Tree_Node* node = pip.solution();

If node represents an unfeasible solution (i.e., ), its value will be 0. For a non-null tree node, the virtual methods PIP_Tree_Node::as_decision() and PIP_Tree_Node::as_solution() can be used to check whether the node is a decision or a solution node:

const PIP_Solution_Node* sol = node->as_solution();
if (sol != 0) {
  // The node is a solution node
  ...
}
else {
  // The node is a decision node
  const PIP_Decision_Node* dec = node->as_decision();
  ...
}

The true (resp., false) child node of a Decision Node may be accessed by using method PIP_Decision_Node::child_node(bool), passing true (resp., false) as the input argument.

Artificial parameters

A PIP_Tree_Node::Artificial_Parameter object represents the result of the integer division of a Linear_Expression (on the other parameters, including the previously-defined artificials) by an integer denominator (a Coefficient object). The dimensions of the artificial parameters (if any) in a tree node have consecutive indices starting from dim+1, where the value of dim is computed as follows:

• for the tree root node, dim is the space dimension of the PIP_Problem;
• for any other node of the tree, it is recursively obtained by adding the value of dim computed for the parent node to the number of artificial parameters defined in the parent node.

Since the numbering of dimensions for artificial parameters follows the rule above, the addition of new problem variables and/or new problem parameters to an already solved PIP_Problem object (as done when incrementally solving a problem) will result in the systematic renumbering of all the existing artificial parameters.

Node constraints

All kind of tree nodes can contain context constraints. Decision nodes always contain at least one of them. The node's local constraint system can be obtained using method PIP_Tree_Node::constraints. These constraints only involve parameters, including both the problem parameters and the artificial parameters that have been defined in nodes occurring on the path from the root node to the current node. The meaning of these constraints is as follows:

• On a decision node, if all tests in the constraints are true, then the solution is the true child; otherwise it is the false child.
• On a solution node, if the (possibly empty) system of constraints evaluates to true for a given parameter assignment, then the solution is described by the node; otherwise the solution is (i.e., the problem is unfeasible for that parameter assignment).

Getting the optimal values for the variables

After spanning the solution tree using the given parameter assignment, if a solution node has been reached, then it is possible to retrieve the parametric expression for each of the problem variables using method PIP_Solution_Node::parametric_values. The retrieved expression will be defined in terms of all the parameters (problem parameters and artificial parameters defined along the path).

Solving maximization problems

You can solve a lexicographic maximization problem by reformulating its constraints using variable substitution. Proceed the following steps:

• Create a big parameter (see PIP_Problem::set_big_parameter_dimension), which we will call .
• Reformulate each of the maximization problem constraints by substituting each variable with an expression of the form , where the variables are positive variables to be minimized.
• Solve the lexicographic minimum for the variable vector.
• In the solution expressions, the values of the variables will be expressed in the form: . To get back the value of the expression of each variable, just apply the formula: .

Note that if the resulting expression of one of the variables is not in the form, this means that the sign-unrestricted problem is unbounded.

You can choose to maximize only a subset of the variables while minimizing the other variables. In that case, just apply the variable substitution method on the variables you want to be maximized. The variable optimization priority will still be in lexicographic order.

Example: consider you want to find the lexicographic maximum of the vector, under the constraints:

where is a parameter.

After variable substitution, the constraints become:

The code for creating the corresponding problem object is the following:

Variable x(0);
Variable y(1);
Variable p(2);
Variable M(3);
Variables_Set params(p, M);
Constraint_System cs;
cs.insert(M - y >= 2*M - 2*x - 4);
cs.insert(M - y <= -M + x + p);
PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);
pip.set_big_parameter_dimension(3);     // M is the big parameter

Solving the problem provides the following solution:

Parameter E = (C + 1) div 3
{D - E - 1 ; -C + D + E + 1}

Under the notations above, the solution is:

Performing substitution again provides us with the values of the original variables:

Allowing variables to be arbitrarily signed

You can deal with arbitrarily signed variables by reformulating the constraints using variable substitution. Proceed the following steps:

• Create a big parameter (see PIP_Problem::set_big_parameter_dimension), which we will call .
• Reformulate each of the maximization problem constraints by substituting each variable with an expression of the form , where the variables are positive.
• Solve the lexicographic minimum for the variable vector.
• The solution expression can be read in the form:
• In the solution expressions, the values of the variables will be expressed in the form: . To get back the value of the expression of each signed variable, just apply the formula: .

Note that if the resulting expression of one of the variables is not in the form, this means that the sign-unrestricted problem is unbounded.

You can choose to define only a subset of the variables to be sign-unrestricted. In that case, just apply the variable substitution method on the variables you want to be sign-unrestricted.

Example: consider you want to find the lexicographic minimum of the vector, where the and variables are sign-unrestricted, under the constraints:

where is a parameter.

After variable substitution, the constraints become:

The code for creating the corresponding problem object is the following:

Variable x(0);
Variable y(1);
Variable p(2);
Variable M(3);
Variables_Set params(p, M);
Constraint_System cs;
cs.insert(y - M >= -2*x + 2*M - 4);
cs.insert(2*y - 2*M <= x - M + 2*p);
PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);
pip.set_big_parameter_dimension(3);     // M is the big parameter

Solving the problem provides the following solution:

Parameter E = (2*C + 3) div 5
{D - E - 1 ; D + 2*E - 2}

Under the notations above, the solution is:

Performing substitution again provides us with the values of the original variables:

Allowing parameters to be arbitrarily signed

You can consider a parameter arbitrarily signed by replacing with , where both and are positive parameters. To represent a set of arbitrarily signed parameters, replace each parameter with , where is the minimum negative value of all parameters.

Minimizing a linear cost function

Lexicographic solving can be used to find the parametric minimum of a linear cost function.

Suppose the variables are named , and the parameters . You can minimize a linear cost function by simply adding the constraint to the constraint system. As lexicographic minimization ensures is minimized in priority, and because is forced by a constraint to be superior or equal to the cost function, optimal solutions of the problem necessarily ensure that the solution value of is the optimal value of the cost function.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::PIP_Problem::PIP_Problem ( dimension_type  dim = 0 )

explicit

Builds a trivial PIP problem.

A trivial PIP problem requires to compute the lexicographic minimum on a vector space under no constraints and with no parameters: due to the implicit non-negativity constraints, 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::PIP_Problem::PIP_Problem	(	dimension_type	dim,
		In	first,
		In	last,
		const Variables_Set &	p_vars
	)

Builds a PIP problem having space dimension dim from the sequence of constraints in the range ; those dimensions whose indices occur in p_vars are interpreted as parameters.

Parameters

dim	The dimension of the vector space (variables and parameters) 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.
p_vars	The set of variables' indexes that are interpreted as parameters.

Exceptions

std::length_error	Thrown if dim exceeds max_space_dimension().
std::invalid_argument	Thrown if the space dimension of a constraint in the sequence (resp., the parameter variables) is strictly greater than dim.

Member Function Documentation

void Parma_Polyhedra_Library::PIP_Problem::clear

(

)

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

The space dimension is reset to .

void Parma_Polyhedra_Library::PIP_Problem::add_space_dimensions_and_embed	(	dimension_type	m_vars,
		dimension_type	m_params
	)

Adds m_vars + m_params new space dimensions and embeds the old PIP problem in the new vector space.

Parameters

m_vars	The number of space dimensions to add that are interpreted as PIP problem variables (i.e., non parameters). These are added before adding the m_params parameters.
m_params	The number of space dimensions to add that are interpreted as PIP problem parameters. These are added after having added the m_vars problem variables.

Exceptions

std::length_error

Thrown if adding m_vars + m_params 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 PIP problem; they are initially unconstrained.

void Parma_Polyhedra_Library::PIP_Problem::add_to_parameter_space_dimensions

(

const Variables_Set &

p_vars

)

Sets the space dimensions whose indexes which are in set p_vars to be parameter space dimensions.

Exceptions

std::invalid_argument

Thrown if some index in p_vars does not correspond to a space dimension in *this.

void Parma_Polyhedra_Library::PIP_Problem::add_constraint

(

const Constraint &

c

)

Adds a copy of constraint c to the PIP problem.

Exceptions

std::invalid_argument

Thrown if the space dimension of c is strictly greater than the space dimension of *this.

void Parma_Polyhedra_Library::PIP_Problem::add_constraints

(

const Constraint_System &

cs

)

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

Exceptions

std::invalid_argument

Thrown if the space dimension of constraint system cs is strictly greater than the space dimension of *this.

bool Parma_Polyhedra_Library::PIP_Problem::is_satisfiable

(

)

const

Checks satisfiability of *this.

Returns

true if and only if the PIP problem is satisfiable.

PIP_Problem_Status Parma_Polyhedra_Library::PIP_Problem::solve

(

)

const

Optimizes the PIP problem.

Returns

A PIP_Problem_Status flag indicating the outcome of the optimization attempt (unfeasible or optimized problem).

PIP_Tree Parma_Polyhedra_Library::PIP_Problem::solution

(

)

const

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

A null pointer is returned for an unfeasible PIP problem.

PIP_Tree Parma_Polyhedra_Library::PIP_Problem::optimizing_solution

(

)

const

Returns an optimizing solution for *this, if it exists.

A null pointer is returned for an unfeasible PIP problem.

void Parma_Polyhedra_Library::PIP_Problem::print_solution	(	std::ostream &	s,
		int	indent = 0
	)		const

Prints on s the solution computed for *this.

Parameters

s	The output stream.
indent	An indentation parameter (default value 0).

Exceptions

std::logic_error

Thrown if trying to print the solution when the PIP problem still has to be solved.

dimension_type Parma_Polyhedra_Library::PIP_Problem::get_big_parameter_dimension ( ) const

inline

Returns the space dimension for the big parameter.

If a big parameter was not set, returns not_a_dimension().

Friends And Related Function Documentation

std::ostream & operator<< ( std::ostream &  s, const PIP_Problem &  pip  )

related

Output operator.

void swap ( PIP_Problem &  x, PIP_Problem &  y  )

related

Swaps x with y.

void swap ( PIP_Problem &  x, PIP_Problem &  y  )

related

---

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

• ppl.hh