Parma_Polyhedra_Library::LP_Problem Class Reference
[C++ Language Interface]

A Linear Programming problem. More...

#include <LP_Problem.defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::LP_Problem:

Collaboration graph
[legend]

List of all members.

Public Member Functions

 LP_Problem ()
 Default constructor: builds a trivial LP problem.
 LP_Problem (const Constraint_System &cs, const Linear_Expression &obj=Linear_Expression::zero(), Optimization_Mode mode=MAXIMIZATION)
 Builds an LP problem from the constraint system cs, the objective function obj and optimization mode mode.
 LP_Problem (const LP_Problem &y)
 Ordinary copy-constructor.
 ~LP_Problem ()
 Destructor.
LP_Problemoperator= (const LP_Problem &y)
 Assignment operator.
dimension_type space_dimension () const
 Returns the space dimension of the current LP problem.
const Constraint_Systemconstraints () const
 Returns the constraints defining the current feasible region.
const Linear_Expressionobjective_function () const
 Returns the current objective function.
Optimization_Mode optimization_mode () const
 Returns the current optimization mode.
void clear ()
 Resets *this to be equal to the trivial LP problem.
void add_constraint (const Constraint &c)
 Adds a copy of constraint c to the current LP problem, increasing the number of space dimensions if needed.
void add_constraints (const Constraint_System &cs)
 Adds a copy of the constraints in cs to the current LP problem, increasing the number of space dimensions if needed.
void set_objective_function (const Linear_Expression &obj)
 Sets the objective function to obj.
void set_optimization_mode (Optimization_Mode mode)
 Sets the optimization mode to mode.
bool is_satisfiable () const
 Checks satisfiability of *this.
LP_Problem_Status solve () const
 Optimizes the current LP problem using the primal simplex algorithm.
void evaluate_objective_function (const Generator &evaluating_point, Coefficient &num, Coefficient &den) const
 Sets num and den so that $\frac{num}{den}$ is the result of evaluating the objective function on evaluating_point.
const Generatorfeasible_point () const
 Returns a feasible point for *this, if it exists.
const Generatoroptimizing_point () const
 Returns an optimal point for *this, if it exists.
void optimal_value (Coefficient &num, Coefficient &den) const
 Sets num and den so that $\frac{num}{den}$ is the solution of the optimization problem.
bool OK () const
 Checks if all the invariants are satisfied.
void ascii_dump () const
 Writes to std::cerr an ASCII representation of *this.
void ascii_dump (std::ostream &s) const
 Writes to s an ASCII representation of *this.
void print () const
 Prints *this to std::cerr using operator<<.
bool ascii_load (std::istream &s)
 Loads from s an ASCII representation (as produced by ascii_dump) 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 swap (LP_Problem &y)
 Swaps *this with y.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a LP_Problem can handle.

Private Types

enum  Status {
  UNSOLVED, UNSATISFIABLE, SATISFIABLE, UNBOUNDED,
  OPTIMIZED, PARTIALLY_SATISFIABLE
}
 An enumerated type describing the internal status of the LP problem. More...

Private Member Functions

void second_phase ()
 Optimizes the current LP problem using the second phase of the primal simplex algorithm.
LP_Problem_Status compute_tableau ()
 Assigns to this->tableau a simplex tableau representing the current LP problem, inserting into this->dim_map the information that is required to recover the original LP problem.
dimension_type get_entering_var_index () const
 Checks for optimality and, if it does not hold, computes the column index of the variable entering the base of the LP problem. Implemented with anti-cycling rule.
dimension_type get_exiting_base_index (dimension_type entering_var_index) const
 Computes the row index of the variable exiting the base of the LP problem. Implemented with anti-cycling rules.
void swap_base (const dimension_type entering_var_index, const dimension_type exiting_base_index)
 Swaps two variables in base during the simplex algorithm, performing the needed linear combinations.
dimension_type steepest_edge () const
 Checks for optimality and, if it does not hold, computes the column index of the variable entering the base of the LP problem.
bool compute_simplex ()
 Returns true if and if only the algorithm successfully computed a feasible solution.
void prepare_first_phase ()
 Adds the slack variables to satisfy the standard form of a LP problem, inserts the "sign" to the cost functions, and makes the necessary swaps to express the problem with the 1st phase base.
void erase_slacks ()
 Drop unnecessary slack variables from the tableau and get ready for the second phase of the simplex algorithm.
bool is_in_base (const dimension_type var_index, dimension_type &row_index) const
Generator compute_generator () const

Static Private Member Functions

static void linear_combine (Row &x, const Row &y, const dimension_type k)
 Linearly combines x with y so that *this[k] is 0.

Private Attributes

Matrix tableau
 The matrix encoding the current feasible region in tableau form.
Row working_cost
 The working cost function.
std::vector< dimension_typebase
 The current basic solution.
std::map< dimension_type,
dimension_type
dim_map
 A mapping between original variables and split ones.
Status status
 The internal state of the LP problem.
Constraint_System input_cs
 The constraint system describing the feasible region.
Linear_Expression input_obj_function
 The objective function to be optimized.
Optimization_Mode opt_mode
 The optimization mode requested.
Generator last_generator
 The last successfully computed feasible or optimizing point.

Related Functions

(Note that these are not member functions.)

void swap (Parma_Polyhedra_Library::LP_Problem &x, Parma_Polyhedra_Library::LP_Problem &y)


Detailed Description

A Linear Programming problem.

Definition at line 40 of file LP_Problem.defs.hh.


Member Enumeration Documentation

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

Enumerator:
UNSOLVED  The LP problem has not been solved yet.
UNSATISFIABLE  The LP problem is unsatisfiable.
SATISFIABLE  The LP problem is satisfiable; a feasible solution has been computed.
UNBOUNDED  The LP problem is unbounded; a feasible solution has been computed.
OPTIMIZED  The LP problem is optimized; an optimal solution has been computed.
PARTIALLY_SATISFIABLE  The feasible region of the LP problem has been changed by adding new constraints; a feasible solution for the old constraints has been computed.

Definition at line 231 of file LP_Problem.defs.hh.

00231               {
00233     UNSOLVED,
00235     UNSATISFIABLE,
00237     SATISFIABLE,
00239     UNBOUNDED,
00241     OPTIMIZED,
00247     PARTIALLY_SATISFIABLE
00248   };


Constructor & Destructor Documentation

Parma_Polyhedra_Library::LP_Problem::LP_Problem (  )  [inline]

Default constructor: builds a trivial LP problem.

The trivial LP problem requires to maximize the objective function $0$ on the zero-dimensional vector space under no constraints at all: the origin of the vector space is the optimal solution.

Definition at line 33 of file LP_Problem.inlines.hh.

References OK().

00034   : tableau(), working_cost(0, Row::Flags()),
00035     base(),  dim_map(), status(OPTIMIZED),
00036     input_cs(), input_obj_function(), opt_mode(MAXIMIZATION),
00037     last_generator(point()) {
00038   assert(OK());
00039 }

Parma_Polyhedra_Library::LP_Problem::LP_Problem ( const Constraint_System cs,
const Linear_Expression obj = Linear_Expression::zero(),
Optimization_Mode  mode = MAXIMIZATION 
) [inline, explicit]

Builds an LP problem from the constraint system cs, the objective function obj and optimization mode mode.

Parameters:
cs The constraint system defining the feasible region for the LP problem.
obj The objective function for the LP problem (optional argument with default value $0$).
mode The optimization mode (optional argument with default value MAXIMIZATION).
Exceptions:
std::invalid_argument Thrown if the constraint system contains any strict inequality or if the space dimension of the objective function is strictly greater than the space dimension of the constraint system.

Definition at line 42 of file LP_Problem.inlines.hh.

References OK().

00045   : tableau(), working_cost(0, Row::Flags()),
00046     base(), dim_map(), status(UNSOLVED),
00047     input_cs(!cs.has_strict_inequalities()
00048              ? cs
00049              : (throw std::invalid_argument("PPL::LP_Problem::"
00050                            "LP_Problem(cs, obj, m):\n"
00051                            "cs contains strict inequalities."),
00052                 cs)),
00053     input_obj_function(obj.space_dimension() <= cs.space_dimension()
00054                        ? obj
00055                        : (throw std::invalid_argument("PPL::LP_Problem::"
00056                                      "LP_Problem(cs, obj, m):\n"
00057                                      "cs and obj have "
00058                                      "incompatible space dimensions."),
00059                           obj)),
00060     opt_mode(mode),
00061     last_generator(point()) {
00062   assert(OK());
00063 }

Parma_Polyhedra_Library::LP_Problem::LP_Problem ( const LP_Problem y  )  [inline]

Ordinary copy-constructor.

Definition at line 66 of file LP_Problem.inlines.hh.

References OK().

00067   : tableau(y.tableau), working_cost(y.working_cost),
00068     base(y.base), dim_map(y.dim_map), status(y.status),
00069     input_cs(y.input_cs), input_obj_function(y.input_obj_function),
00070     opt_mode(y.opt_mode), last_generator(y.last_generator) {
00071   assert(OK());
00072 }

Parma_Polyhedra_Library::LP_Problem::~LP_Problem (  )  [inline]

Destructor.

Definition at line 75 of file LP_Problem.inlines.hh.

