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

#include <PIP_Problem.defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::PIP_Problem:

Public Types
enum	Control_Parameter_Name { CUTTING_STRATEGY, PIVOT_ROW_STRATEGY, CONTROL_PARAMETER_NAME_SIZE }
	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, CONTROL_PARAMETER_VALUE_SIZE }
	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 $[\mathrm{first}, \mathrm{last})$ ; 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.
Private Types
enum	Status { UNSATISFIABLE, OPTIMIZED, PARTIALLY_SATISFIABLE }
	An enumerated type describing the internal status of the PIP problem. More...
typedef std::vector< Constraint >	Constraint_Sequence
	A type alias for a sequence of constraints.
Private Member Functions
void	control_parameters_init ()
	Initializes the control parameters with default values.
void	control_parameters_copy (const PIP_Problem &y)
	Copies the control parameters from problem object `y`.
Private Attributes
dimension_type	external_space_dim
	The dimension of the vector space.
dimension_type	internal_space_dim
	The space dimension of the current (partial) solution of the PIP problem; it may be smaller than `external_space_dim`.
Status	status
	The internal state of the MIP problem.
PIP_Tree_Node *	current_solution
	The current solution decision tree.
Constraint_Sequence	input_cs
	The sequence of constraints describing the feasible region.
dimension_type	first_pending_constraint
	The first index of `input_cs' containing a pending constraint.
Variables_Set	parameters
	A set containing all the indices of space dimensions that are interpreted as problem parameters.
Matrix	initial_context
	The initial context.
Control_Parameter_Value	control_parameters [CONTROL_PARAMETER_NAME_SIZE]
	The control parameters for the problem object.
dimension_type	big_parameter_dimension
	The dimension for the big parameter, or `not_a_dimension()` if not set.
Friends
class	PIP_Solution_Node
Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &s, const PIP_Problem &pip)
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 $\perp$ 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., $\perp$ ), 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 $\perp$ (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:
$\left\{\begin{array}{l} y \geq 2x - 4\\ y \leq -x + p \end{array}\right.$

: where is a parameter.

: After variable substitution, the constraints become:
$\left\{\begin{array}{l} M - y \geq 2M - 2x - 4\\ M - y \leq -M + x + p \end{array}\right.$

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:

$\left\{\begin{array}{l} x' = M - \left\lfloor\frac{p+1}{3}\right\rfloor - 1 \\ y' = M - p + \left\lfloor\frac{p+1}{3}\right\rfloor + 1 \end{array}\right.$

: Performing substitution again provides us with the values of the original variables:
$\left\{\begin{array}{l} x = \left\lfloor\frac{p+1}{3}\right\rfloor + 1 \\ y = p - \left\lfloor\frac{p+1}{3}\right\rfloor - 1 \end{array}\right.$

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:
$\left\{\begin{array}{l} y \geq -2x - 4\\ 2y \leq x + 2p \end{array}\right.$

: where is a parameter.

: After variable substitution, the constraints become:
$\left\{\begin{array}{l} y' - M \geq -2x' + 2M - 4\\ 2y' - 2M \leq x' - M + 2p \end{array}\right.$

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:

$\left\{\begin{array}{l} x' = M - \left\lfloor\frac{2p+3}{5}\right\rfloor - 1 \\ y' = M + 2\left\lfloor\frac{2p+3}{5}\right\rfloor - 2 \end{array}\right.$

: Performing substitution again provides us with the values of the original variables:
$\left\{\begin{array}{l} x = -\left\lfloor\frac{2p+3}{5}\right\rfloor - 1 \\ y = 2\left\lfloor\frac{2p+3}{5}\right\rfloor - 2 \end{array}\right.$

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 $x_1, x_2, \dots, x_n$ , and the parameters $p_1, p_2, \dots, p_m$ . You can minimize a linear cost function $f(x_2, \dots, x_n, p_1, \dots, p_m)$ by simply adding the constraint $x_1 \geq f(x_2, \dots, x_n, p_1, \dots, p_m)$ 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.

Definition at line 495 of file PIP_Problem.defs.hh.

Member Typedef Documentation

typedef Constraint_Sequence::const_iterator Parma_Polyhedra_Library::PIP_Problem::const_iterator

A type alias for the read-only iterator on the constraints defining the feasible region.

Definition at line 574 of file PIP_Problem.defs.hh.

typedef std::vector<Constraint> Parma_Polyhedra_Library::PIP_Problem::Constraint_Sequence

private

A type alias for a sequence of constraints.

Definition at line 567 of file PIP_Problem.defs.hh.

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.
CONTROL_PARAMETER_NAME_SIZE	Number of different enumeration values.

Definition at line 710 of file PIP_Problem.defs.hh.

                              {
    CUTTING_STRATEGY,
    PIVOT_ROW_STRATEGY,
#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
    CONTROL_PARAMETER_NAME_SIZE
  };

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.
CONTROL_PARAMETER_VALUE_SIZE	Number of different enumeration values.

Definition at line 722 of file PIP_Problem.defs.hh.

                               {
    CUTTING_STRATEGY_FIRST,
    CUTTING_STRATEGY_DEEPEST,
    CUTTING_STRATEGY_ALL,

    PIVOT_ROW_STRATEGY_FIRST,
    PIVOT_ROW_STRATEGY_MAX_COLUMN,

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
    CONTROL_PARAMETER_VALUE_SIZE
  };

enum Parma_Polyhedra_Library::PIP_Problem::Status

private

An enumerated type describing the internal status of the PIP problem.

Enumerator:

UNSATISFIABLE	The PIP problem is unsatisfiable.
OPTIMIZED	The PIP problem is optimized; the solution tree has been computed.
PARTIALLY_SATISFIABLE	The feasible region of the PIP problem has been changed by adding new variables, parameters or constraints; a feasible solution for the old feasible region is still available.

Definition at line 775 of file PIP_Problem.defs.hh.

              {
    UNSATISFIABLE,
    OPTIMIZED,
    PARTIALLY_SATISFIABLE
  };

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

Definition at line 47 of file PIP_Problem.cc.

References control_parameters_init(), max_space_dimension(), OK(), and PPL_ASSERT.

  : external_space_dim(dim),
    internal_space_dim(0),
    status(PARTIALLY_SATISFIABLE),
    current_solution(0),
    input_cs(),
    first_pending_constraint(0),
    parameters(),
    initial_context(),
    big_parameter_dimension(not_a_dimension()) {
  // Check for space dimension overflow.
  if (dim > max_space_dimension())
    throw std::length_error("PPL::PIP_Problem::PIP_Problem(dim):\n"
                            "dim exceeds the maximum allowed "
                            "space dimension.");
  control_parameters_init();
  PPL_ASSERT(OK());
}

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 $[\mathrm{first}, \mathrm{last})$ ; 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`.

