Branch-and-price for a class of nonconvex mixed-integer nonlinear programs
From MaRDI portal
Publication:2052398
Abstract: This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-and-price. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved.
Recommendations
- On branching rules for convex mixed-integer nonlinear optimization
- Mixed-integer nonlinear optimization
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
- A lagrangean based branch-and-cut algorithm for global optimization of nonconvex mixed-integer nonlinear programs with decomposable structures
- Integrating nonlinear branch-and-bound and outer approximation for convex mixed integer nonlinear programming
Cites work
- 50 Years of Integer Programming 1958-2008
- \(\alpha BB\): A global optimization method for general constrained nonconvex problems
- A branch-and-cut method for 0-1 mixed convex programming
- A branch-and-reduce approach to global optimization
- A Column Generation Approach to the Urban Transit Crew Scheduling Problem
- A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables
- A Linear Programming Approach to the Cutting-Stock Problem
- A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
- A scalable global optimization algorithm for stochastic nonlinear programs
- Accelerating strategies in column generation methods for vehicle routing and crew scheduling problems
- Algorithms and Software for Convex Mixed Integer Nonlinear Programs
- An outer-approximation algorithm for a class of mixed-integer nonlinear programs
- ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
- Branch and Bound Experiments in Convex Nonlinear Integer Programming
- Branch-and-price: Column generation for solving huge integer programs
- Branching and bounds tighteningtechniques for non-convex MINLP
- Capacity planning with congestion effects
- Column enumeration based decomposition techniques for a class of non-convex MINLP problems
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Computing in operations research using Julia
- Dantzig-Wolfe decomposition for solving multistage stochastic capacity-planning problems
- Decomposition Principle for Linear Programs
- Decomposition-based inner- and outer-refinement algorithms for global optimization
- Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON
- Fleet assignment and routing with schedule synchronization constraints
- Generalized Benders decomposition
- Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO
- Global optimization algorithm for capacitated multi-facility continuous location-allocation problems
- Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- Lagrangean relaxation. (With comments and rejoinder).
- Nonconvex generalized Benders decomposition for stochastic separable mixed-integer nonlinear programs
- On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
- Outline of an algorithm for integer solutions to linear programs
- Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues
- Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems
- Review of nonlinear mixed-integer and disjunctive programming techniques
- Routing with time windows by column generation
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
- Selected Topics in Column Generation
- Solution of a Large-Scale Traveling-Salesman Problem
- Solving mixed integer nonlinear programs by outer approximation
- The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming
- The global solver in the LINDO API
- The operational airline crew scheduling problem
Cited in
(4)
This page was built for publication: Branch-and-price for a class of nonconvex mixed-integer nonlinear programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052398)
