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_inlines_hh
00024 #define PPL_LP_Problem_inlines_hh 1
00025
00026 #include "Constraint.defs.hh"
00027 #include "Constraint_System.defs.hh"
00028 #include <stdexcept>
00029
00030 namespace Parma_Polyhedra_Library {
00031
00032 inline
00033 LP_Problem::LP_Problem()
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 }
00040
00041 inline
00042 LP_Problem::LP_Problem(const Constraint_System& cs,
00043 const Linear_Expression& obj,
00044 const Optimization_Mode mode)
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 }
00064
00065 inline
00066 LP_Problem::LP_Problem(const LP_Problem& y)
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 }
00073
00074 inline
00075 LP_Problem::~LP_Problem() {
00076 }
00077
00078 inline void
00079 LP_Problem::swap(LP_Problem& y) {
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 }
00090
00091 inline LP_Problem&
00092 LP_Problem::operator=(const LP_Problem& y) {
00093 LP_Problem tmp(y);
00094 swap(tmp);
00095 return *this;
00096 }
00097
00098 inline dimension_type
00099 LP_Problem::max_space_dimension() {
00100 return Constraint_System::max_space_dimension();
00101 }
00102
00103 inline dimension_type
00104 LP_Problem::space_dimension() const {
00105 return input_cs.space_dimension();
00106 }
00107
00108 inline const Constraint_System&
00109 LP_Problem::constraints() const {
00110 return input_cs;
00111 }
00112
00113 inline const Linear_Expression&
00114 LP_Problem::objective_function() const {
00115 return input_obj_function;
00116 }
00117
00118 inline Optimization_Mode
00119 LP_Problem::optimization_mode() const {
00120 return opt_mode;
00121 }
00122
00123 inline void
00124 LP_Problem::clear() {
00125 LP_Problem tmp;
00126 swap(tmp);
00127 }
00128
00129 inline void
00130 LP_Problem::add_constraint(const Constraint& c) {
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
00137
00138 status = UNSOLVED;
00139 }
00140
00141 inline void
00142 LP_Problem::add_constraints(const Constraint_System& cs) {
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
00151
00152 status = UNSOLVED;
00153 assert(OK());
00154 }
00155
00156 inline void
00157 LP_Problem::set_objective_function(const Linear_Expression& obj) {
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 }
00175
00176 inline void
00177 LP_Problem::set_optimization_mode(Optimization_Mode mode) {
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 }
00193
00194 inline LP_Problem_Status
00195 LP_Problem::solve() const {
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 }
00206
00207 inline const Generator&
00208 LP_Problem::feasible_point() const {
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 }
00216
00217 inline const Generator&
00218 LP_Problem::optimizing_point() const {
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 }
00224
00225 inline void
00226 LP_Problem::optimal_value(Coefficient& num, Coefficient& den) const {
00227 const Generator& g_ref = optimizing_point();
00228 evaluate_objective_function(g_ref, num, den);
00229 assert(OK());
00230 }
00231
00232 inline memory_size_type
00233 LP_Problem::external_memory_in_bytes() const {
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
00241 n += base.capacity() * sizeof(dimension_type);
00242
00243
00244 n += dim_map.size()
00245 * sizeof(std::map<dimension_type, dimension_type>::value_type);
00246 return n;
00247 }
00248
00249 inline memory_size_type
00250 LP_Problem::total_memory_in_bytes() const {
00251 return sizeof(*this) + external_memory_in_bytes();
00252 }
00253
00254 }
00255
00256 namespace std {
00257
00259 inline void
00260 swap(Parma_Polyhedra_Library::LP_Problem& x,
00261 Parma_Polyhedra_Library::LP_Problem& y) {
00262 x.swap(y);
00263 }
00264
00265 }
00266
00267 #endif // !defined(PPL_LP_Problem_inlines_hh)