Definition at line 32 of file PIP_Problem.templates.hh.

References control_parameters_init(), external_space_dim, input_cs, max_space_dimension(), OK(), PPL_ASSERT, and Parma_Polyhedra_Library::Variables_Set::space_dimension().

  : external_space_dim(dim),
    internal_space_dim(0),
    status(PARTIALLY_SATISFIABLE),
    current_solution(0),
    input_cs(),
    first_pending_constraint(0),
    parameters(p_vars),
    initial_context(),
    big_parameter_dimension(not_a_dimension()) {
  // Check that integer Variables_Set does not exceed the space dimension
  // of the problem.
  if (p_vars.space_dimension() > external_space_dim) {
    std::ostringstream s;
    s << "PPL::PIP_Problem::PIP_Problem(dim, first, last, p_vars):\n"
      << "dim == " << external_space_dim
      << " and p_vars.space_dimension() == "
      << p_vars.space_dimension()
      << " are dimension incompatible.";
    throw std::invalid_argument(s.str());
  }

  // Check for space dimension overflow.
  if (dim > max_space_dimension())
    throw std::length_error("PPL::PIP_Problem::"
                            "PIP_Problem(dim, first, last, p_vars):\n"
                            "dim exceeds the maximum allowed "
                            "space dimension.");
  // Check the constraints.
  for (In i = first; i != last; ++i) {
    if (i->space_dimension() > dim) {
      std::ostringstream s;
      s << "PPL::PIP_Problem::"
        << "PIP_Problem(dim, first, last, p_vars):\n"
        << "range [first, last) contains a constraint having space "
        << "dimension == " << i->space_dimension()
        << " that exceeds this->space_dimension == " << dim << ".";
      throw std::invalid_argument(s.str());
    }
    input_cs.push_back(*i);
  }
  control_parameters_init();
  PPL_ASSERT(OK());
}

Parma_Polyhedra_Library::PIP_Problem::PIP_Problem ( const PIP_Problem & y )

Ordinary copy-constructor.

Definition at line 66 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::clone(), control_parameters_copy(), current_solution, OK(), PPL_ASSERT, and Parma_Polyhedra_Library::PIP_Tree_Node::set_owner().

  : external_space_dim(y.external_space_dim),
    internal_space_dim(y.internal_space_dim),
    status(y.status),
    current_solution(0),
    input_cs(y.input_cs),
    first_pending_constraint(y.first_pending_constraint),
    parameters(y.parameters),
    initial_context(y.initial_context),
    big_parameter_dimension(y.big_parameter_dimension) {
  if (y.current_solution != 0) {
    current_solution = y.current_solution->clone();
    current_solution->set_owner(this);
  }
  control_parameters_copy(y);
  PPL_ASSERT(OK());
}

Parma_Polyhedra_Library::PIP_Problem::~PIP_Problem ( )

Destructor.

Definition at line 84 of file PIP_Problem.cc.

                             {
  delete current_solution;
}

Member Function Documentation

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.

Definition at line 644 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::Constraint::space_dimension().

                                                  {
  if (c.space_dimension() > external_space_dim) {
    std::ostringstream s;
    s << "PPL::PIP_Problem::add_constraint(c):\n"
      << "dim == "<< external_space_dim << " and c.space_dimension() == "
      << c.space_dimension() << " are dimension incompatible.";
    throw std::invalid_argument(s.str());
  }
  input_cs.push_back(c);
  // Update problem status.
  if (status != UNSATISFIABLE)
    status = PARTIALLY_SATISFIABLE;
}

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.

Definition at line 659 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::Constraint_System::begin(), and Parma_Polyhedra_Library::Constraint_System::end().

                                                           {
  for (Constraint_System::const_iterator ci = cs.begin(),
         ci_end = cs.end(); ci != ci_end; ++ci)
    add_constraint(*ci);
}

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.