00075                         {
00076 }


Member Function Documentation

LP_Problem & Parma_Polyhedra_Library::LP_Problem::operator= ( const LP_Problem y  )  [inline]

Assignment operator.

Definition at line 92 of file LP_Problem.inlines.hh.

References swap().

00092                                          {
00093   LP_Problem tmp(y);
00094   swap(tmp);
00095   return *this;
00096 }

dimension_type Parma_Polyhedra_Library::LP_Problem::max_space_dimension (  )  [inline, static]

Returns the maximum space dimension a LP_Problem can handle.

Definition at line 99 of file LP_Problem.inlines.hh.

References Parma_Polyhedra_Library::Constraint_System::max_space_dimension().

00099                                 {
00100   return Constraint_System::max_space_dimension();
00101 }

dimension_type Parma_Polyhedra_Library::LP_Problem::space_dimension (  )  const [inline]

Returns the space dimension of the current LP problem.

Definition at line 104 of file LP_Problem.inlines.hh.

References input_cs, and Parma_Polyhedra_Library::Constraint_System::space_dimension().

Referenced by evaluate_objective_function(), ppl_LP_Problem_space_dimension(), and set_objective_function().

00104                                   {
00105   return input_cs.space_dimension();
00106 }

const Constraint_System & Parma_Polyhedra_Library::LP_Problem::constraints (  )  const [inline]

Returns the constraints defining the current feasible region.

Definition at line 109 of file LP_Problem.inlines.hh.

References input_cs.

Referenced by ppl_LP_Problem_constraints().

00109                               {
00110   return input_cs;
00111 }

const Linear_Expression & Parma_Polyhedra_Library::LP_Problem::objective_function (  )  const [inline]

Returns the current objective function.

Definition at line 114 of file LP_Problem.inlines.hh.

References input_obj_function.

Referenced by ppl_LP_Problem_objective_function().

00114                                      {
00115   return input_obj_function;
00116 }

Optimization_Mode Parma_Polyhedra_Library::LP_Problem::optimization_mode (  )  const [inline]

Returns the current optimization mode.

Definition at line 119 of file LP_Problem.inlines.hh.

References opt_mode.

Referenced by ppl_LP_Problem_optimization_mode().

00119                                     {
00120   return opt_mode;
00121 }

void Parma_Polyhedra_Library::LP_Problem::clear (  )  [inline]

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

Definition at line 124 of file LP_Problem.inlines.hh.

References swap().

Referenced by ppl_LP_Problem_clear().

00124                   {
00125   LP_Problem tmp;
00126   swap(tmp);
00127 }

void Parma_Polyhedra_Library::LP_Problem::add_constraint ( const Constraint c  )  [inline]

Adds a copy of constraint c to the current LP problem, increasing the number of space dimensions if needed.

Exceptions:
std::invalid_argument Thrown if the constraint c is a strict inequality.

Definition at line 130 of file LP_Problem.inlines.hh.

References input_cs, Parma_Polyhedra_Library::Constraint_System::insert(), Parma_Polyhedra_Library::Constraint::is_strict_inequality(), status, UNSATISFIABLE, and UNSOLVED.

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), and ppl_LP_Problem_add_constraint().

00130                                               {
00131   if (c.is_strict_inequality())
00132     throw std::invalid_argument("PPL::LP_Problem::add_constraint(c):\n"
00133                                 "c is a strict inequality.");
00134   input_cs.insert(c);
00135   if (status != UNSATISFIABLE)
00136     // TODO: apply an incremental version of the simplex algorithm,
00137     // setting `status' to PARTIALLY_SATISFIABLE;
00138     status = UNSOLVED;
00139 }

void Parma_Polyhedra_Library::LP_Problem::add_constraints ( const Constraint_System cs  )  [inline]

Adds a copy of the constraints in cs to the current LP problem, increasing the number of space dimensions if needed.

Exceptions:
std::invalid_argument Thrown if the constraint system cs contains any strict inequality.

Definition at line 142 of file LP_Problem.inlines.hh.

References Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities(), input_cs, Parma_Polyhedra_Library::Constraint_System::insert(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), status, UNSATISFIABLE, and UNSOLVED.

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), ppl_LP_Problem_add_constraints(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints().

00142                                                        {
00143   if (cs.has_strict_inequalities())
00144     throw std::invalid_argument("PPL::LP_Problem::add_constraints(cs):\n"
00145                                 "cs contains strict inequalities.");
00146   const dimension_type cs_num_rows = cs.num_rows();
00147   for (dimension_type i = cs_num_rows; i-- > 0; )
00148     input_cs.insert(cs[i]);
00149   if (status != UNSATISFIABLE)
00150     // TODO: apply an incremental version of the simplex algorithm,
00151     // setting `status' to PARTIALLY_SATISFIABLE;
00152     status = UNSOLVED;
00153   assert(OK());
00154 }

void Parma_Polyhedra_Library::LP_Problem::set_objective_function ( const Linear_Expression obj  )  [inline]

Sets the objective function to obj.

Exceptions:
std::invalid_argument Thrown if the space dimension of obj is strictly greater than the space dimension of *this.

Definition at line 157 of file LP_Problem.inlines.hh.

References input_obj_function, OK(), OPTIMIZED, SATISFIABLE, Parma_Polyhedra_Library::Linear_Expression::space_dimension(), space_dimension(), status, and UNBOUNDED.

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), ppl_LP_Problem_set_objective_function(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints().

00157                                                                {
00158   if (space_dimension() < obj.space_dimension())
00159     throw std::invalid_argument("PPL::LP_Problem::"
00160                                 "set_objective_function(obj):\n"
00161                                 "*this and obj are dimension incompatible.");
00162   switch (status) {
00163   case UNBOUNDED:
00164     status = SATISFIABLE;
00165     break;
00166   case OPTIMIZED:
00167     status = SATISFIABLE;
00168     break;
00169   default:
00170     break;
00171   }
00172   input_obj_function = obj;
00173   assert(OK());
00174 }

void Parma_Polyhedra_Library::LP_Problem::set_optimization_mode ( Optimization_Mode  mode  )  [inline]

Sets the optimization mode to mode.

Definition at line 177 of file LP_Problem.inlines.hh.

References OK(), opt_mode, OPTIMIZED, SATISFIABLE, status, and UNBOUNDED.

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), ppl_LP_Problem_set_optimization_mode(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints().

00177                                                         {
00178   if (opt_mode == mode)
00179     return;
00180   switch (status) {
00181   case UNBOUNDED:
00182     status = SATISFIABLE;
00183     break;
00184   case OPTIMIZED:
00185     status = SATISFIABLE;
00186     break;
00187   default:
00188     break;
00189   }
00190   opt_mode = mode;
00191   assert(OK());
00192 }

bool Parma_Polyhedra_Library::LP_Problem::is_satisfiable (  )  const

Checks satisfiability of *this.

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

Definition at line 790 of file LP_Problem.cc.

References base, Parma_Polyhedra_Library::Matrix::clear(), compute_generator(), compute_simplex(), compute_tableau(), dim_map, erase_slacks(), input_cs, last_generator, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OPTIMIZED, Parma_Polyhedra_Library::OPTIMIZED_LP_PROBLEM, PARTIALLY_SATISFIABLE, prepare_first_phase(), SATISFIABLE, status, tableau, UNBOUNDED, Parma_Polyhedra_Library::UNBOUNDED_LP_PROBLEM, Parma_Polyhedra_Library::UNFEASIBLE_LP_PROBLEM, UNSATISFIABLE, UNSOLVED, and working_cost.

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), feasible_point(), ppl_LP_Problem_is_satisfiable(), Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box(), and solve().

