A new dominance procedure for combinatorial optimization problems

DOI10.1016/0167-6377(88)90025-9zbMATH Open0655.90064OpenAlexW2017548615MaRDI QIDQ1109683FDOQ1109683

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

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

zbMATH Keywords

heuristicsbranch and boundmultiple knapsack problemdominance criteria

Mathematics Subject Classification ID

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

Cites Work

• Algorithm 632: A program for the 0–1 multiple knapsack problem
• Title not available (Why is that?)
• The Fixed Job Schedule Problem with Working-Time Constraints
• Title not available (Why is that?)

Cited In (19)

• Integrating Symmetry, Dominance, and Bound-and-Bound in a Multiple Knapsack Solver
• Title not available (Why is that?)
• 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 New approach for combining decision procedures for the word problem, and its connection to the Nelson-Oppen combination method
• A branch-and-bound algorithm for hard multiple knapsack problems
• The single vehicle routing problem with toll-by-weight scheme: a branch-and-bound approach
• Domain reduction techniques for global NLP and MINLP optimization
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

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)