A new dominance procedure for combinatorial optimization problems

DOI10.1016/0167-6377(88)90025-9MaRDI QIDQ1109683zbMATH OpenOpenAlexFDO

Authors Matteo Fischetti, Paolo Toth

Publication date 1988

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(88)90025-9

zbMATH Keywords

heuristicsbranch and boundmultiple knapsack problemdominance criteria

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Boolean programming (90C09)

Recommendations

• scientific article; zbMATH DE number 5010630
• Dominance rules in combinatorial optimization problems
• Dominance certificates for combinatorial optimization problems
• Domination analysis of combinatorial optimization problems.
• New perspectives of several fundamental problems in combinatorial optimization
• Combinatorial dominance guarantees for heuristic algorithms
• scientific article; zbMATH DE number 2177315
• Paradigms of combinatorial optimization. Problems and new approaches
• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• The new faces of combinatorial optimization

Cites work

• scientific article; zbMATH DE number 3989108 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• Algorithm 632: A program for the 0–1 multiple knapsack problem
• The Fixed Job Schedule Problem with Working-Time Constraints

Cited in

(19)

• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Integrating Symmetry, Dominance, and Bound-and-Bound in a Multiple Knapsack Solver
• scientific article; zbMATH DE number 5010630 (Why is no real title available?)
• Compact representation of near-optimal integer programming solutions
• Binary decision diagrams for generating and storing non-dominated project portfolios with interval-valued project scores
• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• An exact algorithm for the capacitated shortest spanning arborescence
• Exact lexicographic scheduling and approximate rescheduling
• The noising method: A new method for combinatorial optimization
• Combinatorial dominance guarantees for heuristic algorithms
• Automatic generation of dominance breaking nogoods for a class of constraint optimization problems
• Computing near-optimal solutions for the dominating subset with minimal weight problem
• On the exact separation of mixed integer knapsack cuts
• Dominance rules in combinatorial optimization problems
• Pruning moves
• A branch-and-bound algorithm for hard multiple knapsack problems
• A New approach for combining decision procedures for the word problem, and its connection to the Nelson-Oppen combination method
• The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach
• Domain reduction techniques for global NLP and MINLP optimization

Describes a project that uses

Uses Software

• Algorithm 632

This page was built for publication: A new dominance procedure for combinatorial optimization problems

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