00790                                     {
00791 #if PPL_NOISY_SIMPLEX
00792   num_iterations = 0;
00793 #endif
00794   // Check for the `status' attribute in trivial cases.
00795   switch (status) {
00796   case UNSATISFIABLE:
00797     return false;
00798   case SATISFIABLE:
00799     return true;
00800   case UNBOUNDED:
00801     return true;
00802   case OPTIMIZED:
00803     return true;
00804   case PARTIALLY_SATISFIABLE:
00805     return false;
00806   case UNSOLVED:
00807     break;
00808   }
00809 
00810   LP_Problem& x = const_cast<LP_Problem&>(*this);
00811 
00812   // The space dimension of the solution to be computed.
00813   // Note: here we can not use method Constraint_System::space_dimension(),
00814   // because if the constraint system is NNC, then even the epsilon
00815   // dimension has to be interpreted as a normal dimension.
00816   const dimension_type space_dim = x.input_cs.num_columns() - 1;
00817 
00818   // Reset internal objects.
00819   x.tableau.clear();
00820   x.dim_map.clear();
00821   // Compute the initial tableau.
00822   LP_Problem_Status s_status = x.compute_tableau();
00823 
00824   // Check for trivial cases.
00825   switch (s_status) {
00826   case UNFEASIBLE_LP_PROBLEM:
00827     return false;
00828   case UNBOUNDED_LP_PROBLEM:
00829     // A feasible point has to be returned: the origin.
00830     // Ensure the right space dimension is obtained.
00831     x.last_generator = point(0*Variable(space_dim-1));
00832     return true;
00833   case OPTIMIZED_LP_PROBLEM:
00834     // Check for the special case of an empty tableau,
00835     // in which case an optimizing solution is the origin.
00836     if (x.tableau.num_rows() == 0) {
00837       // Ensure the right space dimension is obtained.
00838       x.last_generator = point(0*Variable(space_dim-1));
00839       return true;
00840     }
00841     break;
00842   }
00843 
00844 #if PPL_NOISY_SIMPLEX
00845   num_iterations = 0;
00846 #endif
00847 
00848   // Actually solve the LP problem.
00849   x.base = std::vector<dimension_type> (x.tableau.num_rows());
00850 
00851   // This will contain the new cost function for the 1st phase problem.
00852   // Adds the necessary slack variables to get the 1st phase problem.
00853   x.prepare_first_phase();
00854   // Solve the first phase of the primal simplex algorithm.
00855   bool first_phase_successful = x.compute_simplex();
00856 
00857 #if PPL_NOISY_SIMPLEX
00858   std::cout << "LP_Problem::solve: 1st phase ended at iteration "
00859             << num_iterations << "." << std::endl;
00860 #endif
00861   // If the first phase problem was not solved or if we found an optimum
00862   // value different from zero, then the origianl problem is unfeasible.
00863   if (!first_phase_successful || x.working_cost[0] != 0){
00864     x.status = UNSATISFIABLE;
00865     return false;
00866   }
00867 
00868   // The first phase has found a feasible solution. If only a satisfiability
00869   // check was requested, we can return that feasible solution.
00870   // Store the last succesfully computed generator.
00871   x.last_generator = compute_generator();
00872   x.status = SATISFIABLE;
00873   // Erase the slack variables.
00874   x.erase_slacks();
00875   return true;
00876 }

LP_Problem_Status Parma_Polyhedra_Library::LP_Problem::solve (  )  const [inline]

Optimizes the current LP problem using the primal simplex algorithm.

Returns:
An LP_Problem_Status flag indicating the outcome of the optimization attempt (unfeasible, unbounded or optimized problem).

Definition at line 195 of file LP_Problem.inlines.hh.

References is_satisfiable(), OPTIMIZED, Parma_Polyhedra_Library::OPTIMIZED_LP_PROBLEM, second_phase(), status, UNBOUNDED, Parma_Polyhedra_Library::UNBOUNDED_LP_PROBLEM, and Parma_Polyhedra_Library::UNFEASIBLE_LP_PROBLEM.

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), optimizing_point(), ppl_LP_Problem_solve(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints().

00195                         {
00196   if (is_satisfiable()) {
00197     LP_Problem& x = const_cast<LP_Problem&>(*this);
00198     x.second_phase();
00199     if (x.status == UNBOUNDED)
00200       return UNBOUNDED_LP_PROBLEM;
00201     if (x.status == OPTIMIZED)
00202       return OPTIMIZED_LP_PROBLEM;
00203   }
00204   return UNFEASIBLE_LP_PROBLEM;
00205 }

void Parma_Polyhedra_Library::LP_Problem::evaluate_objective_function ( const Generator evaluating_point,
Coefficient num,
Coefficient den 
) const

Sets num and den so that $\frac{num}{den}$ is the result of evaluating the objective function on evaluating_point.

Parameters:
evaluating_point The point on which the objective function will be evaluated.
num On exit will contain the numerator of the evaluated value.
den On exit will contain the denominator of the evaluated value.
Exceptions:
std::invalid_argument Thrown if *this and evaluating_point are dimension-incompatible or if the generator evaluating_point is not a point.

Definition at line 763 of file LP_Problem.cc.

References Parma_Polyhedra_Library::Linear_Expression::coefficient(), Parma_Polyhedra_Library::Generator::coefficient(), Parma_Polyhedra_Library::Generator::divisor(), Parma_Polyhedra_Library::Linear_Expression::inhomogeneous_term(), input_obj_function, Parma_Polyhedra_Library::Generator::is_point(), Parma_Polyhedra_Library::normalize2(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), space_dimension(), and Parma_Polyhedra_Library::Generator::space_dimension().

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), optimal_value(), and ppl_LP_Problem_evaluate_objective_function().

00765                                                                        {
00766   const dimension_type ep_space_dim = evaluating_point.space_dimension();
00767   if (space_dimension() < ep_space_dim)
00768     throw std::invalid_argument("PPL::LP_Problem::"
00769                                 "evaluate_objective_function(p, n, d):\n"
00770                                 "*this and p are dimension incompatible.");
00771   if (!evaluating_point.is_point())
00772     throw std::invalid_argument("PPL::LP_Problem::"
00773                                 "evaluate_objective_function(p, n, d):\n"
00774                                 "p is not a point.");
00775 
00776   // Compute the smallest space dimension  between `input_obj_function'
00777   // and `evaluating_point'.
00778   const dimension_type space_dim
00779     = std::min(ep_space_dim, input_obj_function.space_dimension());
00780   // Compute the optimal value of the cost function.
00781   ext_n = input_obj_function.inhomogeneous_term();
00782   for (dimension_type i = space_dim; i-- > 0; )
00783     ext_n += evaluating_point.coefficient(Variable(i))
00784       * input_obj_function.coefficient(Variable(i));
00785   // Numerator and denominator should be coprime.
00786   normalize2(ext_n, evaluating_point.divisor(), ext_n, ext_d);
00787 }

const Generator & Parma_Polyhedra_Library::LP_Problem::feasible_point (  )  const [inline]

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

Exceptions:
std::domain_error Thrown if the LP problem is not satisfiable.

Definition at line 208 of file LP_Problem.inlines.hh.

References is_satisfiable(), last_generator, and OK().

Referenced by ppl_LP_Problem_feasible_point().

00208                                  {
00209   if (is_satisfiable()) {
00210     assert(OK());
00211     return last_generator;
00212   }
00213   throw std::domain_error("PPL::LP_Problem::feasible_point():\n"
00214                           "*this is not satisfiable.");
00215 }

const Generator & Parma_Polyhedra_Library::LP_Problem::optimizing_point (  )  const [inline]

Returns an optimal point for *this, if it exists.

Exceptions:
std::domain_error Thrown if *this doesn't not have an optimizing point, i.e., if the LP problem is unbounded or not satisfiable.

Definition at line 218 of file LP_Problem.inlines.hh.

References last_generator, Parma_Polyhedra_Library::OPTIMIZED_LP_PROBLEM, and solve().

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), optimal_value(), and ppl_LP_Problem_optimizing_point().

00218                                    {
00219   if (solve() == OPTIMIZED_LP_PROBLEM)
00220     return last_generator;
00221   throw std::domain_error("PPL::LP_Problem::optimizing_point():\n"
00222                           "*this doesn't have an optimizing point.");
00223 }

void Parma_Polyhedra_Library::LP_Problem::optimal_value ( Coefficient num,
Coefficient den 
) const [inline]

Sets num and den so that $\frac{num}{den}$ is the solution of the optimization problem.

Exceptions:
std::domain_error Thrown if *this doesn't not have an optimizing point, i.e., if the LP problem is unbounded or not satisfiable.

Definition at line 226 of file LP_Problem.inlines.hh.

References evaluate_objective_function(), OK(), and optimizing_point().

Referenced by ppl_LP_Problem_optimal_value().

00226                                                                   {
00227   const Generator& g_ref = optimizing_point();
00228   evaluate_objective_function(g_ref, num, den);
00229   assert(OK());
00230 }

bool Parma_Polyhedra_Library::LP_Problem::OK (  )  const

Checks if all the invariants are satisfied.

Definition at line 879 of file LP_Problem.cc.

References base, dim_map, Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities(), input_cs, input_obj_function, last_generator, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OPTIMIZED, SATISFIABLE, Parma_Polyhedra_Library::Constraint_System::satisfies_all_constraints(), Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Generator::space_dimension(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), Parma_Polyhedra_Library::Constraint_System::space_dimension(), status, tableau, UNBOUNDED, and working_cost.

Referenced by add_constraints(), feasible_point(), LP_Problem(), optimal_value(), ppl_LP_Problem_OK(), second_phase(), set_objective_function(), and set_optimization_mode().

