A branch and bound algorithm for the generalized assignment problem

DOI10.1007/BF01580430zbMath0308.90028MaRDI QIDQ4066849

Richard M. Soland, G. Terry Ross

Publication date: 1975

Published in: Mathematical Programming (Search for Journal in Brave)

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items (95)

Some computational results on real 0-1 knapsack problems ⋮ Lagrangean relaxation. (With comments and rejoinder). ⋮ An integer programming model for the allocation of databases in a distributed computer system ⋮ A study of the bottleneck single source transportation problem ⋮ Preventive maintenance scheduling of power generating units ⋮ Reducing multivalued discrete variables in solving separable task assignment problems ⋮ Optimizing single-terminal dispatch of large volume trips to trucks ⋮ A robust heuristic for the generalized assignment problem ⋮ Efficient algorithms for the capacitated concentrator location problem ⋮ A new Lagrangian relaxation approach to the generalized assignment problem ⋮ A planning and scheduling model for onsertion in printed circuit board assembly ⋮ Master surgery scheduling with consideration of multiple downstream units ⋮ Heuristics for the multi-resource generalized assignment problem ⋮ Elitist genetic algorithm for assignment problem with imprecise goal ⋮ A genetic algorithm for the generalised assignment problem ⋮ Multi-neighborhood local search optimization for machine reassignment problem ⋮ A simple dual algorithm for the generalised assignment problem ⋮ Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches ⋮ A PERCENTILE SEARCH HEURISTIC FOR GENERALIZED ASSIGNMENT PROBLEMS WITH A VERY LARGE NUMBER OF JOBS ⋮ An improved direct descent algorithm for binary knapsack problems ⋮ A branch and efficiency algorithm for the optimal design of supply chain networks ⋮ An LP-based heuristic procedure for the generalized assignment problem with special ordered sets ⋮ The vehicle routing problem with backhauls ⋮ Lagrangian relaxation guided problem space search heuristics for generalized assignment problems ⋮ The bottleneck generalized assignment problem ⋮ A note on exact algorithms for the bottleneck generalized assignment problem ⋮ Tabu search for the multilevel generalized assignment problem ⋮ A three-phase matheuristic algorithm for the multi-day task assignment problem ⋮ Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity ⋮ A multicriteria approach to the location of public facilities ⋮ Two stage decision making approach for Sensor Mission Assignment Problem ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Relaxation techniques applied to some loading problems ⋮ The equilibrium generalized assignment problem and genetic algorithm ⋮ Logic cuts for multilevel generalized assignment problems. ⋮ The generalized assignment problem: Valid inequalities and facets ⋮ Effective algorithm and heuristic for the generalized assignment problem. ⋮ Approximate solutions to large scale capacitated facility location problems ⋮ Surrogate duality relaxation for job shop scheduling ⋮ The design of multiactivity multifacility systems ⋮ Locational analysis ⋮ Goal programming in the context of the assignment problem and a computationally effective solution method ⋮ An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating ⋮ A GRASP heuristic for slab scheduling at continuous casters ⋮ Generalized cover facet inequalities for the generalized assignment problem ⋮ Exchanges procedures for timetabling problems ⋮ On a class of assignment problems. ⋮ Minimization of makespan in generalized assignment problem. ⋮ The \(K\)-coverage concentrator location problem ⋮ An algorithm for storage device selection and file assignment ⋮ Probabilistic analysis of the generalised assignment problem ⋮ Solving large scale generalized assignment problems. --- An aggregation/disaggregation approach ⋮ Overcoming human trafficking via operations research and analytics: opportunities for methods, models, and applications ⋮ A survey of algorithms for the generalized assignment problem ⋮ On the variable-depth-search heuristic for the linear-cost generalized assignment problem ⋮ An exact method with variable fixing for solving the generalized assignment problem ⋮ Project scheduling heuristics-based standard PSO for task-resource assignment in heterogeneous grid ⋮ A genetic algorithm for the project assignment problem ⋮ A new extended formulation of the generalized assignment problem and some associated valid inequalities ⋮ A tabu search heuristic for the generalized assignment problem ⋮ Dynamic generalized assignment problems with stochastic demands and multiple agent-task relationships ⋮ Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique ⋮ Bees algorithm for generalized assignment problem ⋮ A hybrid algorithm for the generalized assignment problem ⋮ A family of inequalities for the generalized assignment polytope ⋮ Modeling of financial supply chain ⋮ A Lagrangean dual-based solution method for a special linear programming problem ⋮ Optimal ABC inventory classification using interval programming ⋮ The 0-1 knapsack problem with multiple choice constraints ⋮ An algorithm for the generalized quadratic assignment problem ⋮ An algorithm and efficient data structures for the binary knapsack problem ⋮ Formulating and solving production planning problems ⋮ An algorithm for the bottleneck generalized assignment problem ⋮ Lagrangean/surrogate relaxation for generalized assignment problems ⋮ Computational comparison on the partitioning strategies in multiple choice integer programming ⋮ Optimization-Based Very Large-Scale Neighborhood Search for Generalized Assignment Problems with Location/Allocation Considerations ⋮ A fuzzy programming approach to multiobjective multidimensional 0-1 knapsack problems ⋮ A class of greedy algorithms for the generalized assignment problem ⋮ An exact method for the two-echelon, single-source, capacitated facility location problem ⋮ Capacity planning by the dynamic multi-resource generalized assignment problem (DMRGAP) ⋮ Efficient cuts in Lagrangean `relax-and-cut' schemes ⋮ Addressing capacity uncertainty in resource-constrained assignment problems ⋮ A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times ⋮ Constructing a course schedule by solving a series of assignment type problems ⋮ Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study ⋮ Solving the generalised assignment problem using polyhedral results ⋮ Approximate and exact algorithms for the fixed-charge knapsack problem ⋮ An ejection chain approach for the generalized assignment problem ⋮ A heuristic lagrangean algorithm for the capacitated plant location problem ⋮ A comparison of techniques for solving the fleet size and mix vehicle routing problem ⋮ Online generalized assignment problem with historical information ⋮ A set partitioning heuristic for the generalized assignment problem ⋮ Microcomputer-based algorithms for large scale shortest path problems ⋮ A new variant of the partitioning shortest path algorithm ⋮ The pure fixed charge transportation problem

Cites Work

• Unnamed Item
• Reduction Algorithm for Zero-One Single Knapsack Problems
• Multicommodity Distribution System Design by Benders Decomposition
• An all Zero-One Algorithm for a Certain Class of Transportation Problems
• A tree-search algorithm for mixed integer programming problems
• An Improved Implicit Enumeration Approach for Integer Programming
• A Branch Search Algorithm for the Knapsack Problem
• An Algorithm for Assigning Uses to Sources in a Special Class of Transportation Problems

This page was built for publication: A branch and bound algorithm for the generalized assignment problem