- Main Page
- Classes
- Files

- File List
- File Members

# LagBaBCover.h

Go to the documentation of this file.

    00001 #ifndef LagBaBCoverH
    00002 #define LagBaBCoverH
    00003
    00004 //#include "AuraCover.h"
    00005 #include "CovMatrix.h"
    00006 #include "Cover.h"
    00007
    00008 #define NEG_INFINITY -100000000.0/0.0000001f
    00009 #define POS_INFINITY +100000000.0/0.0000001f
    00010 #define NG_INFINITY -2147483647
    00011 #define PS_INFINITY +2147483647
    00012
    00013
    00014 #ifndef AuraCoverH
    00015
    00017 struct header_of_solution_UCP {
    00018
    00020         long Cost;
    00021
    00023         struct CLink *SetC;
    00024 };
    00025
    00027 struct CLink {
    00028
    00030         struct CLink *Previous;
    00031
    00033         struct CLink *Next;
    00034
    00036         int ID;
    00037
    00038         //int Offset; //Offset to jump from one item to next
    00039
    00041         int Cost;
    00042
    00044         int NumberOf1;
    00045 };
    00046
    00048 struct CoveringMatrix {
    00049
    00051         struct CLink *RowLink;
    00052
    00054         struct CLink *ColLink;
    00055
    00057         long Cost;
    00058
    00060         int Dirty;
    00061
    00063         int countOfCols;
    00064
    00066         int countOfRows;
    00067
    00068         //pridano pro tvoreni doplnkove matice MSIR k matici, kde radky MSIR chybi
    00069         //int MSIR;
    00070
    00072         int countOfOnes;
    00073
    00075         char * *Array;    //Matice
    00076
    00077         //int lbound;
    00078 };
    00079
    00080 #endif
    00081
    00083 class SCPView {
    00084
    00086         CovMatrix* matrix_all;
    00088         int row_count;
    00090         int column_count;
    00092         int* column_map;
    00094         int* row_map;
    00095
    00096         friend class LagrangeSolver;
    00097
    00098 public:
    00099
    00100         SCPView(CovMatrix* matrix_all,CoveringMatrix* matrix);
    00101         ~SCPView();
    00102
    00108         unsigned char get(int row,int column);
    00109
    00113         int get_cost(int column);
    00114
    00115
    00117         unsigned int get_row_count() {return row_count;};
    00119         unsigned int get_column_count() {return column_count;};
    00120
    00124         int get_row_map(int row) { return row_map[row];};
    00125
    00129         int get_column_map(int column) { return column_map[column];};
    00130
    00132         void print();
    00133
    00134 };
    00135
    00137 class LagrangeSolver {
    00138
    00139 private:
    00140
    00142         SCPView* problemView;
    00143
    00145         float ZUB;
    00146
    00148         float ZLP;
    00149
    00151         float ZLB;
    00152
    00154         int lbound;
    00155
    00157         float heur_value;
    00158
    00160         int best_heur_value;
    00161
    00163         float* t;
    00164
    00166         float* n;
    00167
    00169         unsigned char* primal_delta;
    00170
    00172         unsigned char* dual_delta;
    00173
    00175         unsigned char* x;
    00176
    00178         float* y;
    00179
    00181         unsigned char* x_heur;
    00182
    00184         unsigned char* x_best;
    00185
    00187         int selected_columns;
    00188
    00190         int* help_indexes;
    00191
    00193         float* help_costs;
    00194
    00196         int* help_number_of_ones;
    00197
    00199         int covered_rows;
    00200
    00202         bool* row_is_covered;
    00203
    00207         unsigned char* column_is_recounted;
    00208
    00212         unsigned char* row_is_recounted;
    00213
    00215         float* costs;
    00216
    00218         float* reduced_costs;
    00219
    00221         float* modified_reduced_costs;
    00222
    00224         float* min_costs;
    00225
    00227         float* dual_reduced_costs;
    00228
    00230         int* primal_slack;
    00231
    00233         float* dual_slack;
    00234
    00236         int iterations;
    00237
    00239         int sup_iterations;
    00240
    00242         int sup_dual_iterations;
    00243
    00245         float step_coefficient;
    00246
    00248         float dual_step_coefficient;
    00249
    00251         float step_coefficient_min;
    00252
    00254         int step_coefficient_iter;
    00255
    00257         float sup_ZLB;
    00258
    00260         float sup_ZUB;
    00261
    00263         int** rows_covered_by_column;
    00264
    00266         int* rows_covered_by_column_count;
    00267
    00269         int** columns_covered_by_row;
    00270
    00272         int* columns_covered_by_row_count;
    00273
    00275         int primal_subgradient;
    00276
    00278         float dual_subgradient;
    00279
    00281         float primal_step;
    00282
    00284         float dual_step;
    00285
    00287         int primal_step_change_stop;
    00288
    00290         int dual_step_change_stop;
    00291
    00293         int recommended_column;
    00294
    00296         void initialize(int randomizeMultipliers,float stepCoef, float stepCoefMin, int stepCoefIter);
    00297
    00299         int find_heur_ub();
    00300
    00302         void randomize_multipliers(int minCost, int maxCost);
    00303
    00305         void solve_lp();
    00306
    00308         void solve_dlp();
    00309
    00311         void solve_dlp_next();
    00312
    00316         void ha(int removeType);
    00317
    00321         void ha_modified(int removeType);
    00322
    00327         int compute_subgradient();
    00328
    00332         float get_primal_reduced_cost(int columnIndex);
    00333
    00337         float get_dual_reduced_cost(int rowIndex);
    00338
    00340         void update_best_solution(float candZUB);
    00341
    00342
    00343
    00344
    00345 public:
    00346
    00347         LagrangeSolver(SCPView* pv);
    00348         ~LagrangeSolver();
    00349
    00351         int get_lgsolution_cost() { return best_heur_value;};
    00352
    00354         unsigned char* get_best_solution() {return x_best;};
    00355
    00357         int get_lower_bound() { return lbound;};
    00358
    00360         int get_recommended_column() { return recommended_column;};
    00361
    00371         void solve(int iterations,int randomizeCosts, int heuristic, int heurIterations, float stepCoef, float stepCoefMin,int stepCoefIter,int maxLowerBound);
    00372
    00385         void solve_dual(int iterations, int heuristic, int heurIterations,float stepCoef, float stepCoefMin,int stepCoefIter, int maxLowerBound,
    00386                 float stepCoefDual, float stepCoefMinDual,int stepCoefIterDual);
    00387
    00388 };
    00389
    00397 int  compare_three_arrays(float costs[],int number_of_ones[],int c1, int c2);
    00398
    00406 void swap_in_arrays(int columns[], float costs[],int number_of_ones[],int left, int right);
    00407
    00415 void quick_sort_three_arrays(int columns[], float costs[],int number_of_ones[], int l, int r);
    00416
    00423 int compare_column_links(CLink* links[],int c1, int c2);
    00424
    00431 int compare_row_links(CLink* links[],int r1, int r2);
    00432
    00438 void swap_in_links(CLink* links[],int left, int right);
    00439
    00440
    00446 void quick_sort_column_links(CLink* links[], int l, int r);
    00447
    00453 void quick_sort_row_links(CLink* links[], int l, int r);
    00454
    00455
    00457 class LagBaBCover {
    00458
    00459 private:
    00460
    00462         long uBound;
    00463
    00465         long MaxCost;
    00466
    00468         long NumCalls;
    00469
    00471         float lagrangeTime;
    00472
    00474         struct CoveringMatrix *covering_matrix;
    00475
    00477         struct header_of_solution_UCP *solution_UCP;
    00478
    00480         CovMatrix* covMatrix;
    00481
    00483         int *bestLgSolution;
    00484
    00486         long bestLgSolutionCost;
    00487
    00489         char bestLgSolutionUsed;
    00490
    00492         long double  bestLgState;
    00493
    00495         CoverOpts* options;
    00496
    00497         //bool isAllCovered;
    00498
    00502         struct CoveringMatrix *rebuild_matrix (CovMatrix *CVM);
    00503
    00508         struct CoveringMatrix* duplicate ( struct CoveringMatrix *CM);
    00509
    00514         void create_matrix ( struct CoveringMatrix *Cm,int *Costs );
    00515
    00519         void sort_matrix ( struct CoveringMatrix *Cm);
    00520
    00527         int branch_bound_lagrange ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolUCP,long double  instance);
    00528
    00532         void release (struct CoveringMatrix * CM);
    00533
    00537         void release ( struct header_of_solution_UCP *SolUCP );
    00538
    00541         struct header_of_solution_UCP *create_New_Empty_Solution ( void );
    00542
    00547         void append_to_solution (struct header_of_solution_UCP *Source,struct header_of_solution_UCP *Target );
    00548
    00553         void add_to_solution ( struct header_of_solution_UCP *SolutionUCP,struct CLink *Column );
    00554
    00561         void add_to_solution_masked( struct header_of_solution_UCP *TargetSolution,struct CoveringMatrix* Matrix,unsigned char* mask, int len);
    00562
    00567         list<unsigned int> rebuild_solution (struct header_of_solution_UCP *SolutionUCP);
    00568
    00573         void remove_col_from_matrix ( struct CoveringMatrix *CM, struct CLink *colToRemove );
    00574
    00579         void remove_col_from_matrix ( struct CoveringMatrix *CM, int ID );
    00580
    00585         void remove_row_from_matrix ( struct CoveringMatrix *CM, struct CLink *rowToRemove );
    00586
    00591         void remove_col_with_rows ( struct CLink * Column, struct CoveringMatrix *CM );
    00592
    00597         void find_number_of_ones ( struct CoveringMatrix *CM);
    00598
    00603         void solve_row_dominance ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP );
    00604
    00608         void solve_column_dominance ( struct CoveringMatrix *CM);
    00609
    00615         int solve_dominance ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP );
    00616
    00617
    00622         void check_essentiality ( struct CoveringMatrix *CM,struct header_of_solution_UCP *SolutionUCP );
    00623
    00629         float evaluate_column (struct CoveringMatrix *CM,struct CLink *ColumnLink);
    00630
    00635         struct CLink* select_col_contrib (struct CoveringMatrix *CM);
    00636
    00637
    00638         bool check_coverage ( struct CoveringMatrix *CM,list<unsigned int> solution );
    00639
    00640 public:
    00641
    00642         LagBaBCover( CovMatrix *_matrix );
    00643         ~LagBaBCover();
    00644
    00648         list<unsigned int> Run();
    00649
    00654         list<unsigned int> Run(CoverOpts* opts);
    00655
    00658         float getLagrangeanTime(){ return lagrangeTime; };
    00659
    00662         unsigned int getExpandedStates(){ return NumCalls; };
    00663
    00666         //bool getIsAllCovered(){return isAllCovered;};
    00667
    00668 };
    00669
    00670 #endif