Definition at line 584 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::max_space_dimension(), and PPL_ASSERT.

                                                                {
  // Adding no space dims at all is a no-op:
  // this avoids invalidating problem status (if it was optimized).
  if (m_vars == 0 && m_params == 0)
    return;

  // The space dimension of the resulting PIP problem should not
  // overflow the maximum allowed space dimension.
  dimension_type available = max_space_dimension() - space_dimension();
  bool should_throw = (m_vars > available);
  if (!should_throw) {
    available -= m_vars;
    should_throw = (m_params > available);
  }
  if (should_throw)
    throw std::length_error("PPL::PIP_Problem::"
                            "add_space_dimensions_and_embed(m_v, m_p):\n"
                            "adding m_v+m_p new space dimensions exceeds "
                            "the maximum allowed space dimension.");
  // First add PIP variables ...
  external_space_dim += m_vars;
  // ... then add PIP parameters.
  for (dimension_type i = m_params; i-- > 0; ) {
    parameters.insert(Variable(external_space_dim));
    ++external_space_dim;
  }
  // Update problem status.
  if (status != UNSATISFIABLE)
    status = PARTIALLY_SATISFIABLE;
  PPL_ASSERT(OK());
}

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.

Definition at line 619 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::Variables_Set::space_dimension().

                                                               {
  if (p_vars.space_dimension() > external_space_dim)
    throw std::invalid_argument("PPL::PIP_Problem::"
                                "add_to_parameter_space_dimension(p_vars):\n"
                                "*this and p_vars are dimension "
                                "incompatible.");
  const dimension_type original_size = parameters.size();
  parameters.insert(p_vars.begin(), p_vars.end());
  // Do not allow to turn variables into parameters.
  for (Variables_Set::const_iterator p = p_vars.begin(),
         end = p_vars.end(); p != end; ++p) {
    if (*p < internal_space_dim) {
      throw std::invalid_argument("PPL::PIP_Problem::"
                                  "add_to_parameter_space_dimension(p_vars):"
                                  "p_vars contain variable indices.");
    }
  }

  // If a new parameter was inserted, set the internal status to
  // PARTIALLY_SATISFIABLE.
  if (parameters.size() != original_size && status != UNSATISFIABLE)
    status = PARTIALLY_SATISFIABLE;
}

void Parma_Polyhedra_Library::PIP_Problem::ascii_dump ( ) const

Writes to std::cerr an ASCII representation of *this.

void Parma_Polyhedra_Library::PIP_Problem::ascii_dump ( std::ostream & s ) const

Writes to s an ASCII representation of *this.

Definition at line 363 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::PIP_Decision_Node::as_decision(), Parma_Polyhedra_Library::PIP_Solution_Node::as_solution(), Parma_Polyhedra_Library::ascii_dump(), Parma_Polyhedra_Library::PIP_Solution_Node::ascii_dump(), PPL_ASSERT, and value.

                                              {
  using namespace IO_Operators;
  s << "\nexternal_space_dim: " << external_space_dim << "\n";
  s << "\ninternal_space_dim: " << internal_space_dim << "\n";

  const dimension_type input_cs_size = input_cs.size();

  s << "\ninput_cs( " << input_cs_size << " )\n";
  for (dimension_type i = 0; i < input_cs_size; ++i)
    input_cs[i].ascii_dump(s);

  s << "\nfirst_pending_constraint: " <<  first_pending_constraint << "\n";

  s << "\nstatus: ";
  switch (status) {
  case UNSATISFIABLE:
    s << "UNSATISFIABLE";
    break;
  case OPTIMIZED:
    s << "OPTIMIZED";
    break;
  case PARTIALLY_SATISFIABLE:
    s << "PARTIALLY_SATISFIABLE";
    break;
  }
  s << "\n";

  s << "\nparameters";
  parameters.ascii_dump(s);

  s << "\ninitial_context\n";
  initial_context.ascii_dump(s);

  s << "\ncontrol_parameters\n";
  for (dimension_type i = 0; i < CONTROL_PARAMETER_NAME_SIZE; ++i) {
    Control_Parameter_Value value = control_parameters[i];
    switch (value) {
    case CUTTING_STRATEGY_FIRST:
      s << "CUTTING_STRATEGY_FIRST";
      break;
    case CUTTING_STRATEGY_DEEPEST:
      s << "CUTTING_STRATEGY_DEEPEST";
      break;
    case CUTTING_STRATEGY_ALL:
      s << "CUTTING_STRATEGY_ALL";
      break;
    case PIVOT_ROW_STRATEGY_FIRST:
      s << "PIVOT_ROW_STRATEGY_FIRST";
      break;
    case PIVOT_ROW_STRATEGY_MAX_COLUMN:
      s << "PIVOT_ROW_STRATEGY_MAX_COLUMN";
      break;
    default:
      s << "Invalid control parameter value";
    }
    s << "\n";
  }

  s << "\nbig_parameter_dimension: " << big_parameter_dimension << "\n";

  s << "\ncurrent_solution: ";
  if (current_solution == 0)
    s << "BOTTOM\n";
  else if (const PIP_Decision_Node* dec = current_solution->as_decision()) {
    s << "DECISION\n";
    dec->ascii_dump(s);
  }
  else {
    const PIP_Solution_Node* sol = current_solution->as_solution();
    PPL_ASSERT(sol != 0);
    s << "SOLUTION\n";
    sol->ascii_dump(s);
  }
}

