A new modeling and solution approach for the number partitioning problem

DOI10.1155/JAMDS.2005.113MaRDI QIDQ930774zbMATH OpenFDO

Authors Bahram Alidaee, Fred Glover, Gary A. Kochenberger, César Rego

Publication date 1 July 2008

Published in Journal of Applied Mathematics and Decision Sciences (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/130728

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: The number partitioning problem has proven to be a challenging problem for both exact and heuristic solution methods. We present a new modeling and solution approach that consists of recasting the problem as an unconstrained quadratic binary program that can be solved by efficient metaheuristic methods. Our approach readily accommodates both the common two-subset partition case as well as the more general case of multiple subsets. Preliminary computational experience is presented illustrating the attractiveness of the method.

Recommendations

• Heuristics and exact methods for number partitioning
• A mixed-integer linear programming model to solve the multidimensional multi-way number partitioning problem
• A new modeling and solution approach for the set-partitioning problem
• Simple tabu search algorithm for the number partitioning problem
• Integer linear programming model for multidimensional two-way number partitioning problem

Cited in

(15)

• Heuristics and exact methods for number partitioning
• A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria
• A two-phase method for multidimensional number partitioning problem
• A mixed-integer linear programming model to solve the multidimensional multi-way number partitioning problem
• An algebraic expression of the number partitioning problem
• Building an iterative heuristic solver for a quantum annealer
• A new modeling and solution approach for the set-partitioning problem
• An effective modeling and solution approach for the generalized independent set problem
• QUBO formulations of the longest path problem
• Simple tabu search algorithm for the number partitioning problem
• The unconstrained binary quadratic programming problem: a survey
• A new approach to solve open-partition problems
• Integer linear programming model for multidimensional two-way number partitioning problem
• Partially ordered sets corresponding to the partition problem
• Solving the maximum edge weight clique problem via unconstrained quadratic programming

This page was built for publication: A new modeling and solution approach for the number partitioning problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930774)