MeshKit  1.0
IAMilp.hpp
Go to the documentation of this file.
00001 // IAMilp.hpp
00002 // Interval Assignment for Meshkit
00003 //
00004 // This is the solver-translation from Meshkit to the GLPK library
00005 // for solving the MILP (integer solution, no fractional intervals)
00006 //
00007 
00008 #ifndef MESHKIT_IA_IAMILP_HP
00009 #define MESHKIT_IA_IAMILP_HP
00010 
00024 #include <vector>
00025 
00026 #incude "IAWeights.hpp"
00027 
00028 // forward declarations
00029 class IAData;
00030 class IASolution;
00031 class GlpRepresentation;
00032 
00033 class IAMilp
00034 {
00035 public:
00037   // on input, solution_ptr contains a non-integer solution to the interval assignment problem
00038   IAMilp(const IAData *data_ptr, IASolution *solution_ptr); 
00039 
00041   virtual ~IAMilp();
00042 
00043   // Find an integer solution.
00044   // on completion, the integer solution is placed into the solution_ptr that was passed to the constructor
00045   bool solve();
00046   
00047 private:  
00048   // hide untrusted default methods
00050   //  IA_NLP();
00051   IAMilp();
00052   IAMilp(const IAMilp&);
00053   IAMilp& operator=(const IAMilp&);
00055   
00056   // input data
00057   const IAData *data;
00058   // solution data
00059   IASolution *solution;
00060   
00061   // scratch space
00062   // objective weights of deltas
00063   IAWeights weights_plus;
00064   IAWeights weights_minus;
00065   
00066   const bool debugging;
00067 
00068   // much roundoff is tolerated before treating it as integer or satisfied
00069   const double constraint_tolerance;
00070   const double integrality_tolerance;
00071   
00072   // glpk-implementation specific 
00073   GlpRepresentation *lp;
00074   bool naturalConstraintsSet;
00075   bool deltasSet;
00076   bool weightsSet;
00077   bool maxesSet;
00078   bool solved;
00079   
00080   // translate our indices to glpk indexing
00081   int xStart; // column index
00082   int x_i(int i); // glpk index for curve_i
00083   int deltaStart; // column index
00084   int delta_plus_i(int i); // glpk col index for curve_i's value above its goal
00085   int delta_minus_i(int i);// glpk col index for curve_i's value below its goal
00086   int deltaConstraintStart; // first row index of constraint that forces x_i - I_i = p_i - n_i
00087   int delta_j(int j); // continuation of above 
00088   int mwp_i;  // column index of maximum of weighted delta_plus variable
00089   int mwp_j;  // first row index of constraint that calculates mwp variable
00090   int mwm_i;  // column index of maximum of weighted deltas_minus variable
00091   int mwm_j;  // first row index of constraint that calculates mwm variable
00092   int mw_i;  // column index of maximum of weighted deltas_minus variable
00093   int mw_j;  // row index of constaint that calculates mw > mwp variable, mw_j+1 calcs mw > mwm
00094   
00095   // substeps in setting up and solving the solution
00096   bool create_problem();
00097   bool destroy_problem();
00098   bool set_natural_constraints();
00099   bool set_deltas();
00100   bool weight_deltas_1();
00101   bool set_maxes();
00102   bool set_objectives_1();
00103   bool set_sum_even_constratins();
00104   bool set_bounds_1();
00105   bool set_bounds_2();
00106   bool set_bounds_3();
00107   bool set_bounds_4();
00108   bool set_bounds_A();
00109   bool set_bounds_B();
00110   bool glpk_solve(bool &optimal);
00111   bool get_solution();
00112   bool solution_is_integer();
00113   bool solution_satisfies_constraints();
00114   void print_constraint(int j);
00115   void print_solution(int i);
00116 
00117   
00118   
00119   // utilities
00120   // fill with [I,x_solution] or [x_solution,I], depending on which is smaller and defines a proper interval
00121   void get_x_bounds(const int i, double &lobound, double &hibound);
00122 };
00123 
00124 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines