PPL 1.0

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

- Class List
- Class Hierarchy
- Class Members

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

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

`#include <ppl.hh>`

List of all members.

## 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.
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.
| 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.
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.
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.
void | add_constraint (const Constraint &c)
| Adds a copy of constraint `c` to the PIP problem.
void | add_constraints (const Constraint_System &cs)
| Adds a copy of the constraints in `cs` to the PIP problem.
bool | is_satisfiable () const
| Checks satisfiability of `*this`.
PIP_Problem_Status | solve () const
| Optimizes the PIP problem.
PIP_Tree | solution () const
| Returns a feasible solution for `*this`, if it exists.
PIP_Tree | optimizing_solution () const
| Returns an optimizing solution for `*this`, if it exists.
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`.
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.

## 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.
void | swap (PIP_Problem &x, PIP_Problem &y)
| Swaps `x` with `y`.
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.

## Member Enumeration Documentation

enum Parma_Polyhedra_Library::PIP_Problem::Control_Parameter_Name

Possible names for PIP_Problem control parameters.

Enumerator:

  CUTTING_STRATEGY | Cutting strategy.
  PIVOT_ROW_STRATEGY | Pivot row strategy.

enum Parma_Polyhedra_Library::PIP_Problem::Control_Parameter_Value

Possible values for PIP_Problem control parameters.

Enumerator:

  CUTTING_STRATEGY_FIRST | Choose the first non-integer row.
  CUTTING_STRATEGY_DEEPEST | Choose row which generates the deepest cut.
  CUTTING_STRATEGY_ALL | Always generate all possible cuts.
  PIVOT_ROW_STRATEGY_FIRST | Choose the first row with negative parameter sign.
  PIVOT_ROW_STRATEGY_MAX_COLUMN | Choose a row that generates a lexicographically maximal pivot column.

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