00879                         {
00880 #ifndef NDEBUG
00881   using std::endl;
00882   using std::cerr;
00883 #endif
00884 
00885   // Constraint system should contain no strict inequalities.
00886   if (input_cs.has_strict_inequalities()) {
00887 #ifndef NDEBUG
00888     cerr << "The feasible region of the LP_Problem is defined by "
00889          << "a constraint system containing strict inequalities."
00890          << endl;
00891 #endif
00892     return false;
00893   }
00894 
00895   // Constraint system and objective function should be dimension compatible.
00896   const dimension_type space_dim = input_cs.space_dimension();
00897   if (space_dim < input_obj_function.space_dimension()) {
00898 #ifndef NDEBUG
00899     cerr << "The LP_Problem and the objective function have "
00900          << "incompatible space dimensions ("
00901          << space_dim << " < " << input_obj_function.space_dimension() << ")."
00902          << endl;
00903 #endif
00904     return false;
00905   }
00906 
00907   if (status == SATISFIABLE || status == UNBOUNDED || status == OPTIMIZED) {
00908     // Here `last_generator' has to be meaningful.
00909     // Check for dimension compatibility and actual feasibility.
00910     if (space_dim != last_generator.space_dimension()) {
00911 #ifndef NDEBUG
00912       cerr << "The LP_Problem and the cached feasible point have "
00913            << "incompatible space dimensions ("
00914            << space_dim << " != " << last_generator.space_dimension() << ")."
00915            << endl;
00916 #endif
00917       return false;
00918     }
00919     if (!input_cs.satisfies_all_constraints(last_generator)) {
00920 #ifndef NDEBUG
00921       cerr << "The cached feasible point does not belong to "
00922            << "the feasible region of the LP_Problem."
00923            << endl;
00924 #endif
00925       return false;
00926     }
00927 
00928     const dimension_type tableau_nrows = tableau.num_rows();
00929     const dimension_type tableau_ncols = tableau.num_columns();
00930 
00931     // The number of rows in the tableau and base should be equal.
00932     if (tableau_nrows != base.size()) {
00933 #ifndef NDEBUG
00934       cerr << "tableau and base have incompatible sizes" << endl;
00935 #endif
00936       return false;
00937     }
00938 
00939     // The number of columns in the tableau and working_cost should be equal.
00940     if (tableau_ncols != working_cost.size()) {
00941 #ifndef NDEBUG
00942       cerr << "tableau and working_cost have incompatible sizes" << endl;
00943 #endif
00944       return false;
00945     }
00946 
00947     // The vector base should contain indices of tableau's columns.
00948     for (dimension_type i = base.size(); i-- > 0; )
00949       if (base[i] > tableau_ncols) {
00950 #ifndef NDEBUG
00951         cerr << "base contains an invalid column index" << endl;
00952 #endif
00953         return false;
00954       }
00955 
00956     // dim_map should encode an injective function having
00957     // disjoint domain and range.
00958     std::set<dimension_type> domain;
00959     std::set<dimension_type> range;
00960     typedef std::map<dimension_type, dimension_type>::const_iterator Iter;
00961     for (Iter i = dim_map.begin(), iend = dim_map.end(); i != iend; ++i) {
00962       domain.insert(i->first);
00963       range.insert(i->second);
00964     }
00965     if (domain.size() != range.size()
00966         || domain.end() != std::find_first_of(domain.begin(), domain.end(),
00967                                               range.begin(), range.end())) {
00968 #ifndef NDEBUG
00969       cerr << "dim_map encodes an invalid map" << endl;
00970 #endif
00971       return false;
00972     }
00973   }
00974   // TODO: further tests will be added when supporting incremental
00975   // computations.
00976 
00977   // All checks passed.
00978   return true;
00979 }

void Parma_Polyhedra_Library::LP_Problem::ascii_dump (  )  const

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

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

Writes to s an ASCII representation of *this.

Definition at line 982 of file LP_Problem.cc.

References Parma_Polyhedra_Library::Generator::ascii_dump(), Parma_Polyhedra_Library::Row::ascii_dump(), Parma_Polyhedra_Library::Matrix::ascii_dump(), Parma_Polyhedra_Library::Linear_Row::ascii_dump(), Parma_Polyhedra_Library::Constraint_System::ascii_dump(), base, dim_map, input_cs, input_obj_function, last_generator, Parma_Polyhedra_Library::MAXIMIZATION, opt_mode, OPTIMIZED, PARTIALLY_SATISFIABLE, SATISFIABLE, status, tableau, UNBOUNDED, UNSATISFIABLE, UNSOLVED, and working_cost.

00982                                              {
00983   using namespace IO_Operators;
00984 
00985   s << "input_cs\n";
00986   input_cs.ascii_dump(s);
00987   s << "\ninput_obj_function\n";
00988   input_obj_function.ascii_dump(s);
00989   s << "\nopt_mode " << (opt_mode == MAXIMIZATION ? "MAX" : "MIN") << "\n";
00990 
00991   s << "\nstatus: ";
00992   switch (status) {
00993   case UNSATISFIABLE:
00994     s << "UNSAT";
00995     break;
00996   case SATISFIABLE:
00997     s << "SATIS";
00998     break;
00999   case UNBOUNDED:
01000     s << "UNBOU";
01001     break;
01002   case OPTIMIZED:
01003     s << "OPTIM";
01004     break;
01005   case PARTIALLY_SATISFIABLE:
01006     s << "P_SAT";
01007     break;
01008   case UNSOLVED:
01009     s << "UNSOL";
01010     break;
01011   }
01012   s << "\n";
01013 
01014   s << "\ntableau\n";
01015   tableau.ascii_dump(s);
01016   s << "\nworking_cost\n";
01017   working_cost.ascii_dump(s);
01018 
01019   const dimension_type base_size = base.size();
01020   s << "\nbase (" << base_size << ")\n";
01021   for (dimension_type i = 0; i != base_size; ++i)
01022     s << base[i] << ' ';
01023 
01024   const dimension_type dim_map_size = dim_map.size();
01025   s << "\ndim_map (" << dim_map_size << ")\n";
01026   for (std::map<dimension_type, dimension_type>::const_iterator
01027          i = dim_map.begin(), iend = dim_map.end(); i != iend; ++i)
01028     s << Variable(i->first) << "->" << Variable(i->second) << ' ';
01029 
01030   s << "\nlast_generator\n";
01031   last_generator.ascii_dump(s);
01032   s << "\n";
01033 }

void Parma_Polyhedra_Library::LP_Problem::print (  )  const

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

bool Parma_Polyhedra_Library::LP_Problem::ascii_load ( std::istream &  s  ) 

Loads from s an ASCII representation (as produced by ascii_dump) and sets *this accordingly. Returns true if successful, false otherwise.

memory_size_type Parma_Polyhedra_Library::LP_Problem::total_memory_in_bytes (  )  const [inline]

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

Definition at line 250 of file LP_Problem.inlines.hh.

References external_memory_in_bytes().

00250                                         {
00251   return sizeof(*this) + external_memory_in_bytes();
00252 }

memory_size_type Parma_Polyhedra_Library::LP_Problem::external_memory_in_bytes (  )  const [inline]

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

Definition at line 233 of file LP_Problem.inlines.hh.

References base, dim_map, Parma_Polyhedra_Library::Generator::external_memory_in_bytes(), Parma_Polyhedra_Library::Linear_Expression::external_memory_in_bytes(), Parma_Polyhedra_Library::Constraint_System::external_memory_in_bytes(), Parma_Polyhedra_Library::Row::external_memory_in_bytes(), Parma_Polyhedra_Library::Matrix::external_memory_in_bytes(), input_cs, input_obj_function, last_generator, tableau, and working_cost.

Referenced by total_memory_in_bytes().

00233                                            {
00234   memory_size_type n
00235     = tableau.external_memory_in_bytes()
00236     + working_cost.external_memory_in_bytes()
00237     + input_cs.external_memory_in_bytes()
00238     + input_obj_function.external_memory_in_bytes()
00239     + last_generator.external_memory_in_bytes();
00240   // Adding the external memory for `base'.
00241   n += base.capacity() * sizeof(dimension_type);
00242   // Adding the external memory for `dim_map'.
00243   // CHECK ME: just a lower approximation?
00244   n += dim_map.size()
00245     * sizeof(std::map<dimension_type, dimension_type>::value_type);
00246   return n;
00247 }

void Parma_Polyhedra_Library::LP_Problem::swap ( LP_Problem y  )  [inline]

Swaps *this with y.

Definition at line 79 of file LP_Problem.inlines.hh.

References base, dim_map, input_cs, input_obj_function, last_generator, opt_mode, status, tableau, and working_cost.

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

00079                               {
00080   std::swap(tableau, y.tableau);
00081   std::swap(working_cost, y.working_cost);
00082   std::swap(base, y.base);
00083   std::swap(dim_map, y.dim_map);
00084   std::swap(status, y.status);
00085   std::swap(input_cs, y.input_cs);
00086   std::swap(input_obj_function, y.input_obj_function);
00087   std::swap(opt_mode, y.opt_mode);
00088   std::swap(last_generator, y.last_generator);
00089 }

void Parma_Polyhedra_Library::LP_Problem::second_phase (  )  [private]

Optimizes the current LP problem using the second phase of the primal simplex algorithm.

Definition at line 711 of file LP_Problem.cc.

References base, compute_generator(), compute_simplex(), dim_map, input_obj_function, last_generator, linear_combine(), Parma_Polyhedra_Library::MINIMIZATION, Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), opt_mode, OPTIMIZED, SATISFIABLE, Parma_Polyhedra_Library::Row::size(), status, Parma_Polyhedra_Library::Row::swap(), tableau, UNBOUNDED, and working_cost.

Referenced by solve().

