Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
// doxy/ or-tools/ src/ algorithms/ |
00001 // Copyright 2010-2012 Google 00002 // Licensed under the Apache License, Version 2.0 (the "License"); 00003 // you may not use this file except in compliance with the License. 00004 // You may obtain a copy of the License at 00005 // 00006 // http://www.apache.org/licenses/LICENSE-2.0 00007 // 00008 // Unless required by applicable law or agreed to in writing, software 00009 // distributed under the License is distributed on an "AS IS" BASIS, 00010 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00011 // See the License for the specific language governing permissions and 00012 // limitations under the License. 00013 // 00014 // The aim is to provide a basis for solving knapsack problems: 00015 // - 0-1 knapsack problem, 00016 // - Multi-dimensional knapsack problem, 00017 // - TODO(user) Multi-dimensional knapsack problem with n-ary conflicts 00018 // between items. 00019 // 00020 // Given n items, each with a profit and a weight, given a knapsack of 00021 // capacity c, the goal is to find a subset of items which fits inside c 00022 // and maximizes the total profit. 00023 // The knapsack problem can easily be extended from 1 to d dimensions. 00024 // As an example, this can be useful to constrain the maximum number of 00025 // items inside the knapsack. 00026 // Without loss of generality, profits and weights are assumed to be positive. 00027 // 00028 // From a mathematical point of view, the multi-dimensional knapsack problem 00029 // can be modeled by d linear constraints: 00030 // ForEach(j:1..d)(Sum(i:1..n)(weight_ij * item_i) <= c_j 00031 // where item_i is a 0-1 integer variable. 00032 // Then the goal is to maximize: Sum(i:1..n)(profit_i * item_i). 00033 // 00034 // There are several ways to solve knapsack problems. One of the most 00035 // efficient ways is based on dynamic programming (mainly when weights, profits 00036 // and dimensions are small, the algorithm runs in pseudo polynomial time). 00037 // Unfortunately when adding conflict constraints the problem becomes strongly 00038 // NP-hard, i.e. there is no pseudo-polynomial algorithm to solve it. 00039 // That's the reason why the most of the following code is based on branch and 00040 // bound search. 00041 // 00042 // For instance to solve a 2-dimension knapsack problem with 9 items, 00043 // one just has to feed a profit vector with the 9 profits, a vector of 2 00044 // vectors for weights, and a vector of capacities. 00045 // E.g.: 00046 // vector: profits = [1, 2, 3, 4, 5, 6, 7, 8, 9] 00047 // vector of vector: weights = [ [1, 2, 3, 4, 5, 6, 7, 8, 9], 00048 // [1, 1, 1, 1, 1, 1, 1, 1, 1]] 00049 // vector: capacities = [34, 4] 00050 // And then: 00051 // KnapsackSolver solver(KnapsackSolver::KNAPSACK_MULTIDIMENSION_SOLVER, 00052 // "Multi-dimensional solver"); 00053 // solver.Init(profits, weights, capacities); 00054 // int64 profit = solver.Solve(); 00055 00056 00057 #ifndef OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_ 00058 #define OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_ 00059 00060 #include <math.h> 00061 #include <string> 00062 #include <vector> 00063 00064 #include "base/basictypes.h" 00065 #include "base/integral_types.h" 00066 #include "base/logging.h" 00067 #include "base/macros.h" 00068 #include "base/scoped_ptr.h" 00069 00070 using std::string; 00071 00072 namespace operations_research { 00073 00074 // ----- KnapsackSolver ----- 00075 // KnapsackSolver is a factory for knapsack solvers. Several solvers are 00076 // implemented, some can deal with a limited number of items, some can deal with 00077 // several dimensions... 00078 // Currently 4 algorithms are implemented: 00079 // - KNAPSACK_BRUTE_FORCE_SOLVER: Limited to 30 items and one dimension, this 00080 // solver uses a brute force algorithm, ie. explores all possible states. 00081 // Experiments show competitive performance for instances with less than 00082 // 15 items. 00083 // - KNAPSACK_64ITEMS_SOLVER: Limited to 64 items and one dimension, this 00084 // solver uses a branch & bound algorithm. This solver is about 4 times 00085 // faster than KNAPSACK_MULTIDIMENSION_SOLVER. 00086 // - KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER: Limited to one dimension, this solver 00087 // is based on a dynamic programming algorithm. The time and space 00088 // complexity is O(capacity * number_of_items). 00089 // - KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER: This solver can deal 00090 // with both large number of items and several dimensions. This solver is 00091 // based on branch and bound. 00092 // - KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER: This solver can deal with both 00093 // large number of items and several dimensions. This solver is based on 00094 // Integer Programming solver CBC. 00095 // - KNAPSACK_MULTIDIMENSION_GLPK_MIP_SOLVER: This solver can deal with both 00096 // large number of items and several dimensions. This solver is based on 00097 // Integer Programming solver GLPK. 00098 // 00099 // KnapsackSolver also implements a problem reduction algorithm based on lower 00100 // and upper bounds (see Ingargolia and Korsh - A reduction algorithm for 00101 // zero-one single knapsack problems. Management Science 1973). This reduction 00102 // method is preferred to better algorithms (see for instance Martello and Toth 00103 // - A new algorithm for the 0-1 knapsack problem. Management Science 1988), 00104 // because it remains valid with more complex problems, eg. multi-dimensional, 00105 // conflicts... 00106 // The main idea is to compute lower and upper bounds for each item in or out 00107 // of the knapsack; if the best lower bound is strictly greater than the upper 00108 // bound when an item is in, then this item is surely not in the optimal 00109 // solution. 00110 class BaseKnapsackSolver; 00111 00112 class KnapsackSolver { 00113 public: 00114 enum SolverType { 00115 KNAPSACK_BRUTE_FORCE_SOLVER, 00116 KNAPSACK_64ITEMS_SOLVER, 00117 KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER, 00118 #if defined(USE_CBC) 00119 KNAPSACK_MULTIDIMENSION_CBC_MIP_SOLVER, 00120 #endif // USE_CBC 00121 #if defined(USE_GLPK) 00122 KNAPSACK_MULTIDIMENSION_GLPK_MIP_SOLVER, 00123 #endif // USE_GLPK 00124 KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER 00125 }; 00126 00127 explicit KnapsackSolver(const string& solver_name); 00128 KnapsackSolver(SolverType solver_type, const string& solver_name); 00129 virtual ~KnapsackSolver(); 00130 00131 // Initializes the solver and enters the problem to be solved. 00132 void Init(const std::vector<int64>& profits, 00133 const std::vector<std::vector<int64> >& weights, 00134 const std::vector<int64>& capacities); 00135 00136 // Solves the problem and returns the profit of the optimal solution. 00137 int64 Solve(); 00138 00139 // Returns true if the item 'item_id' is packed in the optimal knapsack. 00140 bool BestSolutionContains(int item_id) const; 00141 string GetName() const; 00142 00143 bool use_reduction() const { return use_reduction_; } 00144 void set_use_reduction(bool use_reduction) { use_reduction_ = use_reduction; } 00145 00146 private: 00147 int ReduceProblem(int num_items); 00148 void ComputeAdditionalProfit(const std::vector<int64>& profits); 00149 void InitReducedProblem(const std::vector<int64>& profits, 00150 const std::vector<std::vector<int64> >& weights, 00151 const std::vector<int64>& capacities); 00152 00153 scoped_ptr<BaseKnapsackSolver> solver_; 00154 std::vector<bool> known_value_; 00155 std::vector<bool> best_solution_; 00156 std::vector<int> mapping_reduced_item_id_; 00157 bool is_problem_solved_; 00158 int64 additional_profit_; 00159 bool use_reduction_; 00160 00161 DISALLOW_COPY_AND_ASSIGN(KnapsackSolver); 00162 }; 00163 00164 #if !defined(SWIG) 00165 // The following code defines needed classes for the KnapsackGenericSolver 00166 // class which is the entry point to extend knapsack with new constraints such 00167 // as conflicts between items. 00168 // 00169 // Constraints are enforced using KnapsackPropagator objects, in the current 00170 // code there is one propagator per dimension (KnapsackCapacityPropagator). 00171 // One of those propagators, named master propagator, is used to guide the 00172 // search, i.e. decides which item should be assigned next. 00173 // Roughly speaking the search algorithm is: 00174 // - While not optimal 00175 // - Select next search node to expand 00176 // - Select next item_i to assign (using master propagator) 00177 // - Generate a new search node where item_i is in the knapsack 00178 // - Check validity of this new partial solution (using propagators) 00179 // - If valid, add this new search node to the search 00180 // - Generate a new search node where item_i is not in the knapsack 00181 // - Check validity of this new partial solution (using propagators) 00182 // - If valid, add this new search node to the search 00183 // 00184 // TODO(user): Add a new propagator class for conflict constraint. 00185 // TODO(user): Add a new propagator class used as a guide when the problem has 00186 // several dimensions. 00187 00188 // ----- KnapsackAssignement ----- 00189 // KnapsackAssignement is a small struct used to pair an item with its 00190 // assignment. It is mainly used for search nodes and updates. 00191 struct KnapsackAssignment { 00192 KnapsackAssignment(int _item_id, bool _is_in) 00193 : item_id(_item_id), 00194 is_in(_is_in) { 00195 } 00196 int item_id; 00197 bool is_in; 00198 }; 00199 00200 // ----- KnapsackItem ----- 00201 // KnapsackItem is a small struct to pair an item weight with its 00202 // corresponding profit. 00203 // The aim of the knapsack problem is to pack as many valuable items as 00204 // possible. A straight forward heuristic is to take those with the greatest 00205 // profit-per-unit-weight. This ratio is called efficiency in this 00206 // implementation. So items will be grouped in vectors, and sorted by 00207 // decreasing efficiency. 00208 // Note that profits are duplicated for each dimension. This is done to 00209 // simplify the code, especially the GetEfficiency method and vector sorting. 00210 // As there usually are only few dimensions, the overhead should not be an 00211 // issue. 00212 struct KnapsackItem { 00213 KnapsackItem(int _id, int64 _weight, int64 _profit) 00214 : id(_id), 00215 weight(_weight), 00216 profit(_profit) { 00217 } 00218 double GetEfficiency(int64 profit_max) const { 00219 return (weight > 0) ? 00220 static_cast<double>(profit) / static_cast<double>(weight) : 00221 static_cast<double>(profit_max); 00222 } 00223 00224 // The 'id' field is used to retrieve the initial item in order to 00225 // communicate with other propagators and state. 00226 const int id; 00227 const int64 weight; 00228 const int64 profit; 00229 }; 00230 typedef KnapsackItem* KnapsackItemPtr; 00231 00232 // ----- KnapsackSearchNode ----- 00233 // KnapsackSearchNode is a class used to describe a decision in the decision 00234 // search tree. 00235 // The node is defined by a pointer to the parent search node and an 00236 // assignment (see KnapsackAssignement). 00237 // As the current state is not explicitly stored in a search node, one should 00238 // go through the search tree to incrementally build a partial solution from 00239 // a previous search node. 00240 class KnapsackSearchNode { 00241 public: 00242 KnapsackSearchNode(const KnapsackSearchNode* const parent, 00243 const KnapsackAssignment& assignment); 00244 int depth() const { return depth_; } 00245 const KnapsackSearchNode* const parent() const { return parent_; } 00246 const KnapsackAssignment& assignment() const { return assignment_; } 00247 00248 int64 current_profit() const { return current_profit_; } 00249 void set_current_profit(int64 profit) { current_profit_ = profit; } 00250 00251 int64 profit_upper_bound() const { return profit_upper_bound_; } 00252 void set_profit_upper_bound(int64 profit) { profit_upper_bound_ = profit; } 00253 00254 int next_item_id() const { return next_item_id_; } 00255 void set_next_item_id(int id) { next_item_id_ = id; } 00256 00257 private: 00258 // 'depth' field is used to navigate efficiently through the search tree 00259 // (see KnapsackSearchPath). 00260 int depth_; 00261 const KnapsackSearchNode* const parent_; 00262 KnapsackAssignment assignment_; 00263 00264 // 'current_profit' and 'profit_upper_bound' fields are used to sort search 00265 // nodes using a priority queue. That allows to pop the node with the best 00266 // upper bound, and more importantly to stop the search when optimality is 00267 // proved. 00268 int64 current_profit_; 00269 int64 profit_upper_bound_; 00270 00271 // 'next_item_id' field allows to avoid an O(number_of_items) scan to find 00272 // next item to select. This is done for free by the upper bound computation. 00273 int next_item_id_; 00274 00275 DISALLOW_COPY_AND_ASSIGN(KnapsackSearchNode); 00276 }; 00277 00278 // ----- KnapsackSearchPath ----- 00279 // KnapsackSearchPath is a small class used to represent the path between a 00280 // node to another node in the search tree. 00281 // As the solution state is not stored for each search node, the state should 00282 // be rebuilt at each node. One simple solution is to apply all decisions 00283 // between the node 'to' and the root. This can be computed in 00284 // O(number_of_items). 00285 // However it is possible to achieve better average complexity. Two 00286 // consecutively explored nodes are usually close enough (ie. much less than 00287 // number_of_items) to benefit from an incremental update from the node 00288 // 'from' to the node 'to'. 00289 // 'via' field is the common parent of 'from' field and 'to' field. 00290 // So the state can be built by reverting all decisions from 'from' to 'via' 00291 // and applying all decisions from 'via' to 'to'. 00292 class KnapsackSearchPath { 00293 public: 00294 KnapsackSearchPath(const KnapsackSearchNode& from, 00295 const KnapsackSearchNode& to); 00296 void Init(); 00297 const KnapsackSearchNode& from() const { return from_; } 00298 const KnapsackSearchNode& via() const { return *via_; } 00299 const KnapsackSearchNode& to() const { return to_; } 00300 const KnapsackSearchNode* MoveUpToDepth(const KnapsackSearchNode& node, 00301 int depth) const; 00302 private: 00303 const KnapsackSearchNode& from_; 00304 const KnapsackSearchNode* via_; // Computed in 'Init'. 00305 const KnapsackSearchNode& to_; 00306 00307 DISALLOW_COPY_AND_ASSIGN(KnapsackSearchPath); 00308 }; 00309 00310 // ----- KnapsackState ----- 00311 // KnapsackState represents a partial solution to the knapsack problem. 00312 class KnapsackState { 00313 public: 00314 KnapsackState(); 00315 00316 // Initializes vectors with number_of_items set to false (i.e. not bound yet). 00317 void Init(int number_of_items); 00318 // Updates the state by applying or reverting a decision. 00319 // Returns false if fails, i.e. trying to apply an inconsistent decision 00320 // to an already assigned item. 00321 bool UpdateState(bool revert, const KnapsackAssignment& assignment); 00322 00323 int GetNumberOfItems() const { return is_bound_.size(); } 00324 bool is_bound(int id) const { return is_bound_.at(id); } 00325 bool is_in(int id) const { return is_in_.at(id); } 00326 00327 private: 00328 // Vectors 'is_bound_' and 'is_in_' contain a boolean value for each item. 00329 // 'is_bound_(item_i)' is false when there is no decision for item_i yet. 00330 // When item_i is bound, 'is_in_(item_i)' represents the presence (true) or 00331 // the absence (false) of item_i in the current solution. 00332 std::vector<bool> is_bound_; 00333 std::vector<bool> is_in_; 00334 00335 DISALLOW_COPY_AND_ASSIGN(KnapsackState); 00336 }; 00337 00338 // ----- KnapsackPropagator ----- 00339 // KnapsackPropagator is the base to model and propagate a constraint given 00340 // an assignment. 00341 // When some work has to be done both by the base and the derived class, 00342 // a protected pure virtual method ending by 'Propagator' is defined. 00343 // For instance 'Init' creates a vector of items, and then calls 00344 // 'InitPropagator' to let the derived class to do its own initialization. 00345 class KnapsackPropagator { 00346 public: 00347 explicit KnapsackPropagator(const KnapsackState& state); 00348 virtual ~KnapsackPropagator(); 00349 00350 // Initializes data structure and then calls InitPropagator. 00351 void Init(const std::vector<int64>& profits, 00352 const std::vector<int64>& weights); 00353 00354 // Updates data structure and then calls UpdatePropagator. 00355 // Returns false when failure. 00356 bool Update(bool revert, const KnapsackAssignment& assignment); 00357 // ComputeProfitBounds should set 'profit_lower_bound_' and 00358 // 'profit_upper_bound_' which are constraint specific. 00359 virtual void ComputeProfitBounds() = 0; 00360 // Returns the id of next item to assign. 00361 // Returns kNoSelection when all items are bound. 00362 virtual int GetNextItemId() const = 0; 00363 00364 int64 current_profit() const { return current_profit_; } 00365 int64 profit_lower_bound() const { return profit_lower_bound_; } 00366 int64 profit_upper_bound() const { return profit_upper_bound_; } 00367 00368 // Copies the current state into 'solution'. 00369 // All unbound items are set to false (i.e. not in the knapsack). 00370 // When 'has_one_propagator' is true, CopyCurrentSolutionPropagator is called 00371 // to have a better solution. When there is only one propagator 00372 // there is no need to check the solution with other propagators, so the 00373 // partial solution can be smartly completed. 00374 void CopyCurrentStateToSolution(bool has_one_propagator, 00375 std::vector<bool>* solution) const; 00376 00377 protected: 00378 // Initializes data structure. This method is called after initialization 00379 // of KnapsackPropagator data structure. 00380 virtual void InitPropagator() = 0; 00381 00382 // Updates internal data structure incrementally. This method is called 00383 // after update of KnapsackPropagator data structure. 00384 virtual bool UpdatePropagator(bool revert, 00385 const KnapsackAssignment& assignment) = 0; 00386 00387 // Copies the current state into 'solution'. 00388 // Only unbound items have to be copied as CopyCurrentSolution was already 00389 // called with current state. 00390 // This method is useful when a propagator is able to find a better solution 00391 // than the blind instantiation to false of unbound items. 00392 virtual void CopyCurrentStateToSolutionPropagator( 00393 std::vector<bool>* solution) const = 0; 00394 00395 const KnapsackState& state() const { return state_; } 00396 const std::vector<KnapsackItemPtr>& items() const { return items_; } 00397 00398 void set_profit_lower_bound(int64 profit) { profit_lower_bound_ = profit; } 00399 void set_profit_upper_bound(int64 profit) { profit_upper_bound_ = profit; } 00400 00401 private: 00402 std::vector<KnapsackItemPtr> items_; 00403 int64 current_profit_; 00404 int64 profit_lower_bound_; 00405 int64 profit_upper_bound_; 00406 const KnapsackState& state_; 00407 00408 DISALLOW_COPY_AND_ASSIGN(KnapsackPropagator); 00409 }; 00410 00411 // ----- KnapsackCapacityPropagator ----- 00412 // KnapsackCapacityPropagator is a KnapsackPropagator used to enforce 00413 // a capacity constraint. 00414 // As a KnapsackPropagator is supposed to compute profit lower and upper 00415 // bounds, and get the next item to select, it can be seen as a 0-1 Knapsack 00416 // solver. The most efficient way to compute upper bound is to iterate on 00417 // items in profit-per-unit-weight decreasing order. The break item is 00418 // commonly defined as the first item for which there is not enough remaining 00419 // capacity. Selecting this break item as the next-item-to-assign usually 00420 // gives the best results (see Greenbreg & Hegerich). 00421 // This is exactly what is implemented in this class. 00422 // When there is only one propagator, it is possible to compute a better 00423 // profit lower bound almost for free. During the scan to find the 00424 // break element all unbound items are added just as if they were part of 00425 // the current solution. This is used both in ComputeProfitBounds and 00426 // CopyCurrentSolutionPropagator. 00427 // For incrementality reasons, the ith item should be accessible in O(1). That's 00428 // the reason why item vector has to be duplicated 'sorted_items_'. 00429 class KnapsackCapacityPropagator : public KnapsackPropagator { 00430 public: 00431 KnapsackCapacityPropagator(const KnapsackState& state, int64 capacity); 00432 virtual ~KnapsackCapacityPropagator(); 00433 virtual void ComputeProfitBounds(); 00434 virtual int GetNextItemId() const { return break_item_id_; } 00435 00436 protected: 00437 // Initializes KnapsackCapacityPropagator (eg. sort items in decreasing 00438 // order). 00439 virtual void InitPropagator(); 00440 // Updates internal data structure incrementally (ie. 'consumed_capacity_') 00441 // to avoid a O(number_of_items) scan. 00442 virtual bool UpdatePropagator(bool revert, 00443 const KnapsackAssignment& assignment); 00444 virtual void CopyCurrentStateToSolutionPropagator( 00445 std::vector<bool>* solution) const; 00446 00447 private: 00448 // An obvious additional profit upper bound corresponds to the linear 00449 // relaxation: remaining_capacity * efficiency of the break item. 00450 // It is possible to do better in O(1), using Martello-Toth bound U2. 00451 // The main idea is to enforce integrality constraint on the break item, 00452 // ie. either the break item is part of the solution, either it is not. 00453 // So basically the linear relaxation is done on the item before the break 00454 // item, or the one after the break item. 00455 // This is what GetAdditionalProfit method implements. 00456 int64 GetAdditionalProfit(int64 remaining_capacity, int break_item_id) const; 00457 00458 const int64 capacity_; 00459 int64 consumed_capacity_; 00460 int break_item_id_; 00461 std::vector<KnapsackItemPtr> sorted_items_; 00462 int64 profit_max_; 00463 00464 DISALLOW_COPY_AND_ASSIGN(KnapsackCapacityPropagator); 00465 }; 00466 00467 // ----- BaseKnapsackSolver ----- 00468 // This the base class for knapsack solvers. 00469 class BaseKnapsackSolver { 00470 public: 00471 explicit BaseKnapsackSolver(const string& solver_name) 00472 : solver_name_(solver_name) {} 00473 virtual ~BaseKnapsackSolver() {} 00474 00475 // Initializes the solver and enters the problem to be solved. 00476 virtual void Init(const std::vector<int64>& profits, 00477 const std::vector<std::vector<int64> >& weights, 00478 const std::vector<int64>& capacities) = 0; 00479 00480 // Gets the lower and upper bound when the item is in or out of the knapsack. 00481 // To ensure objects are correctly initialized, this method should not be 00482 // called before ::Init. 00483 virtual void GetLowerAndUpperBoundWhenItem(int item_id, 00484 bool is_item_in, 00485 int64* lower_bound, 00486 int64* upper_bound); 00487 00488 // Solves the problem and returns the profit of the optimal solution. 00489 virtual int64 Solve() = 0; 00490 00491 // Returns true if the item 'item_id' is packed in the optimal knapsack. 00492 virtual bool best_solution(int item_id) const = 0; 00493 00494 virtual string GetName() const { return solver_name_; } 00495 00496 private: 00497 const string solver_name_; 00498 }; 00499 00500 // ----- KnapsackGenericSolver ----- 00501 // KnapsackGenericSolver is the multi-dimensional knapsack solver class. 00502 // In the current implementation, the next item to assign is given by the 00503 // master propagator. Using SetMasterPropagator allows to change the default 00504 // (propagator of the first dimension), and select another dimension when 00505 // more constrained. 00506 // TODO(user): In case of multi-dimensional knapsack problem, implement an 00507 // aggregated propagator to combine all dimensions and give a better guide 00508 // to select next item (see for instance Dobson's aggregated efficiency). 00509 class KnapsackGenericSolver : public BaseKnapsackSolver { 00510 public: 00511 explicit KnapsackGenericSolver(const string& solver_name); 00512 virtual ~KnapsackGenericSolver(); 00513 00514 // Initializes the solver and enters the problem to be solved. 00515 virtual void Init(const std::vector<int64>& profits, 00516 const std::vector<std::vector<int64> >& weights, 00517 const std::vector<int64>& capacities); 00518 int GetNumberOfItems() const { return state_.GetNumberOfItems(); } 00519 void GetLowerAndUpperBoundWhenItem(int item_id, 00520 bool is_item_in, 00521 int64* lower_bound, 00522 int64* upper_bound); 00523 00524 // Sets which propagator should be used to guide the search. 00525 // 'master_propagator_id' should be in 0..p-1 with p the number of 00526 // propagators. 00527 void set_master_propagator_id(int master_propagator_id) { 00528 master_propagator_id_ = master_propagator_id; 00529 } 00530 00531 // Solves the problem and returns the profit of the optimal solution. 00532 virtual int64 Solve(); 00533 // Returns true if the item 'item_id' is packed in the optimal knapsack. 00534 virtual bool best_solution(int item_id) const { 00535 return best_solution_.at(item_id); 00536 } 00537 00538 private: 00539 // Clears internal data structure. 00540 void Clear(); 00541 00542 // Updates all propagators reverting/applying all decision on the path. 00543 // Returns true if fails. Note that, even if fails, all propagators should 00544 // be updated to be in a stable state in order to stay incremental. 00545 bool UpdatePropagators(const KnapsackSearchPath& path); 00546 // Updates all propagators reverting/applying one decision. 00547 // Return true if fails. Note that, even if fails, all propagators should 00548 // be updated to be in a stable state in order to stay incremental. 00549 bool IncrementalUpdate(bool revert, const KnapsackAssignment& assignment); 00550 // Updates the best solution if the current solution has a better profit. 00551 void UpdateBestSolution(); 00552 00553 // Returns true if new relevant search node was added to the nodes array, that 00554 // means this node should be added to the search queue too. 00555 bool MakeNewNode(const KnapsackSearchNode& node, bool is_in); 00556 00557 // Gets the aggregated (min) profit upper bound among all propagators. 00558 int64 GetAggregatedProfitUpperBound() const; 00559 bool HasOnePropagator() const { return propagators_.size() == 1; } 00560 int64 GetCurrentProfit() const { 00561 return propagators_.at(master_propagator_id_)->current_profit(); 00562 } 00563 int64 GetNextItemId() const { 00564 return propagators_.at(master_propagator_id_)->GetNextItemId(); 00565 } 00566 00567 std::vector<KnapsackPropagator*> propagators_; 00568 int master_propagator_id_; 00569 std::vector<KnapsackSearchNode*> search_nodes_; 00570 KnapsackState state_; 00571 int64 best_solution_profit_; 00572 std::vector<bool> best_solution_; 00573 00574 DISALLOW_COPY_AND_ASSIGN(KnapsackGenericSolver); 00575 }; 00576 #endif // SWIG 00577 } // namespace operations_research 00578 00579 #endif // OR_TOOLS_ALGORITHMS_KNAPSACK_SOLVER_H_