bool Parma_Polyhedra_Library::PIP_Problem::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.

Definition at line 441 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::Constraint::ascii_load(), Parma_Polyhedra_Library::PIP_Solution_Node::ascii_load(), Parma_Polyhedra_Library::PIP_Decision_Node::ascii_load(), c, PPL_ASSERT, Parma_Polyhedra_Library::PIP_Solution_Node::set_owner(), Parma_Polyhedra_Library::PIP_Decision_Node::set_owner(), value, and Parma_Polyhedra_Library::Constraint::zero_dim_positivity().

                                        {
  std::string str;
  if (!(s >> str) || str != "external_space_dim:")
    return false;

  if (!(s >> external_space_dim))
    return false;

  if (!(s >> str) || str != "internal_space_dim:")
    return false;

  if (!(s >> internal_space_dim))
    return false;

  if (!(s >> str) || str != "input_cs(")
    return false;

  dimension_type input_cs_size;

  if (!(s >> input_cs_size))
    return false;

  if (!(s >> str) || str != ")")
    return false;

  Constraint c(Constraint::zero_dim_positivity());
  for (dimension_type i = 0; i < input_cs_size; ++i) {
    if (!c.ascii_load(s))
      return false;
    input_cs.push_back(c);
  }

  if (!(s >> str) || str != "first_pending_constraint:")
    return false;

  if (!(s >> first_pending_constraint))
    return false;

  if (!(s >> str) || str != "status:")
    return false;

  if (!(s >> str))
    return false;

  if (str == "UNSATISFIABLE")
    status = UNSATISFIABLE;
  else if (str == "OPTIMIZED")
    status = OPTIMIZED;
  else if (str == "PARTIALLY_SATISFIABLE")
    status = PARTIALLY_SATISFIABLE;
  else
    return false;

  if (!(s >> str) || str != "parameters")
    return false;

  if (!parameters.ascii_load(s))
    return false;

  if (!(s >> str) || str != "initial_context")
    return false;

  if (!initial_context.ascii_load(s))
    return false;

  if (!(s >> str) || str != "control_parameters")
    return false;

  for (dimension_type i = 0; i < CONTROL_PARAMETER_NAME_SIZE; ++i) {
    if (!(s >> str))
      return false;
    Control_Parameter_Value value;
    if (str == "CUTTING_STRATEGY_FIRST")
      value = CUTTING_STRATEGY_FIRST;
    else if (str == "CUTTING_STRATEGY_DEEPEST")
      value = CUTTING_STRATEGY_DEEPEST;
    else if (str == "CUTTING_STRATEGY_ALL")
      value = CUTTING_STRATEGY_ALL;
    else if (str == "PIVOT_ROW_STRATEGY_FIRST")
      value = PIVOT_ROW_STRATEGY_FIRST;
    else if (str == "PIVOT_ROW_STRATEGY_MAX_COLUMN")
      value = PIVOT_ROW_STRATEGY_MAX_COLUMN;
    else
      return false;
    control_parameters[i] = value;
  }

  if (!(s >> str) || str != "big_parameter_dimension:")
    return false;
  if (!(s >> big_parameter_dimension))
    return false;

  // Release current_solution tree (if any).
  delete current_solution;
  current_solution = 0;
  // Load current_solution (if any).
  if (!(s >> str) || str != "current_solution:")
    return false;
  if (!(s >> str))
    return false;
  if (str == "BOTTOM")
    current_solution = 0;
  else if (str == "DECISION") {
    PIP_Decision_Node* dec = new PIP_Decision_Node(0, 0, 0);
    current_solution = dec;
    if (!dec->ascii_load(s))
      return false;
    dec->set_owner(this);
  }
  else if (str == "SOLUTION") {
    PIP_Solution_Node* sol = new PIP_Solution_Node(0);
    current_solution = sol;
    if (!sol->ascii_load(s))
      return false;
    sol->set_owner(this);
  }
  else
    // Unknown node kind.
    return false;

  PPL_ASSERT(OK());
  return true;
}

void Parma_Polyhedra_Library::PIP_Problem::clear ( )

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

The space dimension is reset to $0$ .

Definition at line 566 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::not_a_dimension().

                      {
  external_space_dim = 0;
  internal_space_dim = 0;
  status = PARTIALLY_SATISFIABLE;
  if (current_solution != 0) {
    delete current_solution;
    current_solution = 0;
  }
  input_cs.clear();
  first_pending_constraint = 0;
  parameters.clear();
  initial_context.clear();
  control_parameters_init();
  big_parameter_dimension = not_a_dimension();
}

PIP_Problem::const_iterator Parma_Polyhedra_Library::PIP_Problem::constraints_begin ( ) const

inline

Returns a read-only iterator to the first constraint defining the feasible region.

Definition at line 40 of file PIP_Problem.inlines.hh.

References input_cs.

Referenced by operator<<().

                                     {
  return input_cs.begin();
}

PIP_Problem::const_iterator Parma_Polyhedra_Library::PIP_Problem::constraints_end ( ) const

inline

Returns a past-the-end read-only iterator to the sequence of constraints defining the feasible region.