00711                             {
00712   // Second_phase requires that *this is satisfiable.
00713   assert(status == SATISFIABLE || status == UNBOUNDED || status == OPTIMIZED);
00714   // In the following cases the problem is already solved.
00715   if (status == UNBOUNDED || status == OPTIMIZED)
00716     return;
00717 
00718   // Negate the cost function if we are minimizing.
00719   Row new_cost = input_obj_function;
00720   if (opt_mode == MINIMIZATION)
00721     for (dimension_type i = new_cost.size(); i-- > 0; )
00722       neg_assign(new_cost[i]);
00723 
00724   // Substitute properly the cost funcion in the `costs' Matrix.
00725   const dimension_type cost_zero_size = working_cost.size();
00726   Row tmp_cost = Row(new_cost, cost_zero_size, cost_zero_size);
00727   tmp_cost.swap(working_cost);
00728   working_cost[cost_zero_size-1] = 1;
00729   // Split the variable in the original cost function as defined in the
00730   // `dim_map' variable.
00731   typedef std::map<dimension_type, dimension_type>::const_iterator iter;
00732   for (iter map_itr = dim_map.begin(),
00733          map_end = dim_map.end(); map_itr != map_end; ++map_itr){
00734     const dimension_type original_var = (map_itr->first) + 1;
00735     const dimension_type split_var = (map_itr->second) + 1;
00736     working_cost[split_var] = -working_cost[original_var];
00737   }
00738 
00739   // Here the first phase problem succeeded with optimum value zero.
00740   // Express the old cost function in terms of the computed base.
00741   for (dimension_type i = tableau.num_rows(); i-- > 0; ) {
00742     const dimension_type base_i = base[i];
00743     if (working_cost[base_i] != 0)
00744       linear_combine(working_cost, tableau[i], base_i);
00745   }
00746   // Solve the second phase problem.
00747   bool second_phase_successful = compute_simplex();
00748 
00749 #if PPL_NOISY_SIMPLEX
00750   std::cout << "LP_Problem::solve: 2nd phase ended at iteration "
00751             << num_iterations << "." << std::endl;
00752 #endif
00753   if (second_phase_successful) {
00754     last_generator = compute_generator();
00755     status = OPTIMIZED;
00756   }
00757   else
00758     status = UNBOUNDED;
00759   assert(OK());
00760 }

PPL::LP_Problem_Status Parma_Polyhedra_Library::LP_Problem::compute_tableau (  )  [private]

Assigns to this->tableau a simplex tableau representing the current LP problem, inserting into this->dim_map the information that is required to recover the original LP problem.

Returns:
UNFEASIBLE_LP_PROBLEM if the constraint system contains any trivially unfeasible constraint (tableau was not computed); UNBOUNDED_LP_PROBLEM if the problem is trivially unbounded (the computed tableau contains no constraints); OPTIMIZED_LP_PROBLEM> if the problem is neither trivially unfeasible nor trivially unbounded (the tableau was computed successfully).

Definition at line 400 of file LP_Problem.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), dim_map, input_cs, input_obj_function, Parma_Polyhedra_Library::Linear_Row::is_line_or_equality(), Parma_Polyhedra_Library::Linear_Row::is_ray_or_point_or_inequality(), Parma_Polyhedra_Library::Matrix::max_num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OPTIMIZED, Parma_Polyhedra_Library::OPTIMIZED_LP_PROBLEM, status, tableau, UNBOUNDED, Parma_Polyhedra_Library::UNBOUNDED_LP_PROBLEM, and Parma_Polyhedra_Library::UNFEASIBLE_LP_PROBLEM.

Referenced by is_satisfiable().

00400                                {
00401   assert(tableau.num_rows() == 0);
00402   assert(dim_map.size() == 0);
00403   // Note: exploiting friendship so as to efficiently access the
00404   // coefficients of each constraint.
00405   Linear_System& cs = input_cs;
00406   const dimension_type cs_num_rows = cs.num_rows();
00407   const dimension_type cs_num_cols = cs.num_columns();
00408 
00409   // Step 1:
00410   // determine variables that are constrained to be nonnegative,
00411   // detect (non-negativity or tautology) constraints that will not
00412   // be part of the tableau and count the number of slack variables.
00413 
00414   // Counters determining the dimensions of the tableau:
00415   // initialized here, they will be updated while examining `cs'.
00416   dimension_type tableau_num_rows = cs_num_rows;
00417   dimension_type tableau_num_cols = 2*cs_num_cols - 1;
00418   dimension_type num_slack_variables = 0;
00419 
00420   // On exit, `is_tableau_constraint[i]' will be true if and only if
00421   // `cs[i]' is neither a tautology (e.g., 1 >= 0) nor a non-negativity
00422   // constraint (e.g., X >= 0).
00423   std::deque<bool> is_tableau_constraint(cs_num_rows, true);
00424 
00425   // On exit, `nonnegative_variable[j]' will be true if and only if
00426   // Variable(j) is bound to be nonnegative in `cs'.
00427   std::deque<bool> nonnegative_variable(cs_num_cols - 1, false);
00428 
00429   // Process each row of the `cs' matrix.
00430   for (dimension_type i = cs_num_rows; i-- > 0; ) {
00431     const Linear_Row& cs_i = cs[i];
00432     bool found_a_nonzero_coeff = false;
00433     bool found_many_nonzero_coeffs = false;
00434     dimension_type nonzero_coeff_column_index = 0;
00435     for (dimension_type j = cs_num_cols; j-- > 1; ) {
00436       if (cs_i[j] != 0)
00437         if (found_a_nonzero_coeff) {
00438           found_many_nonzero_coeffs = true;
00439           if (cs_i.is_ray_or_point_or_inequality())
00440             ++num_slack_variables;
00441           break;
00442         }
00443         else {
00444           nonzero_coeff_column_index = j;
00445           found_a_nonzero_coeff = true;
00446         }
00447     }
00448     // If more than one coefficient is nonzero,
00449     // continue with next constraint.
00450     if (found_many_nonzero_coeffs)
00451       continue;
00452 
00453     if (!found_a_nonzero_coeff) {
00454       // All coefficients are 0.
00455       // The constraint is either trivially true or trivially false.
00456       if (cs_i.is_ray_or_point_or_inequality()) {
00457         if (cs_i[0] < 0)
00458           // A constraint such as -1 >= 0 is trivially false.
00459           return UNFEASIBLE_LP_PROBLEM;
00460       }
00461       else
00462         // The constraint is an equality.
00463         if (cs_i[0] != 0)
00464           // A constraint such as 1 == 0 is trivially false.
00465           return UNFEASIBLE_LP_PROBLEM;
00466       // Here the constraint is trivially true.
00467       is_tableau_constraint[i] = false;
00468       --tableau_num_rows;
00469       continue;
00470     }
00471     else {
00472       // Here we have only one nonzero coefficient.
00473       /*
00474 
00475       We have the following methods:
00476       A) Do split the variable and do add the constraint in the tableau.
00477       B) Don't split the variable and do add the constraint in the tableau.
00478       C) Don't split the variable and don't add the constraint in the tableau.
00479 
00480       Let the constraint be (a*v + b relsym 0).
00481       These are the 12 possible combinations we can have:
00482                 a |  b | relsym | method
00483       ----------------------------------
00484       1)       >0 | >0 |   >=   |   A
00485       2)       >0 | >0 |   ==   |   A
00486       3)       <0 | <0 |   >=   |   A
00487       4)       >0 | =0 |   ==   |   B
00488       5)       >0 | <0 |   ==   |   B
00489       Note:    <0 | >0 |   ==   | impossible by strong normalization
00490       Note:    <0 | =0 |   ==   | impossible by strong normalization
00491       Note:    <0 | <0 |   ==   | impossible by strong normalization
00492       6)       >0 | <0 |   >=   |   B
00493       7)       >0 | =0 |   >=   |   C
00494       8)       <0 | >0 |   >=   |   A
00495       9)       <0 | =0 |   >=   |   A
00496 
00497       The next lines will apply the correct method to each case.
00498       */
00499 
00500       // The variable index is not equal to the column index.
00501       const dimension_type nonzero_var_index = nonzero_coeff_column_index - 1;
00502 
00503       const int sgn_a = sgn(cs_i[nonzero_coeff_column_index]);
00504       const int sgn_b = sgn(cs_i[0]);
00505       // Cases 1-3: apply method A.
00506       if (sgn_a == sgn_b) {
00507         if (cs_i.is_ray_or_point_or_inequality())
00508           ++num_slack_variables;
00509       }
00510       // Cases 4-5: apply method B.
00511       else if (cs_i.is_line_or_equality()) {
00512         if (!nonnegative_variable[nonzero_var_index]) {
00513           nonnegative_variable[nonzero_var_index] = true;
00514           --tableau_num_cols;
00515         }
00516       }
00517       // Case 6: apply method B.
00518       else if (sgn_b < 0) {
00519         if (!nonnegative_variable[nonzero_var_index]) {
00520           nonnegative_variable[nonzero_var_index] = true;
00521           --tableau_num_cols;
00522         }
00523         ++num_slack_variables;
00524       }
00525       // Case 7: apply method C.
00526       else if (sgn_a > 0) {
00527         if (!nonnegative_variable[nonzero_var_index]) {
00528           nonnegative_variable[nonzero_var_index] = true;
00529           --tableau_num_cols;
00530         }
00531         is_tableau_constraint[i] = false;
00532         --tableau_num_rows;
00533       }
00534       // Cases 8-9: apply method A.
00535       else
00536         ++num_slack_variables;
00537     }
00538   }
00539 
00540   // The slack variables will be columns in the tableau.
00541   tableau_num_cols += num_slack_variables;
00542 
00543   // Now we can fill the map.
00544   for (dimension_type i = 0, j = nonnegative_variable.size(),
00545          nnv_size = j; i < nnv_size; ++i)
00546     if (!nonnegative_variable[i]) {
00547       dim_map.insert(std::make_pair(i, j));
00548       ++j;
00549     }
00550 
00551   // Step 2:
00552   // set the dimensions for the tableau and the cost function.
00553   if (tableau_num_rows > 0) {
00554     if (tableau_num_cols > tableau.max_num_columns())
00555       throw std::length_error("PPL::LP_Problem:\nthe maximum size of an "
00556                               "internal data structure has been exceeded "
00557                               "while solving the LP_Problem.");
00558     tableau.add_zero_rows_and_columns(tableau_num_rows,
00559                                       tableau_num_cols,
00560                                       Row::Flags());
00561   }
00562 
00563   // Phase 3:
00564   // insert all the (possibly transformed) constraints that are not
00565   // nonnegativity constraints. The transformation includes both
00566   // the variable splitting (for variables that are unconstrained
00567   // in sign) and the addition of slack variables (for inequalities
00568   // in the original problem).
00569 
00570   for (dimension_type k = tableau_num_rows, slack_index = tableau_num_cols,
00571          i = cs_num_rows; i-- > 0; )
00572     if (is_tableau_constraint[i]) {
00573       // Copy the original constraint in the tableau.
00574       Row& tableau_k = tableau[--k];
00575       const Linear_Row& cs_i = cs[i];
00576       for (dimension_type j = cs_num_cols; j-- > 0; )
00577         tableau_k[j] = cs_i[j];
00578       // Add the slack variable, if needed.
00579       if (cs_i.is_ray_or_point_or_inequality())
00580         tableau_k[--slack_index] = -1;
00581     }
00582 
00583   // Split the variables in the tableau and cost function.
00584   typedef std::map<dimension_type, dimension_type>::const_iterator iter;
00585   for (iter map_itr = dim_map.begin(),
00586          map_end = dim_map.end(); map_itr != map_end; ++map_itr) {
00587     const dimension_type original_var = (map_itr->first) + 1;
00588     const dimension_type split_var = (map_itr->second) + 1;
00589     for (dimension_type i = tableau_num_rows; i-- > 0; ) {
00590       Row& tableau_i = tableau[i];
00591       tableau_i[split_var] = -tableau_i[original_var];
00592     }
00593   }
00594 
00595   // If there is no constraint in the tableau, then the feasible region
00596   // is only delimited by non-negativity constraints. Therefore,
00597   // the problem is unbounded as soon as the cost function has
00598   // a variable with a positive coefficient.
00599   if (tableau_num_rows == 0)
00600     for (dimension_type i = tableau_num_cols; i-- > 1; )
00601       if (input_obj_function[i] > 0){
00602         status = UNBOUNDED;
00603         return UNBOUNDED_LP_PROBLEM;
00604       }
00605   // The problem is neither trivially unfeasible nor trivially unbounded.
00606   // The tableau was successfull computed and the caller has to figure
00607   // out which case applies.
00608   status = OPTIMIZED;
00609   return OPTIMIZED_LP_PROBLEM;
00610 }

