00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef PPL_LP_Problem_defs_hh
00024 #define PPL_LP_Problem_defs_hh 1
00025
00026 #include "LP_Problem.types.hh"
00027 #include "globals.types.hh"
00028 #include "Row.defs.hh"
00029 #include "Matrix.defs.hh"
00030 #include "Constraint_System.defs.hh"
00031 #include "Linear_Expression.defs.hh"
00032 #include "Constraint.types.hh"
00033 #include "Generator.defs.hh"
00034 #include <vector>
00035 #include <map>
00036 #include <iosfwd>
00037
00039
00040 class Parma_Polyhedra_Library::LP_Problem {
00041 public:
00043
00048 LP_Problem();
00049
00070 explicit LP_Problem(const Constraint_System& cs,
00071 const Linear_Expression& obj = Linear_Expression::zero(),
00072 Optimization_Mode mode = MAXIMIZATION);
00073
00075 LP_Problem(const LP_Problem& y);
00076
00078 ~LP_Problem();
00079
00081 LP_Problem& operator=(const LP_Problem& y);
00082
00084 static dimension_type max_space_dimension();
00085
00087 dimension_type space_dimension() const;
00088
00090 const Constraint_System& constraints() const;
00091
00093 const Linear_Expression& objective_function() const;
00094
00096 Optimization_Mode optimization_mode() const;
00097
00099 void clear();
00100
00108 void add_constraint(const Constraint& c);
00109
00117 void add_constraints(const Constraint_System& cs);
00118
00120
00125 void set_objective_function(const Linear_Expression& obj);
00126
00128 void set_optimization_mode(Optimization_Mode mode);
00129
00131
00135 bool is_satisfiable() const;
00136
00138
00143 LP_Problem_Status solve() const;
00144
00162 void evaluate_objective_function(const Generator& evaluating_point,
00163 Coefficient& num,
00164 Coefficient& den) const;
00165
00167
00171 const Generator& feasible_point() const;
00172
00174
00179 const Generator& optimizing_point() const;
00180
00189 void optimal_value(Coefficient& num, Coefficient& den) const;
00190
00192 bool OK() const;
00193
00194 PPL_OUTPUT_DECLARATIONS;
00195
00196 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
00197
00202 #endif // PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
00203 bool ascii_load(std::istream& s);
00204
00206 memory_size_type total_memory_in_bytes() const;
00207
00209 memory_size_type external_memory_in_bytes() const;
00210
00212 void swap(LP_Problem& y);
00213
00214 private:
00216 Matrix tableau;
00218 Row working_cost;
00220 std::vector<dimension_type> base;
00222
00228 std::map<dimension_type, dimension_type> dim_map;
00229
00231 enum Status {
00233 UNSOLVED,
00235 UNSATISFIABLE,
00237 SATISFIABLE,
00239 UNBOUNDED,
00241 OPTIMIZED,
00247 PARTIALLY_SATISFIABLE
00248 };
00249
00251 Status status;
00252
00254 Constraint_System input_cs;
00255
00257 Linear_Expression input_obj_function;
00258
00260 Optimization_Mode opt_mode;
00261
00263 Generator last_generator;
00264
00269 void second_phase();
00270
00284 LP_Problem_Status compute_tableau();
00285
00295 dimension_type get_entering_var_index() const;
00296
00307 dimension_type
00308 get_exiting_base_index(dimension_type entering_var_index) const;
00309
00311
00325 static void linear_combine(Row& x, const Row& y, const dimension_type k);
00326
00337 void swap_base(const dimension_type entering_var_index,
00338 const dimension_type exiting_base_index);
00339
00365 dimension_type steepest_edge() const;
00366
00371 bool compute_simplex();
00372
00378 void prepare_first_phase();
00379
00384 void erase_slacks();
00385
00386 bool is_in_base(const dimension_type var_index,
00387 dimension_type& row_index) const;
00388
00389 Generator compute_generator() const;
00390 };
00391
00392 #include "LP_Problem.inlines.hh"
00393
00394 #endif // !defined(PPL_LP_Problem_defs_hh)