Definition at line 45 of file PIP_Problem.inlines.hh.

References input_cs.

Referenced by operator<<().

                                   {
  return input_cs.end();
}

void Parma_Polyhedra_Library::PIP_Problem::control_parameters_copy ( const PIP_Problem & y )

private

Copies the control parameters from problem object y.

Definition at line 95 of file PIP_Problem.cc.

References control_parameters.

Referenced by PIP_Problem().

                                                            {
  for (dimension_type i = CONTROL_PARAMETER_NAME_SIZE; i-- > 0; )
    control_parameters[i] = y.control_parameters[i];
}

void Parma_Polyhedra_Library::PIP_Problem::control_parameters_init ( )

private

Initializes the control parameters with default values.

Definition at line 89 of file PIP_Problem.cc.

Referenced by PIP_Problem().

                                        {
  control_parameters[CUTTING_STRATEGY] = CUTTING_STRATEGY_FIRST;
  control_parameters[PIVOT_ROW_STRATEGY] = PIVOT_ROW_STRATEGY_FIRST;
}

PPL::memory_size_type Parma_Polyhedra_Library::PIP_Problem::external_memory_in_bytes ( ) const

Returns the size in bytes of the memory managed by *this.

Definition at line 708 of file PIP_Problem.cc.

                                               {
  memory_size_type n = initial_context.external_memory_in_bytes();
  // Adding the external memory for `current_solution'.
  if (current_solution != 0)
    n += current_solution->total_memory_in_bytes();
  // Adding the external memory for `input_cs'.
  n += input_cs.capacity() * sizeof(Constraint);
  for (const_iterator i = input_cs.begin(),
       i_end = input_cs.end(); i != i_end; ++i)
    n += (i->external_memory_in_bytes());
  // FIXME: Adding the external memory for `parameters'.
  n += parameters.size() * sizeof(dimension_type);

  return n;
}

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

Definition at line 84 of file PIP_Problem.inlines.hh.

References big_parameter_dimension.

Referenced by operator<<().

                                               {
  return big_parameter_dimension;
}

PIP_Problem::Control_Parameter_Value Parma_Polyhedra_Library::PIP_Problem::get_control_parameter ( Control_Parameter_Name name ) const

inline

Returns the value of control parameter name.

Definition at line 78 of file PIP_Problem.inlines.hh.

References CONTROL_PARAMETER_NAME_SIZE, control_parameters, and PPL_ASSERT.

                                                                    {
  PPL_ASSERT(name >= 0 && name < CONTROL_PARAMETER_NAME_SIZE);
  return control_parameters[name];
}

bool Parma_Polyhedra_Library::PIP_Problem::is_satisfiable ( ) const

Checks satisfiability of *this.

Returns:: true if and only if the PIP problem is satisfiable.

Definition at line 666 of file PIP_Problem.cc.

                                     {
  if (status == PARTIALLY_SATISFIABLE)
    solve();
  return status == OPTIMIZED;
}

void Parma_Polyhedra_Library::PIP_Problem::m_swap ( PIP_Problem & y )

inline

Swaps *this with y.

Definition at line 55 of file PIP_Problem.inlines.hh.

References big_parameter_dimension, CONTROL_PARAMETER_NAME_SIZE, control_parameters, current_solution, external_space_dim, first_pending_constraint, initial_context, input_cs, internal_space_dim, parameters, status, and swap().

Referenced by operator=(), and swap().

                                  {
  using std::swap;
  swap(external_space_dim, y.external_space_dim);
  swap(internal_space_dim, y.internal_space_dim);
  swap(status, y.status);
  swap(current_solution, y.current_solution);
  swap(input_cs, y.input_cs);
  swap(first_pending_constraint, y.first_pending_constraint);
  swap(parameters, y.parameters);
  swap(initial_context, y.initial_context);
  for (dimension_type i = CONTROL_PARAMETER_NAME_SIZE; i-- > 0; )
    swap(control_parameters[i], y.control_parameters[i]);
  swap(big_parameter_dimension, y.big_parameter_dimension);
}

dimension_type Parma_Polyhedra_Library::PIP_Problem::max_space_dimension ( )

inlinestatic

Returns the maximum space dimension a PIP_Problem can handle.

Definition at line 35 of file PIP_Problem.inlines.hh.

Referenced by PIP_Problem().

                                 {
  return Constraint::max_space_dimension();
}

bool Parma_Polyhedra_Library::PIP_Problem::OK ( ) const

Checks if all the invariants are satisfied.

Definition at line 265 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::ascii_dump(), and Parma_Polyhedra_Library::not_a_dimension().