PPL::dimension_type Parma_Polyhedra_Library::LP_Problem::get_entering_var_index (  )  const [private]

Checks for optimality and, if it does not hold, computes the column index of the variable entering the base of the LP problem. Implemented with anti-cycling rule.

Returns:
The column index of the variable that enters the base. If no such variable exists, optimality was achieved and 0 is retuned.

Definition at line 138 of file LP_Problem.cc.

References Parma_Polyhedra_Library::Row::size(), and working_cost.

Referenced by compute_simplex().

00138                                             {
00139   // The variable entering the base is the first one whose coefficient
00140   // in the cost function has the same sign the cost function itself.
00141   // If no such variable exists, then we met the optimality condition
00142   // (and return 0 to the caller).
00143 
00144   // Get the "sign" of the cost function.
00145   const dimension_type cost_sign_index = working_cost.size() - 1;
00146   const int cost_sign = sgn(working_cost[cost_sign_index]);
00147   assert(cost_sign != 0);
00148   for (dimension_type i = 1; i < cost_sign_index; ++i)
00149     if (sgn(working_cost[i]) == cost_sign)
00150       return i;
00151   // No variable has to enter the base:
00152   // the cost function was optimized.
00153   return 0;
00154 }

PPL::dimension_type Parma_Polyhedra_Library::LP_Problem::get_exiting_base_index ( dimension_type  entering_var_index  )  const [private]

Computes the row index of the variable exiting the base of the LP problem. Implemented with anti-cycling rules.

Returns:
The row index of the variable exiting the base.
Parameters:
entering_var_index The column index of the variable entering the base.

Definition at line 204 of file LP_Problem.cc.

References base, Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::lcm_assign(), Parma_Polyhedra_Library::Matrix::num_rows(), tableau, and TEMP_INTEGER.

Referenced by compute_simplex().

00204                                                                        {
00205   // The variable exiting the base should be associated to a tableau
00206   // constraint such that the ratio
00207   // tableau[i][entering_var_index] / tableau[i][base[i]]
00208   // is strictly positive and minimal.
00209 
00210   // Find the first tableau constraint `c' having a positive value for
00211   //   tableau[i][entering_var_index] / tableau[i][base[i]]
00212   const dimension_type tableau_num_rows = tableau.num_rows();
00213   dimension_type exiting_base_index = tableau_num_rows;
00214   for (dimension_type i = 0; i < tableau_num_rows; ++i) {
00215     const Row& t_i = tableau[i];
00216     const int num_sign = sgn(t_i[entering_var_index]);
00217     if (num_sign != 0 && num_sign == sgn(t_i[base[i]])) {
00218       exiting_base_index = i;
00219       break;
00220     }
00221   }
00222   // Check for unboundedness.
00223   if (exiting_base_index == tableau_num_rows)
00224     return tableau_num_rows;
00225 
00226   // Reaching this point means that a variable will definitely exit the base.
00227   TEMP_INTEGER(lcm);
00228   TEMP_INTEGER(current_min);
00229   TEMP_INTEGER(challenger);
00230   for (dimension_type i = exiting_base_index + 1; i < tableau_num_rows; ++i) {
00231     const Row& t_i = tableau[i];
00232     const Coefficient& t_ie = t_i[entering_var_index];
00233     const Coefficient& t_ib = t_i[base[i]];
00234     const int t_ie_sign = sgn(t_ie);
00235     if (t_ie_sign != 0 && t_ie_sign == sgn(t_ib)) {
00236       const Row& t_e = tableau[exiting_base_index];
00237       const Coefficient& t_ee = t_e[entering_var_index];
00238       lcm_assign(lcm, t_ee, t_ie);
00239       exact_div_assign(current_min, lcm, t_ee);
00240       current_min *= t_e[0];
00241       current_min = abs(current_min);
00242       exact_div_assign(challenger, lcm, t_ie);
00243       challenger *= t_i[0];
00244       challenger = abs(challenger);
00245       current_min -= challenger;
00246       const int sign = sgn(current_min);
00247       if (sign > 0
00248           || (sign == 0 && base[i] < base[exiting_base_index]))
00249         exiting_base_index = i;
00250     }
00251   }
00252   return exiting_base_index;
00253 }

void Parma_Polyhedra_Library::LP_Problem::linear_combine ( Row x,
const Row y,
const dimension_type  k 
) [static, private]

Linearly combines x with y so that *this[k] is 0.

Parameters:
x The Row that will be combined with y object.
y The Row that will be combined with x object.
k The position of *this that have to be $0$.
Computes a linear combination of x and y having the element of index k equal to $0$. Then it assigns the resulting Linear_Row to x and normalizes it.

Definition at line 157 of file LP_Problem.cc.

References Parma_Polyhedra_Library::Row::normalize(), Parma_Polyhedra_Library::normalize2(), Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::sub_mul_assign(), and TEMP_INTEGER.

Referenced by prepare_first_phase(), second_phase(), and swap_base().

00159                                                         {
00160   assert(x.size() == y.size());
00161   assert(y[k] != 0 && x[k] != 0);
00162   // Let g be the GCD between `x[k]' and `y[k]'.
00163   // For each i the following computes
00164   //   x[i] = x[i]*y[k]/g - y[i]*x[k]/g.
00165   TEMP_INTEGER(normalized_x_k);
00166   TEMP_INTEGER(normalized_y_k);
00167   normalize2(x[k], y[k], normalized_x_k, normalized_y_k);
00168   for (dimension_type i = x.size(); i-- > 0; )
00169     if (i != k) {
00170       Coefficient& x_i = x[i];
00171       x_i *= normalized_y_k;
00172       // Note: the test speeds up the GMP computation.
00173       const Coefficient& y_i = y[i];
00174       if (y_i != 0)
00175         sub_mul_assign(x_i, y_i, normalized_x_k);
00176     }
00177   x[k] = 0;
00178   x.normalize();
00179 }

void Parma_Polyhedra_Library::LP_Problem::swap_base ( const dimension_type  entering_var_index,
const dimension_type  exiting_base_index 
) [private]

Swaps two variables in base during the simplex algorithm, performing the needed linear combinations.

Parameters:
entering_var_index The index of the variable entering the base.
exiting_base_index The index of the row exiting the base.

