Improving branch-and-cut performance by random sampling

DOI10.1007/S12532-015-0096-0MaRDI QIDQ266414zbMATH OpenOpenAlexFDO

Authors Matteo Fischetti, Andrea Lodi, Michele Monaci, Domenico Salvagnin, Andrea Tramontani

Publication date 13 April 2016

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

Full work available at URL https://doi.org/10.1007/s12532-015-0096-0

zbMATH Keywords

integer programmingperformance variability

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Integer programming (90C10) Mixed integer programming (90C11)

Recommendations

• Branch-and-bound solves random binary IPs in poly\((n)\)-time
• Branching rules revisited
• Using diversification, communication and parallelism to solve mixed-integer linear programs
• Improved strategies for branching on general disjunctions
• Exploring the numerics of branch-and-cut for mixed integer linear optimization

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• A distributed processing algorithm for solving integer programs using a cluster of workstations
• Conflict analysis in mixed integer programming
• Exploiting erraticism in search
• Measuring the impact of primal heuristics
• Mixed integer programming computation
• Mixed integer programming: analyzing 12 years of progress
• The feasibility pump
• Using diversification, communication and parallelism to solve mixed-integer linear programs
• Valid inequalities for mixed integer linear programs

Cited in

(15)

• Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining
• A data driven Dantzig-Wolfe decomposition framework
• Generation of feasible integer solutions on a massively parallel computer using the feasibility pump
• Cutting plane selection with analytic centers and multiregression
• Parallelization of the FICO Xpress-Optimizer
• Exact approaches for the knapsack problem with setups
• Exploiting erraticism in search
• On the generation of metric TSP instances with a large integrality gap by branch-and-cut
• Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs
• An exploratory computational analysis of dual degeneracy in mixed-integer programming
• One side cut accelerated random search
• Exploring the numerics of branch-and-cut for mixed integer linear optimization
• Random sampling in cut, flow, and network design problems
• On learning and branching: a survey
• Using diversification, communication and parallelism to solve mixed-integer linear programs

Describes a project that uses

Uses Software

• SCIP
• MIPLIB
• CPLEX
• Gurobi
• FEASPUMP
• XPRESS
• ParaSCIP
• MIPLIB2003

This page was built for publication: Improving branch-and-cut performance by random sampling

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