Referenced by PIP_Problem().

                         {
#ifndef NDEBUG
  using std::endl;
  using std::cerr;
#endif

  if (external_space_dim < internal_space_dim) {
#ifndef NDEBUG
      cerr << "The internal space dimension of the PIP_Problem is "
           << "greater than its external space dimension."
           << endl;
      ascii_dump(cerr);
#endif
      return false;
    }

  // Constraint system should be OK.
  const dimension_type input_cs_num_rows = input_cs.size();
  for (dimension_type i = input_cs_num_rows; i-- > 0; )
    if (!input_cs[i].OK())
      return false;

  // Constraint system should be space dimension compatible.
  for (dimension_type i = input_cs_num_rows; i-- > 0; ) {
    if (input_cs[i].space_dimension() > external_space_dim) {
#ifndef NDEBUG
      cerr << "The space dimension of the PIP_Problem is smaller than "
           << "the space dimension of one of its constraints."
           << endl;
      ascii_dump(cerr);
#endif
      return false;
    }
  }

  // Test validity of control parameter values.
  Control_Parameter_Value strategy = control_parameters[CUTTING_STRATEGY];
  if (strategy != CUTTING_STRATEGY_FIRST
      && strategy != CUTTING_STRATEGY_DEEPEST
      && strategy != CUTTING_STRATEGY_ALL) {
#ifndef NDEBUG
    cerr << "Invalid value for the CUTTING_STRATEGY control parameter."
         << endl;
    ascii_dump(cerr);
#endif
    return false;
  }

  strategy = control_parameters[PIVOT_ROW_STRATEGY];
  if (strategy < PIVOT_ROW_STRATEGY_FIRST
      || strategy > PIVOT_ROW_STRATEGY_MAX_COLUMN) {
#ifndef NDEBUG
    cerr << "Invalid value for the PIVOT_ROW_STRATEGY control parameter."
        << endl;
    ascii_dump(cerr);
#endif
    return false;
  }

  if (big_parameter_dimension != not_a_dimension()
      && parameters.count(big_parameter_dimension) == 0) {
#ifndef NDEBUG
    cerr << "The big parameter is set, but it is not a parameter." << endl;
    ascii_dump(cerr);
#endif
    return false;
  }

  if (!parameters.OK())
    return false;
  if (!initial_context.OK())
    return false;

  if (current_solution != 0) {
    // Check well formedness of the solution tree.
    if (!current_solution->OK()) {
#ifndef NDEBUG
      cerr << "The computed solution tree is broken.\n";
      ascii_dump(cerr);
#endif
      return false;
    }
    // Check that all nodes in the solution tree belong to *this.
    if (!current_solution->check_ownership(this)) {
#ifndef NDEBUG
      cerr << "There are nodes in the solution tree "
           << "that are not owned by *this.\n";
      ascii_dump(cerr);
#endif
      return false;
    }
  }

  // All checks passed.
  return true;
}

PIP_Problem & Parma_Polyhedra_Library::PIP_Problem::operator= ( const PIP_Problem & y )

inline

Assignment operator.

Definition at line 71 of file PIP_Problem.inlines.hh.

References m_swap().

                                           {
  PIP_Problem tmp(y);
  m_swap(tmp);
  return *this;
}

PPL::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.

Definition at line 258 of file PIP_Problem.cc.

                                          {
  if (status == PARTIALLY_SATISFIABLE)
    solve();
  return current_solution;
}

const Variables_Set & Parma_Polyhedra_Library::PIP_Problem::parameter_space_dimensions ( ) const

inline

Returns a set containing all the variables' indexes representing the parameters of the PIP problem.

Definition at line 50 of file PIP_Problem.inlines.hh.

References parameters.

Referenced by operator<<(), Parma_Polyhedra_Library::PIP_Solution_Node::parametric_values(), Parma_Polyhedra_Library::PIP_Tree_Node::print(), and Parma_Polyhedra_Library::PIP_Solution_Node::update_solution().

                                              {
  return parameters;
}

void Parma_Polyhedra_Library::PIP_Problem::print ( ) const

Prints *this to std::cerr using operator<<.

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.

Definition at line 730 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::indent_and_print(), and PPL_ASSERT.

                                                              {
  switch (status) {

  case UNSATISFIABLE:
    PPL_ASSERT(current_solution == 0);
    PIP_Tree_Node::indent_and_print(s, indent, "_|_\n");
    break;

  case OPTIMIZED:
    PPL_ASSERT(current_solution != 0);
    current_solution->print(s, indent);
    break;

  case PARTIALLY_SATISFIABLE:
    throw std::logic_error("PIP_Problem::print_solution():\n"
                           "the PIP problem has not been solved.");
  }
}

void Parma_Polyhedra_Library::PIP_Problem::set_big_parameter_dimension ( dimension_type big_dim )

Sets the dimension for the big parameter to big_dim.

Definition at line 694 of file PIP_Problem.cc.

                                                                  {
  if (parameters.count(big_dim) == 0)
    throw std::invalid_argument("PPL::PIP_Problem::"
                                "set_big_parameter_dimension(big_dim):\n"
                                "dimension 'big_dim' is not a parameter.");
  if (big_dim < internal_space_dim)
    throw std::invalid_argument("PPL::PIP_Problem::"
                                "set_big_parameter_dimension(big_dim):\n"
                                "only newly-added parameters can be"
                                "converted into the big parameter.");
  big_parameter_dimension = big_dim;
}

void Parma_Polyhedra_Library::PIP_Problem::set_control_parameter ( Control_Parameter_Value value )

Sets control parameter value.

Definition at line 673 of file PIP_Problem.cc.

References value.

                                                                   {
  switch (value) {
  case CUTTING_STRATEGY_FIRST:
    // Intentionally fall through.
  case CUTTING_STRATEGY_DEEPEST:
    // Intentionally fall through.
  case CUTTING_STRATEGY_ALL:
    control_parameters[CUTTING_STRATEGY] = value;
    break;
  case PIVOT_ROW_STRATEGY_FIRST:
    // Intentionally fall through.
  case PIVOT_ROW_STRATEGY_MAX_COLUMN:
    control_parameters[PIVOT_ROW_STRATEGY] = value;
    break;
  default:
    throw std::invalid_argument("PPL::PIP_Problem::set_control_parameter(v)"
                                ":\ninvalid value.");
  }
}