Definition at line 184 of file LP_Problem.cc.

References base, linear_combine(), Parma_Polyhedra_Library::Matrix::num_rows(), tableau, and working_cost.

Referenced by compute_simplex(), and erase_slacks().

00185                                                                     {
00186   const Row& tableau_out = tableau[exiting_base_index];
00187   // Linearly combine the constraints.
00188   for (dimension_type i = tableau.num_rows(); i-- > 0; ) {
00189     Row& tableau_i = tableau[i];
00190     if (i != exiting_base_index && tableau_i[entering_var_index] != 0)
00191       linear_combine(tableau_i, tableau_out, entering_var_index);
00192   }
00193   // Linearly combine the cost function.
00194   if (working_cost[entering_var_index] != 0)
00195     linear_combine(working_cost, tableau_out, entering_var_index);
00196   // Adjust the base.
00197   base[exiting_base_index] = entering_var_index;
00198 }

PPL::dimension_type Parma_Polyhedra_Library::LP_Problem::steepest_edge (  )  const [private]

Checks for optimality and, if it does not hold, computes the column index of the variable entering the base of the LP problem.

Returns:
The column index of the variable that enters the base. If no such variable exists, optimality was achieved and 0 is retuned.
To compute the entering_index, the steepest edge algorithm chooses the index `j' such that $\frac{d_{j}}{\|\Delta x^{j} \|}$ is the largest in absolute value, where

\[ \|\Delta x^{j} \| = \left( 1+\sum_{i=1}^{m} \alpha_{ij}^2 \right)^{\frac{1}{2}}. \]

Recall that, due to the Integer implementation of the algorithm, our tableau doesn't contain the ``real'' $\alpha$ values, but these can be computed dividing the value of the cofficient by the value of the variable in base. Obviously the result may not be an Integer, so we will proceed in another way: the following code will compute the lcm of all the variables in base to get the good ``weight'' of each Coefficient of the tableau.

Definition at line 65 of file LP_Problem.cc.

References Parma_Polyhedra_Library::add_mul_assign(), base, Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::lcm_assign(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Row::size(), tableau, TEMP_INTEGER, and working_cost.

Referenced by compute_simplex().

00065                                    {
00066   const dimension_type tableau_num_rows = tableau.num_rows();
00067   assert(tableau_num_rows == base.size());
00068   // The square of the lcm of all the coefficients of variables in base.
00069   TEMP_INTEGER(squared_lcm_basis);
00070   // The normalization factor for each coefficient in the tableau.
00071   std::vector<Coefficient> norm_factor(tableau_num_rows);
00072   {
00073     // Compute the lcm of all the coefficients of variables in base.
00074     TEMP_INTEGER(lcm_basis);
00075     lcm_basis = 1;
00076     for (dimension_type i = tableau_num_rows; i-- > 0; )
00077       lcm_assign(lcm_basis, lcm_basis, tableau[i][base[i]]);
00078     // Compute normalization factors.
00079     for (dimension_type i = tableau_num_rows; i-- > 0; )
00080       exact_div_assign(norm_factor[i], lcm_basis, tableau[i][base[i]]);
00081     // Compute the square of `lcm_basis', exploiting the fact that
00082     // `lcm_basis' will no longer be needed.
00083     lcm_basis *= lcm_basis;
00084     std::swap(squared_lcm_basis, lcm_basis);
00085   }
00086 
00087   // Defined here to avoid repeated (de-)allocations.
00088   TEMP_INTEGER(challenger_num);
00089   TEMP_INTEGER(scalar_value);
00090   TEMP_INTEGER(challenger_den);
00091   TEMP_INTEGER(challenger_value);
00092   TEMP_INTEGER(current_value);
00093 
00094   TEMP_INTEGER(current_num);
00095   TEMP_INTEGER(current_den);
00096   dimension_type entering_index = 0;
00097   const int cost_sign = sgn(working_cost[working_cost.size() - 1]);
00098   for (dimension_type j = tableau.num_columns() - 1; j-- > 1; ) {
00099     const Coefficient& cost_j = working_cost[j];
00100     if (sgn(cost_j) == cost_sign) {
00101       // We can't compute the (exact) square root of abs(\Delta x_j).
00102       // The workaround is to compute the square of `cost[j]'.
00103       challenger_num = cost_j * cost_j;
00104       // Due to our integer implementation, the `1' term in the denominator
00105       // of the original formula has to be replaced by `squared_lcm_basis'.
00106       challenger_den = squared_lcm_basis;
00107       for (dimension_type i = tableau_num_rows; i-- > 0; ) {
00108         const Coefficient& tableau_ij = tableau[i][j];
00109         // Note: this test speeds up the GMP computation.
00110         if (tableau_ij != 0) {
00111           scalar_value = tableau_ij * norm_factor[i];
00112           add_mul_assign(challenger_den, scalar_value, scalar_value);
00113         }
00114       }
00115       // Initialization during the first loop.
00116       if (entering_index == 0) {
00117         std::swap(current_num, challenger_num);
00118         std::swap(current_den, challenger_den);
00119         entering_index = j;
00120         continue;
00121       }
00122       challenger_value = challenger_num * current_den;
00123       current_value = current_num * challenger_den;
00124       // Update the values, if the challeger wins.
00125       if (challenger_value > current_value) {
00126         std::swap(current_num, challenger_num);
00127         std::swap(current_den, challenger_den);
00128         entering_index = j;
00129       }
00130     }
00131   }
00132   return entering_index;
00133 }

bool Parma_Polyhedra_Library::LP_Problem::compute_simplex (  )  [private]

Returns true if and if only the algorithm successfully computed a feasible solution.

Definition at line 258 of file LP_Problem.cc.

