Information-theoretic approaches to branching in search

DOI10.1016/j.disopt.2010.07.001zbMath1241.90183OpenAlexW2089358540MaRDI QIDQ429675

Andrew Gilpin, Tuomas W. Sandholm

Publication date: 20 June 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.07.001

zbMATH Keywords

branch-and-boundsearchmixed-integer programmingbranching heuristicentropic branching

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Accelerating the branch-and-price algorithm using machine learning ⋮ On learning and branching: a survey ⋮ Mixed-integer programming techniques for the minimum sum-of-squares clustering problem ⋮ Expressive markets for donating to charities ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ Information-based branching schemes for binary linear mixed integer problems ⋮ Improving strong branching by domain propagation ⋮ Unnamed Item

Uses Software

• MIPLIB
• CPLEX
• LINDO
• Concorde
• CABOB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• BOB: Improved winner determination in combinatorial auctions and generalizations
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Branching rules revisited
• Side constraints and non-price attributes in markets
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• CABOB: A Fast Optimal Algorithm for Winner Determination in Combinatorial Auctions
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Generalized best-first search strategies and the optimality of A*
• Backtrack programming techniques
• The Set-Covering Problem: A New Implicit Enumeration Algorithm
• New methods to color the vertices of a graph
• A Computational Study of Search Strategies for Mixed Integer Programming
• Experiments in mixed-integer linear programming
• Principles and Practice of Constraint Programming – CP 2004
• Experimental results on using general disjunctions in branch-and-bound for general-integer linear programming
• Algorithm for optimal winner determination in combinatorial auctions