#include <LP_Problem.defs.hh>
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_Problem & | operator= (const LP_Problem &y) |
Assignment operator. | |
dimension_type | space_dimension () const |
Returns the space dimension of the current LP problem. | |
const Constraint_System & | constraints () const |
Returns the constraints defining the current feasible region. | |
const Linear_Expression & | objective_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 ![]() evaluating_point . | |
const Generator & | feasible_point () const |
Returns a feasible point for *this , if it exists. | |
const Generator & | optimizing_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 ![]() | |
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_type > | base |
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) |
Definition at line 40 of file LP_Problem.defs.hh.
enum Parma_Polyhedra_Library::LP_Problem::Status [private] |
An enumerated type describing the internal status of the LP problem.
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 };
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 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
.
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 ![]() | |
mode | The optimization mode (optional argument with default value MAXIMIZATION ). |
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] |
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.
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.
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
.
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
.
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.
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 is the result of evaluating the objective function on
evaluating_point
.
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. |
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.
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.
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 is the solution of the optimization problem.
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.
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.
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.
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.
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 ![]() |
x
and y
having the element of index k
equal 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.
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.
0
is retuned.
Recall that, due to the Integer implementation of the algorithm, our tableau doesn't contain the ``real'' 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 }
void swap | ( | Parma_Polyhedra_Library::LP_Problem & | x, | |
Parma_Polyhedra_Library::LP_Problem & | y | |||
) | [related] |
Definition at line 260 of file LP_Problem.inlines.hh.
References swap().
00261 { 00262 x.swap(y); 00263 }
The matrix encoding the current feasible region in tableau form.
Definition at line 216 of file LP_Problem.defs.hh.
Referenced by ascii_dump(), compute_generator(), compute_simplex(), compute_tableau(), erase_slacks(), external_memory_in_bytes(), get_exiting_base_index(), is_satisfiable(), OK(), prepare_first_phase(), second_phase(), steepest_edge(), swap(), and swap_base().
The working cost function.
Definition at line 218 of file LP_Problem.defs.hh.
Referenced by ascii_dump(), compute_simplex(), erase_slacks(), external_memory_in_bytes(), get_entering_var_index(), is_satisfiable(), OK(), prepare_first_phase(), second_phase(), steepest_edge(), swap(), and swap_base().
std::vector<dimension_type> Parma_Polyhedra_Library::LP_Problem::base [private] |
The current basic solution.
Definition at line 220 of file LP_Problem.defs.hh.
Referenced by ascii_dump(), erase_slacks(), external_memory_in_bytes(), get_exiting_base_index(), is_in_base(), is_satisfiable(), OK(), prepare_first_phase(), second_phase(), steepest_edge(), swap(), and swap_base().
std::map<dimension_type, dimension_type> Parma_Polyhedra_Library::LP_Problem::dim_map [private] |
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 internal state of the LP problem.
Definition at line 251 of file LP_Problem.defs.hh.
Referenced by add_constraint(), add_constraints(), ascii_dump(), compute_tableau(), is_satisfiable(), OK(), second_phase(), set_objective_function(), set_optimization_mode(), solve(), 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 objective function to be optimized.
Definition at line 257 of file LP_Problem.defs.hh.
Referenced by ascii_dump(), compute_tableau(), evaluate_objective_function(), external_memory_in_bytes(), objective_function(), OK(), second_phase(), set_objective_function(), 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().