References get_entering_var_index(), get_exiting_base_index(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Row::size(), steepest_edge(), swap_base(), tableau, and working_cost.

Referenced by is_satisfiable(), and second_phase().

00258                                {
00259   assert(tableau.num_columns() == working_cost.size());
00260   const dimension_type tableau_num_rows = tableau.num_rows();
00261   while (true) {
00262     // Choose the index of the variable entering the base, if any.
00263     const dimension_type entering_var_index
00264 #if PPL_SIMPLEX_ENABLE_STEEPEST_EDGE
00265       = steepest_edge();
00266 #else
00267       = get_entering_var_index();
00268 #endif
00269     // If no entering index was computed, the problem is solved.
00270     if (entering_var_index == 0)
00271       return true;
00272 
00273     // Choose the index of the row exiting the base.
00274     const dimension_type exiting_base_index
00275       = get_exiting_base_index(entering_var_index);
00276     // If no exiting index was computed, the problem is unbounded.
00277     if (exiting_base_index == tableau_num_rows)
00278       return false;
00279 
00280     // We have not reached the optimality or unbounded condition:
00281     // compute the new base and the corresponding vertex of the
00282     // feasible region.
00283     swap_base(entering_var_index, exiting_base_index);
00284 #if PPL_NOISY_SIMPLEX
00285     ++num_iterations;
00286     if (num_iterations % 200 == 0)
00287       std::cout << "Primal Simplex: iteration "
00288                 << num_iterations << "." << std::endl;
00289 #endif
00290   }
00291 }

void Parma_Polyhedra_Library::LP_Problem::prepare_first_phase (  )  [private]

Adds the slack variables to satisfy the standard form of a LP problem, inserts the "sign" to the cost functions, and makes the necessary swaps to express the problem with the 1st phase base.

Definition at line 296 of file LP_Problem.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_columns(), base, linear_combine(), Parma_Polyhedra_Library::Matrix::max_num_columns(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Row::size(), tableau, and working_cost.

Referenced by is_satisfiable().

00296                                    {
00297   // We negate the row if tableau[i][0] <= 0 to get the inhomogeneous term > 0.
00298   // This simplifies the insertion of the slack variables: the value of the
00299   // slack variable of every constraint will be 1.
00300   const dimension_type tableau_old_n_cols = tableau.num_columns();
00301   for (dimension_type i = tableau.num_rows(); i-- > 0 ; ) {
00302     Row& tableau_i = tableau[i];
00303     if (tableau_i[0] > 0)
00304       for (dimension_type j = tableau_old_n_cols; j-- > 0; )
00305         neg_assign(tableau_i[j]);
00306   }
00307 
00308   // Add the columns for all the slack variables, plus an additional
00309   // column for the sign of the cost function, provided we are not going
00310   // to exceed the maximum number of allowed columns.
00311   if (tableau.max_num_columns() - tableau_old_n_cols <= tableau.num_rows())
00312     throw std::length_error("PPL::LP_Problem:\nthe maximum size of an "
00313                             "internal data structure has been exceeded "
00314                             "while solving the LP_Problem.");
00315   tableau.add_zero_columns(tableau.num_rows() + 1);
00316   // Set the working cost function with the right size.
00317   working_cost = Row(tableau.num_columns(), Row::Flags());
00318 
00319   // Modify the tableau and the new cost function by adding
00320   // the slack variables (which enter the base).
00321   // As for the cost function, all the slack variables should have
00322   // coefficient -1.
00323   for (dimension_type i = 0; i < tableau.num_rows(); ++i) {
00324     const dimension_type j = tableau_old_n_cols + i;
00325     tableau[i][j] = 1;
00326     working_cost[j] = -1;
00327     base[i] = j;
00328   }
00329 
00330   // Set the extra-coefficient of the cost functions to record its sign.
00331   // This is done to keep track of the possible sign's inversion.
00332   const dimension_type last_obj_index = working_cost.size() - 1;
00333   working_cost[last_obj_index] = 1;
00334 
00335   // Express the problem in terms of the variables in base.
00336   for (dimension_type i = tableau.num_rows(); i-- > 0; )
00337     linear_combine(working_cost, tableau[i], base[i]);
00338 }

void Parma_Polyhedra_Library::LP_Problem::erase_slacks (  )  [private]

Drop unnecessary slack variables from the tableau and get ready for the second phase of the simplex algorithm.

Definition at line 343 of file LP_Problem.cc.

References base, Parma_Polyhedra_Library::Matrix::erase_to_end(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::remove_trailing_columns(), Parma_Polyhedra_Library::Row::shrink(), Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Row::swap(), swap_base(), tableau, and working_cost.

Referenced by is_satisfiable().

00343                             {
00344   const dimension_type tableau_last_index = tableau.num_columns() - 1;
00345   dimension_type tableau_n_rows = tableau.num_rows();
00346   const dimension_type first_slack_index = tableau_last_index - tableau_n_rows;
00347 
00348   // Step 1: try to remove from the base all the remaining slack variables.
00349   for (dimension_type i = 0; i < tableau_n_rows; ++i)
00350     if (base[i] >= first_slack_index) {
00351       // Search for a non-zero element to enter the base.
00352       Row& tableau_i = tableau[i];
00353       bool redundant = true;
00354       for (dimension_type j = first_slack_index; j-- > 1; )
00355         if (tableau_i[j] != 0) {
00356           swap_base(j, i);
00357           redundant = false;
00358           break;
00359         }
00360       if (redundant) {
00361         // No original variable entered the base:
00362         // the constraint is redundant and should be deleted.
00363         --tableau_n_rows;
00364         if (i < tableau_n_rows) {
00365           // Replace the redundant row with the last one,
00366           // taking care of adjusting the iteration index.
00367           tableau_i.swap(tableau[tableau_n_rows]);
00368           base[i] = base[tableau_n_rows];
00369           --i;
00370         }
00371         tableau.erase_to_end(tableau_n_rows);
00372         base.pop_back();
00373       }
00374     }
00375 
00376   // Step 2: Adjust data structures so as to enter phase 2 of the simplex.
00377 
00378   // Compute the dimensions of the new tableau.
00379   const dimension_type new_tableau_n_cols = first_slack_index + 1;
00380   const dimension_type new_tableau_last_index = first_slack_index;
00381 
00382   // Adjust the number of columns of `tableau'.
00383   tableau.remove_trailing_columns(tableau.num_columns() - new_tableau_n_cols);
00384   // Zero the last column of the tableau.
00385   for (dimension_type i = tableau_n_rows; i-- > 0; )
00386     tableau[i][new_tableau_last_index] = 0;
00387 
00388   // ... then properly set the element in the (new) last column,
00389   // encoding the kind of optimization; ...
00390   working_cost[new_tableau_last_index] = working_cost[tableau_last_index];
00391   // ... and finally remove redundant columns.
00392   const dimension_type working_cost_new_size = working_cost.size() -
00393     (tableau_last_index - new_tableau_last_index);
00394   working_cost.shrink(working_cost_new_size);
00395 }

bool Parma_Polyhedra_Library::LP_Problem::is_in_base ( const dimension_type  var_index,
dimension_type row_index 
) const [private]

Definition at line 613 of file LP_Problem.cc.

References base.

Referenced by compute_generator().

00614                                                              {
00615   for (row_index = base.size(); row_index-- > 0; )
00616     if (base[row_index] == var_index)
00617       return true;
00618   return false;
00619 }

PPL::Generator Parma_Polyhedra_Library::LP_Problem::compute_generator (  )  const [private]

Definition at line 622 of file LP_Problem.cc.

References dim_map, Parma_Polyhedra_Library::exact_div_assign(), input_cs, is_in_base(), Parma_Polyhedra_Library::lcm_assign(), Parma_Polyhedra_Library::Constraint_System::space_dimension(), Parma_Polyhedra_Library::sub_mul_assign(), tableau, and TEMP_INTEGER.

Referenced by is_satisfiable(), and second_phase().

00622                                        {
00623   // We will store in num[] and in den[] the numerators and
00624   // the denominators of every variable of the original problem.
00625   dimension_type original_space_dim = input_cs.space_dimension();
00626   std::vector<Coefficient> num(original_space_dim);
00627   std::vector<Coefficient> den(original_space_dim);
00628   dimension_type row = 0;
00629 
00630   // We start to compute num[] and den[].
00631   typedef std::map<dimension_type, dimension_type>::const_iterator iter;
00632   iter map_end = dim_map.end();
00633 
00634   for (dimension_type i = original_space_dim; i-- > 0; ) {
00635     Coefficient& num_i = num[i];
00636     Coefficient& den_i = den[i];
00637     // Get the value of the variable from the tableau
00638     // (if it is not a basic variable, the value is 0).
00639     if (is_in_base(i+1, row)) {
00640       const Row& t_row = tableau[row];
00641       if (t_row[i+1] > 0) {
00642         num_i= -t_row[0];
00643         den_i= t_row[i+1];
00644       }
00645       else {
00646         num_i= t_row[0];
00647         den_i= -t_row[i+1];
00648       }
00649     }
00650     else {
00651       num_i = 0;
00652       den_i = 1;
00653     }
00654     // Check whether the variable was split.
00655     iter map_iter = dim_map.find(i);
00656     if (map_iter != map_end) {
00657       // The variable was split: get the value for the negative component,
00658       // having index map[i] + 1.
00659       const dimension_type split_i = map_iter->second;
00660       // Like before, we he have to check if the variable is in base.
00661       if (is_in_base(split_i+1, row)) {
00662         const Row& t_row = tableau[row];
00663         TEMP_INTEGER(split_num);
00664         TEMP_INTEGER(split_den);
00665         if (t_row[split_i+1] > 0) {
00666           split_num = -t_row[0];
00667           split_den = t_row[split_i+1];
00668         }
00669         else {
00670           split_num = t_row[0];
00671           split_den = -t_row[split_i+1];
00672         }
00673         // We compute the lcm to compute subsequently the difference
00674         // between the 2 variables.
00675         TEMP_INTEGER(lcm);
00676         lcm_assign(lcm, den_i, split_den);
00677         exact_div_assign(den_i, lcm, den_i);
00678         exact_div_assign(split_den, lcm, split_den);
00679         num_i *= den_i;
00680         sub_mul_assign(num_i, split_num, split_den);
00681         if (num_i == 0)
00682           den_i = 1;
00683         else
00684           den_i = lcm;
00685       }
00686       // Note: if the negative component was not in base, then
00687       // it has value zero and there is nothing left to do.
00688     }
00689   }
00690 
00691   // Compute the lcm of all denominators.
00692   TEMP_INTEGER(lcm);
00693   lcm = den[0];
00694   for (dimension_type i = 1; i < original_space_dim; ++i)
00695     lcm_assign(lcm, lcm, den[i]);
00696   // Use the denominators to store the numerators' multipliers
00697   // and then compute the normalized numerators.
00698   for (dimension_type i = original_space_dim; i-- > 0; ) {
00699     exact_div_assign(den[i], lcm, den[i]);
00700     num[i] *= den[i];
00701   }
00702 
00703   // Finally, build the generator.
00704   Linear_Expression expr;
00705   for (dimension_type i = original_space_dim; i-- > 0; )
00706     expr += num[i] * Variable(i);
00707   return point(expr, lcm);
00708 }


Friends And Related Function Documentation

Definition at line 260 of file LP_Problem.inlines.hh.

References swap().

00261                                            {
00262   x.swap(y);
00263 }


Member Data Documentation

A mapping between original variables and split ones.

Contains all the pairs (i, j) such that Variable(i) (that was not found to be constrained in sign) has been split into two nonnegative variables. The "positive" one is represented again by Variable(i), and the "negative" one is represented by Variable(j).

Definition at line 228 of file LP_Problem.defs.hh.

Referenced by ascii_dump(), compute_generator(), compute_tableau(), external_memory_in_bytes(), is_satisfiable(), OK(), second_phase(), and swap().

The constraint system describing the feasible region.

Definition at line 254 of file LP_Problem.defs.hh.

Referenced by add_constraint(), add_constraints(), ascii_dump(), compute_generator(), compute_tableau(), constraints(), external_memory_in_bytes(), is_satisfiable(), OK(), space_dimension(), and swap().

The optimization mode requested.

Definition at line 260 of file LP_Problem.defs.hh.

Referenced by ascii_dump(), optimization_mode(), second_phase(), set_optimization_mode(), and swap().

The last successfully computed feasible or optimizing point.

Definition at line 263 of file LP_Problem.defs.hh.

Referenced by ascii_dump(), external_memory_in_bytes(), feasible_point(), is_satisfiable(), OK(), optimizing_point(), second_phase(), and swap().


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

Generated on Wed Jul 16 22:55:52 2008 for PPL by  doxygen 1.5.6