PPL::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.

Definition at line 251 of file PIP_Problem.cc.

                               {
  if (status == PARTIALLY_SATISFIABLE)
    solve();
  return current_solution;
}

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

Definition at line 101 of file PIP_Problem.cc.

                            {
  switch (status) {

  case UNSATISFIABLE:
    PPL_ASSERT(OK());
    return UNFEASIBLE_PIP_PROBLEM;

  case OPTIMIZED:
    PPL_ASSERT(OK());
    return OPTIMIZED_PIP_PROBLEM;

  case PARTIALLY_SATISFIABLE:
    {
      PIP_Problem& x = const_cast<PIP_Problem&>(*this);
      // Allocate PIP solution tree root, if needed.
      if (current_solution == 0)
        x.current_solution = new PIP_Solution_Node(this);

      // Properly resize context matrix.
      const dimension_type new_num_cols = parameters.size() + 1;
      const dimension_type old_num_cols = initial_context.num_columns();
      if (old_num_cols < new_num_cols)
        x.initial_context.add_zero_columns(new_num_cols - old_num_cols);

      // Computed once for all (to be used inside loop).
      const Variables_Set::const_iterator param_begin = parameters.begin();
      const Variables_Set::const_iterator param_end = parameters.end();

      // This flag will be set if we insert a pending constraint
      // in the initial context.
      bool check_feasible_context = false;

      // Go through all pending constraints.
      for (Constraint_Sequence::const_iterator
             cs_i = nth_iter(input_cs, first_pending_constraint),
             cs_end = input_cs.end(); cs_i != cs_end; ++cs_i) {
        const Constraint& c = *cs_i;
        const dimension_type c_space_dim = c.space_dimension();
        PPL_ASSERT(external_space_dim >= c_space_dim);

        // Check if constraint has a non-zero variable coefficient.
        bool has_nonzero_variable_coefficient = false;
        for (dimension_type i = c_space_dim; i-- > 0; ) {
          if (c.coefficient(Variable(i)) != 0
              && parameters.count(i) == 0) {
            has_nonzero_variable_coefficient = true;
            break;
          }
        }
        // Constraints having a non-zero variable coefficient
        // should not be inserted in context.
        if (has_nonzero_variable_coefficient)
          continue;

        check_feasible_context = true;

        x.initial_context.add_zero_rows(1, Row_Flags());

        Row& row = x.initial_context[x.initial_context.num_rows()-1];

        {
          Row::iterator itr = row.end();

          if (c.inhomogeneous_term() != 0) {
            itr = row.insert(0, c.inhomogeneous_term());
            // Adjust inhomogeneous term if strict.
            if (c.is_strict_inequality())
              --(*itr);
          } else {
            // Adjust inhomogeneous term if strict.
            if (c.is_strict_inequality())
              itr = row.insert(0, -1);
          }
          dimension_type i = 1;

          // itr may still be end(), but it can still be used as hint.
          for (Variables_Set::const_iterator
               pi = param_begin; pi != param_end; ++pi, ++i) {
            if (*pi < c_space_dim) {
              Coefficient_traits::const_reference coeff_pi
                = c.coefficient(Variable(*pi));
              if (coeff_pi != 0)
                itr = row.insert(itr, i, coeff_pi);
            } else
              break;
          }
        }

        // If it is an equality, also insert its negation.
        if (c.is_equality()) {
          x.initial_context.add_zero_rows(1, Row_Flags());

          // The reference `row' has been invalidated.

          Row& last_row = x.initial_context[x.initial_context.num_rows()-1];

          last_row = x.initial_context[x.initial_context.num_rows()-2];

          for (Row::iterator
               i = last_row.begin(), i_end = last_row.end(); i != i_end; ++i)
            neg_assign(*i);
        }
      }

      if (check_feasible_context) {
        // Check for feasibility of initial context.
        Matrix ctx_copy(initial_context);
        if (!PIP_Solution_Node::compatibility_check(ctx_copy)) {
          // Problem found to be unfeasible.
          delete x.current_solution;
          x.current_solution = 0;
          x.status = UNSATISFIABLE;
          PPL_ASSERT(OK());
          return UNFEASIBLE_PIP_PROBLEM;
        }
      }

      // Update tableau and mark constraints as no longer pending.
      x.current_solution->update_tableau(*this,
                                         external_space_dim,
                                         first_pending_constraint,
                                         input_cs,
                                         parameters);
      x.internal_space_dim = external_space_dim;
      x.first_pending_constraint = input_cs.size();

      // Actually solve problem.
      x.current_solution = x.current_solution->solve(*this,
                                                     check_feasible_context,
                                                     initial_context,
                                                     parameters,
                                                     external_space_dim,
                                                     /*indent_level=*/ 0);
      // Update problem status.
      x.status = (x.current_solution != 0) ? OPTIMIZED : UNSATISFIABLE;

      PPL_ASSERT(OK());
      return (x.current_solution != 0)
        ? OPTIMIZED_PIP_PROBLEM
        : UNFEASIBLE_PIP_PROBLEM;
    } // End of handler for PARTIALLY_SATISFIABLE case.

  } // End of switch.

  // We should not be here!
  PPL_UNREACHABLE;
  return UNFEASIBLE_PIP_PROBLEM;
}

