Lurupa: Lurupa.h Source File

00001 /*
00002  * Lurupa, a library for verified linear programming.
00003  * Copyright (C) 2006 by Christian Keil
00004  *
00005  * This file is part of Lurupa.
00006  *
00007  * Lurupa is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Lesser General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2.1 of the License, or (at your option) any later version.
00011  *
00012  * This library is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Lesser General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Lesser General Public
00018  * License along with this library; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
00020  * USA
00021  */
00022 
00033 #ifndef LURUPA_LURUPA_H
00034 #define LURUPA_LURUPA_H
00035 
00036 #include <lurupa/Solver_module.h>
00037 #include <lurupa/Report.h>
00038 #include <lurupa/globals.h>
00039 #include <IntervalMatrix.h>
00040 #include <IntervalVector.h>
00041 #include <Vector.h>
00042 #include <ltdl.h>
00043 
00044 #ifndef LU_LURUPA_SCOPE
00045 #  if defined(_WIN32) || defined(WIN32)
00046 #    ifdef LU_LURUPA_IMPORT
00047 #      define LU_LURUPA_SCOPE __declspec(dllimport)
00048 #    elif defined DLL_EXPORT
00049 #      define LU_LURUPA_SCOPE __declspec(dllexport)
00050 #    endif
00051 #  endif
00052 #  ifndef LU_LURUPA_SCOPE
00053 #    define LU_LURUPA_SCOPE
00054 #  endif
00055 #endif
00056 
00057 class Condition;
00058 class Lp;
00059 
00069 class LU_LURUPA_SCOPE Lurupa {
00070 public:
00071   Lurupa();
00072   ~Lurupa();
00073 
00075   const char *get_core_version() const;
00077   void print_core_version() const;
00079   void print_core_brief_version() const;
00081   void print_module_version() const;
00083   void print_module_brief_version() const;
00084 
00087   double get_alpha() const;
00089   void set_alpha(double alpha);
00090 
00092   double get_eta() const;
00094   void set_eta(double eta);
00095 
00097   bool is_inflate() const;
00099   void set_inflate(bool inflate);
00104   bool set_module(char *module_path);
00105 
00107   void set_interface(Solver_module_interface module);
00108 
00110   const char *get_module_version() const;
00111 
00113   void print_module_options() const;
00114 
00116   double get_solver_eps() const;
00117 
00119   Lp *read_lp(FILE *in, const double &relative_interval_radius);
00120 
00122   bool set_solution(Lp *lp, void *p);
00123 
00125   bool set_lp(Lp *lp, const double relative_interval_radius);
00126 
00128   void lp2solver(Lp *lp);
00129 
00131   bool set_module_options(Lp *lp, int argc, char *argv[]);
00132 
00134   Solver_status solve_lp(Lp *lp, double &optimal_value);
00139   void rho_p(Lp *lp, double &lower, double &upper);
00141   void rho_d(Lp *lp, double &lower, double &upper);
00143   void cond(Lp *lp, double &lower, double &upper);
00147   Bound_status lower_bound(Lp *lp, double &bound, int &iterations);
00148 
00150   Bound_status upper_bound(Lp *lp, double &bound, int &iterations);
00151 
00153   Bound_status dual_certificate(Lp *lp);
00154 
00156   Bound_status primal_certificate(Lp *lp);
00157 
00159   char *get_lp_name() const;
00160 
00162   bool is_lp_maximize() const;
00163 
00164   Report report;          
00166   friend class Condition;
00167   friend class Lp;
00168 
00169 private:
00171   Solver_module_interface solver_module;
00172 
00174   lt_dlhandle mod_handle;
00175 
00176   int iteration;          
00177   int max_iterations;     
00178   bool inflate;           
00179   double eta;             
00180   double eps;             
00181   double alpha;           
00191   double pivot_element(MATRIX LU, int step, int &pivot_index);
00193   void do_pivot(MATRIX &LU, int pivot_index, int step, int *basis_indices);
00195   void eliminate(MATRIX &LU, int step);
00197   void add_column_to_basis(int step, INTERVAL_MATRIX &A,
00198                            INTERVAL_MATRIX &IBasis, int *basis_indices);
00200   void shorten_basis_indices(int *&basis_indices, int basis_size);
00202   bool find_basis(INTERVAL_MATRIX &A,
00203                   int *&basis_indices, int size_basis_indices,
00204                   INTERVAL_MATRIX &IBasis, MATRIX &Basis_mid_inverse);
00215   void establish_ix_simple_bounds(Lp *lp);
00217   bool establish_equality_constraints(Lp *lp, const INTERVAL_MATRIX &IBasis,
00218                                       const MATRIX &Basis_mid_inverse,
00219                                       const INTERVAL_MATRIX &IResidual,
00220                                       const int *basis_indices);
00222   bool primal_feasible(Lp *lp);
00224   Bound_status establish_primal_feasibility(Lp *lp,
00225                                             const INTERVAL_MATRIX &IBasis,
00226                                             const MATRIX &Basis_mid_inverse,
00227                                             const INTERVAL_MATRIX &IResidual,
00228                                             const int *basis_indices);
00239   void establish_iy_simple_bounds(Lp *lp);
00241   Bound_status process_free_variables(Lp *lp, const INTERVAL_MATRIX &IBasis,
00242                                       const MATRIX &Basis_mid_inverse,
00243                                       const INTERVAL_MATRIX &IResidual,
00244                                       const int *basis_indices);
00246   Bound_status process_bounded_variables(Lp *lp, INTERVAL_VECTOR &id_pos,
00247                                          INTERVAL_VECTOR &id_neg);
00249   Bound_status establish_lagrange_parameters(Lp *lp, const INTERVAL_MATRIX &IBasis,
00250                                              const MATRIX &Basis_mid_inverse,
00251                                              const INTERVAL_MATRIX &IResidual,
00252                                              const int *basis_indices,
00253                                              INTERVAL_VECTOR &id_pos,
00254                                              INTERVAL_VECTOR &id_neg);
00256   Bound_status establish_dual_feasibility(Lp *lp, const INTERVAL_MATRIX &IBasis,
00257                                           const MATRIX &Basis_mid_inverse,
00258                                           const INTERVAL_MATRIX &IResidual,
00259                                           const int *basis_indices,
00260                                           INTERVAL_VECTOR &id_pos,
00261                                           INTERVAL_VECTOR &id_neg);
00272   bool find_equation_basis(Lp *lp, INTERVAL_MATRIX &IResidual, int *&basis_indices, 
00273                            INTERVAL_MATRIX &IBasis, MATRIX &Basis_mid_inverse);
00275   void process_initial_primal_solution(Lp *lp, Bound_status &status, double &bound,
00276                                        const INTERVAL_MATRIX &IBasis,
00277                                        const MATRIX &Basis_mid_inverse,
00278                                        const INTERVAL_MATRIX &IResidual,
00279                                        const int *basis_indices);
00281   void compute_primal_deflation(Lp *lp, Primal_deflation &d);
00283   void increase_primal_deflation(Lp *lp, Primal_deflation &d);
00285   void decrease_primal_deflation(Lp *lp, Primal_deflation &d);
00287   void process_perturbed_primal_solution(Lp *lp, Bound_status &status, double &bound,
00288                                          const INTERVAL_MATRIX &IBasis,
00289                                          const MATRIX &Basis_mid_inverse,
00290                                          const INTERVAL_MATRIX &IResidual,
00291                                          const int *basis_indices,
00292                                          Primal_deflation &deflation);
00294   Bound_status compute_upper(Lp *lp, double &bound);
00305   bool find_constraint_basis(Lp *lp, INTERVAL_MATRIX &IResidual, int *&basis_indices,
00306                              INTERVAL_MATRIX &IBasis, MATRIX &Basis_mid_inverse);
00308   void process_initial_dual_solution(Lp *lp, Bound_status &status, double &bound,
00309                                      const INTERVAL_MATRIX &IBasis,
00310                                      const MATRIX &Basis_mid_inverse,
00311                                      const INTERVAL_MATRIX &IResidual,
00312                                      const int *basis_indices);
00314   void compute_dual_deflation(Lp *lp, VECTOR &d_c);
00316   void increase_dual_deflation(Lp *lp, VECTOR &d_c,
00317                                const INTERVAL_VECTOR &id_pos,
00318                                const INTERVAL_VECTOR &id_neg);
00320   void decrease_dual_deflation(Lp *lp, VECTOR &d_c);
00322   void process_perturbed_dual_solution(Lp *lp, Bound_status &status, double &bound,
00323                                        const INTERVAL_MATRIX &IBasis,
00324                                        const MATRIX &Basis_mid_inverse,
00325                                        const INTERVAL_MATRIX &IResidual,
00326                                        const int *basis_indices,
00327                                        VECTOR &deflation_c);
00329   Bound_status compute_lower(Lp *lp, double &bound);
00333   void set_primal_phase1(Lp *lp, bool *maximize);
00335   void restore_primal_phase1(Lp *lp, const INTERVAL_VECTOR &icT, const bool maxmimize);
00337   void set_dual_phase1(Lp *lp);
00339   void restore_dual_phase1(Lp *lp, const INTERVAL_VECTOR &iaT, const INTERVAL_VECTOR &ibT, 
00340                            const VECTOR &xlT, const VECTOR &xuT, const int non_fixed_varsT,
00341                            const int free_variables_sizeT);
00342 
00343 }; /* class Lurupa */
00344 
00345 #endif /* LURUPA_LURUPA_H */