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_MIP_Problem_defs_hh
00024 #define PPL_MIP_Problem_defs_hh 1
00025
00026 #include "MIP_Problem.types.hh"
00027 #include "globals.types.hh"
00028 #include "Row.defs.hh"
00029 #include "Matrix.defs.hh"
00030 #include "Linear_Expression.defs.hh"
00031 #include "Constraint.types.hh"
00032 #include "Constraint_System.types.hh"
00033 #include "Generator.defs.hh"
00034 #include "Variables_Set.defs.hh"
00035 #include <vector>
00036 #include <deque>
00037 #include <iosfwd>
00038
00039 namespace Parma_Polyhedra_Library {
00040
00041 namespace IO_Operators {
00042
00044
00045 std::ostream&
00046 operator<<(std::ostream& s, const MIP_Problem& lp);
00047
00048 }
00049
00050 }
00051
00053
00079 class Parma_Polyhedra_Library::MIP_Problem {
00080 public:
00082
00094 explicit MIP_Problem(dimension_type dim = 0);
00095
00132 template <typename In>
00133 MIP_Problem(dimension_type dim,
00134 In first, In last,
00135 const Variables_Set& int_vars,
00136 const Linear_Expression& obj = Linear_Expression::zero(),
00137 Optimization_Mode mode = MAXIMIZATION);
00138
00170 template <typename In>
00171 MIP_Problem(dimension_type dim,
00172 In first, In last,
00173 const Linear_Expression& obj = Linear_Expression::zero(),
00174 Optimization_Mode mode = MAXIMIZATION);
00175
00201 MIP_Problem(dimension_type dim,
00202 const Constraint_System& cs,
00203 const Linear_Expression& obj = Linear_Expression::zero(),
00204 Optimization_Mode mode = MAXIMIZATION);
00205
00207 MIP_Problem(const MIP_Problem& y);
00208
00210 ~MIP_Problem();
00211
00213 MIP_Problem& operator=(const MIP_Problem& y);
00214
00216 static dimension_type max_space_dimension();
00217
00219 dimension_type space_dimension() const;
00220
00225 const Variables_Set& integer_space_dimensions() const;
00226
00227 private:
00229 typedef std::vector<Constraint> Constraint_Sequence;
00230
00231 public:
00236 typedef Constraint_Sequence::const_iterator const_iterator;
00237
00242 const_iterator constraints_begin() const;
00243
00248 const_iterator constraints_end() const;
00249
00251 const Linear_Expression& objective_function() const;
00252
00254 Optimization_Mode optimization_mode() const;
00255
00257
00260 void clear();
00261
00276 void add_space_dimensions_and_embed(dimension_type m);
00277
00286 void add_to_integer_space_dimensions(const Variables_Set& i_vars);
00287
00295 void add_constraint(const Constraint& c);
00296
00305 void add_constraints(const Constraint_System& cs);
00306
00308
00313 void set_objective_function(const Linear_Expression& obj);
00314
00316 void set_optimization_mode(Optimization_Mode mode);
00317
00319
00323 bool is_satisfiable() const;
00324
00326
00331 MIP_Problem_Status solve() const;
00332
00350 void evaluate_objective_function(const Generator& evaluating_point,
00351 Coefficient& num,
00352 Coefficient& den) const;
00353
00355
00359 const Generator& feasible_point() const;
00360
00362
00367 const Generator& optimizing_point() const;
00368
00377 void optimal_value(Coefficient& num, Coefficient& den) const;
00378
00380 bool OK() const;
00381
00382 PPL_OUTPUT_DECLARATIONS
00383
00384 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
00385
00390 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
00391 bool ascii_load(std::istream& s);
00392
00394 memory_size_type total_memory_in_bytes() const;
00395
00397 memory_size_type external_memory_in_bytes() const;
00398
00400 void swap(MIP_Problem& y);
00401
00403 enum Control_Parameter_Name {
00405 PRICING
00406 };
00407
00409 enum Control_Parameter_Value {
00411 PRICING_STEEPEST_EDGE_FLOAT,
00413 PRICING_STEEPEST_EDGE_EXACT,
00415 PRICING_TEXTBOOK
00416 };
00417
00419 Control_Parameter_Value
00420 get_control_parameter(Control_Parameter_Name name) const;
00421
00423 void set_control_parameter(Control_Parameter_Value value);
00424
00425 private:
00427 dimension_type external_space_dim;
00428
00433 dimension_type internal_space_dim;
00434
00436 Matrix tableau;
00437
00439 Row working_cost;
00440
00442
00449 std::vector<std::pair<dimension_type, dimension_type> > mapping;
00450
00452 std::vector<dimension_type> base;
00453
00455 enum Status {
00457 UNSATISFIABLE,
00459 SATISFIABLE,
00461 UNBOUNDED,
00463 OPTIMIZED,
00469 PARTIALLY_SATISFIABLE
00470 };
00471
00473 Status status;
00474
00475
00476
00477
00478
00480 Control_Parameter_Value pricing;
00481
00487 bool initialized;
00488
00490 Constraint_Sequence input_cs;
00491
00493 dimension_type first_pending_constraint;
00494
00496 Linear_Expression input_obj_function;
00497
00499 Optimization_Mode opt_mode;
00500
00502 Generator last_generator;
00503
00508 Variables_Set i_variables;
00509
00511
00516 bool process_pending_constraints();
00517
00522 void second_phase();
00523
00537 MIP_Problem_Status
00538 compute_tableau(std::vector<dimension_type>& worked_out_row);
00539
00576 bool parse_constraints(dimension_type& new_num_rows,
00577 dimension_type& num_slack_variables,
00578 std::deque<bool>& is_tableau_constraint,
00579 std::deque<bool>& nonnegative_variable,
00580 std::vector<dimension_type>& unfeasible_tableau_rows,
00581 std::deque<bool>& satisfied_ineqs);
00582
00593 dimension_type
00594 get_exiting_base_index(dimension_type entering_var_index) const;
00595
00597
00611 static void linear_combine(Row& x, const Row& y, const dimension_type k);
00612
00622 void pivot(dimension_type entering_var_index,
00623 dimension_type exiting_base_index);
00624
00634 dimension_type textbook_entering_index() const;
00635
00661 dimension_type steepest_edge_exact_entering_index() const;
00662
00674 dimension_type steepest_edge_float_entering_index() const;
00675
00684 bool compute_simplex_using_exact_pricing();
00685
00695 bool compute_simplex_using_steepest_edge_float();
00696
00701 void erase_artificials(dimension_type begin_artificials,
00702 dimension_type end_artificials);
00703
00704 bool is_in_base(dimension_type var_index,
00705 dimension_type& row_index) const;
00706
00711 void compute_generator() const;
00712
00724 void merge_split_variables(dimension_type var_index,
00725 std::vector<dimension_type>& nonfeasible_cs);
00726
00728 static bool is_satisfied(const Constraint& c, const Generator& g);
00729
00731 static bool is_saturated(const Constraint& c, const Generator& g);
00732
00752 static MIP_Problem_Status solve_mip(bool& have_incumbent_solution,
00753 mpq_class& incumbent_solution_value,
00754 Generator& incumbent_solution_point,
00755 MIP_Problem& mip,
00756 const Variables_Set& i_vars);
00757
00758 bool is_lp_satisfiable() const;
00759
00774 static bool is_mip_satisfiable(MIP_Problem& mip, Generator& p,
00775 const Variables_Set& i_vars);
00776
00791 static bool choose_branching_variable(const MIP_Problem& mip,
00792 const Variables_Set& i_vars,
00793 dimension_type& branching_index);
00794 };
00795
00796 namespace std {
00797
00799
00800 void swap(Parma_Polyhedra_Library::MIP_Problem& x,
00801 Parma_Polyhedra_Library::MIP_Problem& y);
00802
00803 }
00804
00805 #include "MIP_Problem.inlines.hh"
00806 #include "MIP_Problem.templates.hh"
00807
00808 #endif // !defined(PPL_MIP_Problem_defs_hh)