Parma_Polyhedra_Library::PIP_Problem Class Reference

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

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. More...
	~PIP_Problem ()
	Destructor. More...
PIP_Problem &	operator= (const PIP_Problem &y)
	Assignment operator. More...
dimension_type	space_dimension () const
	Returns the space dimension of the PIP problem. More...
const Variables_Set &	parameter_space_dimensions () const
	Returns a set containing all the variables' indexes representing the parameters of the PIP problem. More...
const_iterator	constraints_begin () const
	Returns a read-only iterator to the first constraint defining the feasible region. More...
const_iterator	constraints_end () const
	Returns a past-the-end read-only iterator to the sequence of constraints defining the feasible region. More...
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. More...
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. More...
void	ascii_dump (std::ostream &s) const
	Writes to s an ASCII representation of *this. More...
void	print () const
	Prints *this to std::cerr using operator<<. More...
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. More...
memory_size_type	total_memory_in_bytes () const
	Returns the total size in bytes of the memory occupied by *this. More...
memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by *this. More...
void	m_swap (PIP_Problem &y)
	Swaps *this with y. More...
Control_Parameter_Value	get_control_parameter (Control_Parameter_Name name) const
	Returns the value of control parameter name. More...
void	set_control_parameter (Control_Parameter_Value value)
	Sets control parameter value. More...
void	set_big_parameter_dimension (dimension_type big_dim)
	Sets the dimension for the big parameter to big_dim. More...
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. More...

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. More...
typedef Sparse_Row	Row

Private Member Functions
void	control_parameters_init ()
	Initializes the control parameters with default values. More...
void	control_parameters_copy (const PIP_Problem &y)
	Copies the control parameters from problem object y. More...

Private Attributes
dimension_type	external_space_dim
	The dimension of the vector space. More...
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. More...
Status	status
	The internal state of the MIP problem. More...
PIP_Tree_Node *	current_solution
	The current solution decision tree. More...
Constraint_Sequence	input_cs
	The sequence of constraints describing the feasible region. More...
dimension_type	first_pending_constraint
	The first index of `input_cs' containing a pending constraint. More...
Variables_Set	parameters
	A set containing all the indices of space dimensions that are interpreted as problem parameters. More...
Matrix< Row >	initial_context
	The initial context. More...
Control_Parameter_Value	control_parameters [CONTROL_PARAMETER_NAME_SIZE]
	The control parameters for the problem object. More...
dimension_type	big_parameter_dimension
	The dimension for the big parameter, or not_a_dimension() if not set. More...

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

Definition at line 493 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 572 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 565 of file PIP_Problem_defs.hh.

typedef Sparse_Row Parma_Polyhedra_Library::PIP_Problem::Row

private

Definition at line 805 of file PIP_Problem_defs.hh.

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 50 of file PIP_Problem.cc.

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

  : 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 ; 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(), 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 70 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::clone(), control_parameters_copy(), current_solution, OK(), 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 88 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 697 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 713 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 632 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::max_space_dimension().

                                                                {
  // 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 670 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 372 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::PIP_Solution_Node::ascii_dump(), 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) {
    const 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* const dec
             = current_solution->as_decision()) {
    s << "DECISION\n";
    dec->ascii_dump(s);
  }
  else {
    const PIP_Solution_Node* const 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 453 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::ascii_load(), Parma_Polyhedra_Library::Constraint::ascii_load(), Parma_Polyhedra_Library::PIP_Decision_Node::ascii_load(), c, 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* const 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* const 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 .

Definition at line 614 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 99 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 93 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 766 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 85 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 79 of file PIP_Problem_inlines.hh.

References CONTROL_PARAMETER_NAME_SIZE, and control_parameters.

                                                                    {
  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 721 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, swap(), and Parma_Polyhedra_Library::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.

References Parma_Polyhedra_Library::Constraint::max_space_dimension().

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 277 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 space dimension compatible.
  const dimension_type input_cs_num_rows = input_cs.size();
  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 72 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 269 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 790 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::PIP_Tree_Node::indent_and_print().

                                                              {
  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 750 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 729 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 261 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 106 of file PIP_Problem.cc.

References Parma_Polyhedra_Library::Expression_Hide_Last< T >::all_zeroes_except(), Parma_Polyhedra_Library::Sparse_Row::begin(), c, Parma_Polyhedra_Library::Constraint::coefficient(), Parma_Polyhedra_Library::PIP_Tree_Node::compatibility_check(), current_solution, Parma_Polyhedra_Library::Sparse_Row::end(), Parma_Polyhedra_Library::Constraint::expression(), first_pending_constraint, Parma_Polyhedra_Library::Constraint::inhomogeneous_term(), initial_context, Parma_Polyhedra_Library::Sparse_Row::insert(), internal_space_dim, Parma_Polyhedra_Library::Constraint::is_equality(), Parma_Polyhedra_Library::Constraint::is_strict_inequality(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::nth_iter(), Parma_Polyhedra_Library::OPTIMIZED_PIP_PROBLEM, Parma_Polyhedra_Library::PIP_Tree_Node::solve(), Parma_Polyhedra_Library::Constraint::space_dimension(), status, Parma_Polyhedra_Library::UNFEASIBLE_PIP_PROBLEM, and Parma_Polyhedra_Library::PIP_Tree_Node::update_tableau().

                            {
  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);

        // Constraints having a non-zero variable coefficient
        // should not be inserted in context.
        if (!c.expression().all_zeroes_except(parameters, 1, c_space_dim + 1)) {
          continue;
        }

        check_feasible_context = true;

        x.initial_context.add_zero_rows(1);

        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;

          // TODO: This loop may be optimized more, if needed.
          // If the size of param_end is expected to be greater than the
          // number of nonzeroes of c in most cases, then this implementation
          // can't be optimized further.
          // 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);

          // 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<Row> 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 785 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  )

related

Definition at line 32 of file PIP_Problem.cc.

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  )

related

Output operator.

friend class PIP_Solution_Node

friend

Definition at line 827 of file PIP_Problem_defs.hh.

void swap ( PIP_Problem &  x, PIP_Problem &  y  )

related

Swaps x with y.

Referenced by m_swap().

void swap ( PIP_Problem &  x, PIP_Problem &  y  )

related

Definition at line 91 of file PIP_Problem_inlines.hh.

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 825 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 819 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 790 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 764 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 796 of file PIP_Problem_defs.hh.

Referenced by m_swap(), and solve().

Matrix<Row> Parma_Polyhedra_Library::PIP_Problem::initial_context

private

The initial context.

Contains problem constraints on parameters only

Definition at line 815 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 793 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 770 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 802 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 787 of file PIP_Problem_defs.hh.

Referenced by m_swap(), and solve().

---

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

• PIP_Problem_defs.hh
• PIP_Problem.cc
• PIP_Problem_inlines.hh
• PIP_Problem_templates.hh