|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
| // doxy/ or-tools/ src/ algorithms/ |
Classes | |
| class | HungarianOptimizer |
| class | KnapsackBruteForceSolver |
| KnapsackBruteForceSolver KnapsackBruteForceSolver solves the 0-1 knapsack problem when the number of items is less or equal to 30 with brute force, ie. More... | |
| struct | KnapsackItemWithEfficiency |
| KnapsackItemWithEfficiency KnapsackItem is a small struct to pair an item weight with its corresponding profit. More... | |
| class | Knapsack64ItemsSolver |
| Knapsack64ItemsSolver Knapsack64ItemsSolver solves the 0-1 knapsack problem when the number of items is less or equal to 64. More... | |
| class | KnapsackDynamicProgrammingSolver |
| KnapsackDynamicProgrammingSolver KnapsackDynamicProgrammingSolver solves the 0-1 knapsack problem using dynamic programming. More... | |
| class | KnapsackMIPSolver |
| KnapsackMIPSolver. More... | |
| class | KnapsackSolver |
| struct | KnapsackAssignment |
| The following code defines needed classes for the KnapsackGenericSolver class which is the entry point to extend knapsack with new constraints such as conflicts between items. More... | |
| struct | KnapsackItem |
| KnapsackItem KnapsackItem is a small struct to pair an item weight with its corresponding profit. More... | |
| class | KnapsackSearchNode |
| KnapsackSearchNode KnapsackSearchNode is a class used to describe a decision in the decision search tree. More... | |
| class | KnapsackSearchPath |
| KnapsackSearchPath KnapsackSearchPath is a small class used to represent the path between a node to another node in the search tree. More... | |
| class | KnapsackState |
| KnapsackState KnapsackState represents a partial solution to the knapsack problem. More... | |
| class | KnapsackPropagator |
| KnapsackPropagator KnapsackPropagator is the base to model and propagate a constraint given an assignment. More... | |
| class | KnapsackCapacityPropagator |
| KnapsackCapacityPropagator KnapsackCapacityPropagator is a KnapsackPropagator used to enforce a capacity constraint. More... | |
| class | BaseKnapsackSolver |
| BaseKnapsackSolver This the base class for knapsack solvers. More... | |
| class | KnapsackGenericSolver |
| KnapsackGenericSolver KnapsackGenericSolver is the multi-dimensional knapsack solver class. More... | |
Typedefs | |
| typedef std::priority_queue < KnapsackSearchNode *, std::vector < KnapsackSearchNode * > , CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder > | SearchQueue |
| typedef KnapsackItem * | KnapsackItemPtr |
Functions | |
| void | MinimizeLinearAssignment (const std::vector< std::vector< double > > &cost, hash_map< int, int > *direct_assignment, hash_map< int, int > *reverse_assignment) |
| void | MaximizeLinearAssignment (const std::vector< std::vector< double > > &cost, hash_map< int, int > *direct_assignment, hash_map< int, int > *reverse_assignment) |
| bool | WillProductOverflow (int64 value_1, int64 value_2) |
| Returns true when value_1 * value_2 may overflow int64. | |
| int64 | UpperBoundOfRatio (int64 numerator_1, int64 numerator_2, int64 denominator) |
| Returns an upper bound of (numerator_1 * numerator_2) / denominator. | |
| bool | CompareKnapsackItemWithEfficiencyInDecreasingEfficiencyOrder (const KnapsackItemWithEfficiency &item1, const KnapsackItemWithEfficiency &item2) |
| Comparator used to sort item in decreasing efficiency order. | |
Variables | |
| const int | kNoSelection = -1 |
| const int | kMasterPropagatorId = 0 |
| const int | kMaxNumberOfBruteForceItems = 30 |
| const int | kMaxNumberOf64Items = 64 |
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. See: //depot/or-tools/java/com/google/wireless/genie/frontend /mixer/matching/HungarianOptimizer.java
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. See: //depot/or-tools/java/com/google/wireless/genie/frontend /mixer/matching/HungarianOptimizer.java An O(n^4) implementation of the Kuhn-Munkres algorithm (aka the Hungarian algorithm) for solving the assignment problem. The assignment problem takes a set of agents, a set of tasks and a cost associated with assigning each agent to each task and produces an optimal (i.e. least cost) assignment of agents to tasks. The code also enables to compute a maximum assignment by changing the input matrix.
This code is based on (read: translated from) the Java version (read: translated from) the python version at http://www.clapper.org/software/python/munkres/ which in turn is based on http://www.public.iastate.edu/~ddoty/HungarianAlgorithm.html.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Definition at line 230 of file knapsack_solver.h.
typedef std::priority_queue< KnapsackSearchNode*, std::vector<KnapsackSearchNode*>, CompareKnapsackSearchNodePtrInDecreasingUpperBoundOrder> operations_research::SearchQueue [static] |
Definition at line 67 of file knapsack_solver.cc.
| bool operations_research::CompareKnapsackItemWithEfficiencyInDecreasingEfficiencyOrder | ( | const KnapsackItemWithEfficiency & | item1, | |
| const KnapsackItemWithEfficiency & | item2 | |||
| ) |
Comparator used to sort item in decreasing efficiency order.
Definition at line 731 of file knapsack_solver.cc.
| void operations_research::MaximizeLinearAssignment | ( | const std::vector< std::vector< double > > & | cost, | |
| hash_map< int, int > * | direct_assignment, | |||
| hash_map< int, int > * | reverse_assignment | |||
| ) |
Definition at line 683 of file hungarian.cc.
| void operations_research::MinimizeLinearAssignment | ( | const std::vector< std::vector< double > > & | cost, | |
| hash_map< int, int > * | direct_assignment, | |||
| hash_map< int, int > * | reverse_assignment | |||
| ) |
Definition at line 670 of file hungarian.cc.
| int64 operations_research::@2::UpperBoundOfRatio | ( | int64 | numerator_1, | |
| int64 | numerator_2, | |||
| int64 | denominator | |||
| ) | [static] |
Returns an upper bound of (numerator_1 * numerator_2) / denominator.
Definition at line 80 of file knapsack_solver.cc.
| bool operations_research::@2::WillProductOverflow | ( | int64 | value_1, | |
| int64 | value_2 | |||
| ) | [inline, static] |
Returns true when value_1 * value_2 may overflow int64.
Definition at line 70 of file knapsack_solver.cc.
const int operations_research::kMasterPropagatorId = 0 [static] |
Definition at line 30 of file knapsack_solver.cc.
const int operations_research::kMaxNumberOf64Items = 64 [static] |
Definition at line 32 of file knapsack_solver.cc.
const int operations_research::kMaxNumberOfBruteForceItems = 30 [static] |
Definition at line 31 of file knapsack_solver.cc.
const int operations_research::kNoSelection = -1 [static] |
Definition at line 29 of file knapsack_solver.cc.