dimension_type Parma_Polyhedra_Library::PIP_Problem::space_dimension ( ) const

inline

Returns the space dimension of the PIP problem.

Definition at line 30 of file PIP_Problem.inlines.hh.

References external_space_dim.

Referenced by operator<<(), Parma_Polyhedra_Library::PIP_Solution_Node::parametric_values(), Parma_Polyhedra_Library::PIP_Tree_Node::print(), and Parma_Polyhedra_Library::PIP_Solution_Node::update_solution().

                                   {
  return external_space_dim;
}

PPL::memory_size_type Parma_Polyhedra_Library::PIP_Problem::total_memory_in_bytes ( ) const

Returns the total size in bytes of the memory occupied by *this.

Definition at line 725 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::external_memory_in_bytes().

                                            {
  return sizeof(*this) + external_memory_in_bytes();
}

Friends And Related Function Documentation

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

References constraints_begin(), constraints_end(), get_big_parameter_dimension(), Parma_Polyhedra_Library::not_a_dimension(), parameter_space_dimensions(), and space_dimension().

                                                                 {
  s << "Space dimension: " << pip.space_dimension();
  s << "\nConstraints:";
  for (PIP_Problem::const_iterator i = pip.constraints_begin(),
         i_end = pip.constraints_end(); i != i_end; ++i)
    s << "\n" << *i;
  s << "\nProblem parameters: " << pip.parameter_space_dimensions();
  if (pip.get_big_parameter_dimension() == not_a_dimension())
    s << "\nNo big-parameter set.\n";
  else
    s << "\nBig-parameter: " << Variable(pip.get_big_parameter_dimension());
  s << "\n";
  return s;
}

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

friend class PIP_Solution_Node

friend

Definition at line 823 of file PIP_Problem.defs.hh.

void swap	(	PIP_Problem &	x,
		PIP_Problem &	y
	)

Referenced by m_swap().

void swap	(	PIP_Problem &	x,
		PIP_Problem &	y
	)

References m_swap().

                                     {
  x.m_swap(y);
}

Member Data Documentation

dimension_type Parma_Polyhedra_Library::PIP_Problem::big_parameter_dimension

private

The dimension for the big parameter, or not_a_dimension() if not set.

Definition at line 821 of file PIP_Problem.defs.hh.

Referenced by get_big_parameter_dimension(), m_swap(), and Parma_Polyhedra_Library::PIP_Solution_Node::update_tableau().

Control_Parameter_Value Parma_Polyhedra_Library::PIP_Problem::control_parameters[CONTROL_PARAMETER_NAME_SIZE]

private

The control parameters for the problem object.

Definition at line 815 of file PIP_Problem.defs.hh.

Referenced by control_parameters_copy(), get_control_parameter(), m_swap(), and Parma_Polyhedra_Library::PIP_Solution_Node::solve().

PIP_Tree_Node* Parma_Polyhedra_Library::PIP_Problem::current_solution

private

The current solution decision tree.

Definition at line 792 of file PIP_Problem.defs.hh.

Referenced by m_swap(), PIP_Problem(), and solve().

dimension_type Parma_Polyhedra_Library::PIP_Problem::external_space_dim

private

The dimension of the vector space.

Definition at line 766 of file PIP_Problem.defs.hh.

Referenced by m_swap(), PIP_Problem(), space_dimension(), and Parma_Polyhedra_Library::PIP_Solution_Node::update_tableau().

dimension_type Parma_Polyhedra_Library::PIP_Problem::first_pending_constraint

private

The first index of `input_cs' containing a pending constraint.

Definition at line 798 of file PIP_Problem.defs.hh.

Referenced by m_swap(), and solve().

Matrix Parma_Polyhedra_Library::PIP_Problem::initial_context

private

The initial context.

Contains problem constraints on parameters only

Definition at line 811 of file PIP_Problem.defs.hh.

Referenced by m_swap(), and solve().

Constraint_Sequence Parma_Polyhedra_Library::PIP_Problem::input_cs

private

The sequence of constraints describing the feasible region.

Definition at line 795 of file PIP_Problem.defs.hh.

Referenced by constraints_begin(), constraints_end(), m_swap(), and PIP_Problem().

dimension_type Parma_Polyhedra_Library::PIP_Problem::internal_space_dim

private

The space dimension of the current (partial) solution of the PIP problem; it may be smaller than external_space_dim.

Definition at line 772 of file PIP_Problem.defs.hh.

Referenced by m_swap(), solve(), and Parma_Polyhedra_Library::PIP_Solution_Node::update_tableau().

Variables_Set Parma_Polyhedra_Library::PIP_Problem::parameters

private

A set containing all the indices of space dimensions that are interpreted as problem parameters.

Definition at line 804 of file PIP_Problem.defs.hh.

Referenced by m_swap(), and parameter_space_dimensions().

Status Parma_Polyhedra_Library::PIP_Problem::status

private

The internal state of the MIP problem.

Definition at line 789 of file PIP_Problem.defs.hh.

Referenced by m_swap(), and solve().

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

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation