/home/coin/SVN-release/Bcp-1.2.1/Applications/Mkc/include/MKC_knapsack.hpp

Go to the documentation of this file.
00001 // Copyright (C) 2000, International Business Machines
00002 // Corporation and others.  All Rights Reserved.
00003 #ifndef _MKC_KNAPSACK_H
00004 #define _MKC_KNAPSACK_H
00005 
00006 #include "BCP_vector.hpp"
00007 
00008 class BCP_buffer;
00009 
00010 //#############################################################################
00011 
00012 // This structure corresponds to an order
00013 struct MKC_knapsack_entry {
00014    int    orig_index; // it's index in the original list of vars
00015    int    index;      // the index of the order
00016    int    color;
00017    double weight;
00018    double orig_cost;  // the original cost of the order
00019    double cost;       // the costof the entry in the knapsack subproblems
00020    double ratio;      // the cost/weight ratio in the knapsack subproblems
00021 public:
00022    MKC_knapsack_entry() : orig_index(-2), index(-2), color(-2),
00023       weight(0.0), orig_cost(0.0), cost(0.0), ratio(0.0) {}
00024    ~MKC_knapsack_entry() {}
00025    void pack(BCP_buffer& buf);
00026    void unpack(BCP_buffer& buf);
00027 };
00028 
00029 //#############################################################################
00030 
00031 inline bool MKC_ks_entry_color_ascend(const MKC_knapsack_entry& order0,
00032                                       const MKC_knapsack_entry& order1)
00033 {
00034    return order0.color < order1.color;
00035 }
00036 
00037 inline bool MKC_ks_entry_ratio_descend(const MKC_knapsack_entry& order0,
00038                                        const MKC_knapsack_entry& order1)
00039 {
00040    return order0.ratio > order1.ratio;
00041 }
00042 
00043 inline bool MKC_ks_entry_weight_ascend(const MKC_knapsack_entry& order0,
00044                                        const MKC_knapsack_entry& order1)
00045 {
00046    return order0.weight < order1.weight;
00047 }
00048 
00049 inline bool MKC_ks_entry_weight_descend(const MKC_knapsack_entry& order0,
00050                                         const MKC_knapsack_entry& order1)
00051 {
00052    return order0.weight < order1.weight;
00053 }
00054 
00055 //#############################################################################
00056 
00057 class MKC_knapsack_fixing {
00058 public:
00059    // An entry in the char vector is
00060    // 0: if the order can't be in the corresponding knapsack
00061    // 1: if there are no restrictions for that order
00062    // Note: those that must be in the KS are already listed in the fixed
00063    // entries, thus they will have a 0 in fixing.
00064    BCP_vec<char> fixing; //
00065    int fixed_entry_num;
00066    int * fixed_entries; // index in the KS
00067    int * fixed_entries_ind; // index of the order
00068    double fixed_cost;
00069    double fixed_weight;
00070 public:
00071    MKC_knapsack_fixing() :
00072       fixed_entry_num(0), fixed_entries(0), fixed_entries_ind(0),
00073       fixed_cost(0.0), fixed_weight(0.0) {}
00074    ~MKC_knapsack_fixing() {
00075       delete[] fixed_entries_ind;
00076       delete[] fixed_entries;
00077    }
00078 };
00079 
00080 //#############################################################################
00081 
00082 // This structure corresponds to a slab
00083 class MKC_knapsack {
00084 public:
00085    double cost;     // the cost of using this slab at all
00086    double capacity; 
00087    int size;        // the numbor of KS entries (orders) that can go into this
00088                     // KS (slab) at all.
00089    MKC_knapsack_entry * entries; // the orders that can go into this slab
00090                     // These entries are ordered by color
00091    int color_num;   // the number of different colors among the entries
00092    int * color_beg; // length: color_num + 1; the positions where the colors
00093                     // start in entries (remember, it's ordered by color)
00094    int orig_index; // the index of the corresponding z variable in the
00095                    // original list of vars
00096 public:
00097    MKC_knapsack() :
00098       cost(0.0), capacity(0.0), size(0), entries(0),
00099       color_num(0), color_beg(0), orig_index(-1) {}
00100    ~MKC_knapsack() {
00101       delete[] entries;
00102       delete[] color_beg;
00103    }
00104 
00105    void pack(BCP_buffer& buf);
00106    void unpack(BCP_buffer& buf);
00107 };
00108 
00109 //#############################################################################
00110 
00111 class MKC_knapsack_set {
00112 public:
00113   int order_num;         // the number of orders (KS entries)
00114   int ks_num;            // the number of slabs (knapsacks)
00115   MKC_knapsack* ks_list; // the description of the KSs
00116   int orig_var_num;      
00117   char **orig_name_list;
00118   double * orig_row_0;
00119   double * orig_row_1;
00120 public:
00121    MKC_knapsack_set() :
00122       order_num(0), ks_num(0), ks_list(0),
00123       orig_var_num(0), orig_name_list(0), orig_row_0(0), orig_row_1(0) {}
00124    ~MKC_knapsack_set() {
00125       delete[] ks_list;
00126       if (orig_name_list) {
00127          for (int i = 0; i < orig_var_num; ++i)
00128             delete[] orig_name_list[i];
00129          delete[] orig_name_list;
00130       }
00131       delete[] orig_row_0;
00132       delete[] orig_row_1;
00133    }
00134 
00135    void pack(BCP_buffer& buf);
00136    void unpack(BCP_buffer& buf);
00137 };
00138 
00139 #endif

Generated on Thu Jan 15 03:00:58 2009 for coin-Bcp by  doxygen 1.4.7