Active-constraint variable ordering for faster feasibility of mixed integer linear programs

DOI10.1007/S10107-006-0009-0zbMath1205.90207OpenAlexW2068133968MaRDI QIDQ985305

Jagat Patel, John W. Chinneck

Publication date: 21 July 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0009-0

zbMATH Keywords

branching variable selectionMIP solver

Mathematics Subject Classification ID

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

Related Items (14)

DASH: dynamic approach for switching heuristics ⋮ Achieving MILP feasibility quickly using general disjunctions ⋮ Inequalities and Target Objectives for Metaheuristic Search – Part I: Mixed Binary Optimization ⋮ Faster integer-feasibility in mixed-integer linear programs by branching to force change ⋮ Branching on nonchimerical fractionalities ⋮ Solution Counting Algorithms for Constraint-Centered Search Heuristics ⋮ Zero duality gap in surrogate constraint optimization: a concise review of models ⋮ Information-based branching schemes for binary linear mixed integer problems ⋮ A computational study of parametric tabu search for 0-1 mixed integer programs ⋮ Minimal infeasible constraint sets in convex integer programs ⋮ Faster MIP solutions via new node selection rules ⋮ Solution counting algorithms for constraint-centered search heuristics ⋮ Improving strong branching by domain propagation ⋮ The feasibility pump

Uses Software

• MIPLIB
• CPLEX
• Benchmarks for Optimization Software
• FEASPUMP
• MIPLIB2003
• Octane

Cites Work

• Unnamed Item
• Tutorial on surrogate constraint approaches for optimization in graphs
• Exploring relaxation induced neighborhoods to improve MIP solutions
• Pivot and shift -- a mixed integer programming heuristic
• The feasibility pump
• An Automatic Method of Solving Discrete Programming Problems
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Octane: A New Heuristic for Pure 0–1 Programs
• Practical Solution of Large Mixed Integer Programming Problems with Umpire
• Experiments in mixed-integer linear programming using pseudo-costs
• Parallel Branch-and-Bound Algorithms for General Mixed Integer Programming on the CM-5
• Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
• Analyzing Infeasible Mixed-Integer and Integer Linear Programs
• A Computational Study of Search Strategies for Mixed Integer Programming
• A tree-search algorithm for mixed integer programming problems
• Surrogate Constraints
• Technical Note—An Improved Branch-and-Bound Method for Integer Programming
• Experiments in mixed-integer linear programming
• Investigation of some branch and bound strategies for the solution of mixed integer linear programs
• Benchmarking optimization software with performance profiles.

This page was built for publication: Active-constraint variable ordering for faster feasibility of mixed integer linear programs