branch-and-cut – Page 3 – Optimization Online

Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality

Published: 2020/06/05, Updated: 2020/09/16

Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch- and-cut has proven to be a powerful extension … Read more

A Unified Framework for Multistage and Multilevel Mixed Integer Linear Optimization

Published: 2020/04/16, Updated: 2020/08/02

(Mixed) Integer Linear Programming, Game Theory, Stochastic Programming branch-and-cut, decomposition, duality, integer programming, multiobjective optimization, multistage optimization with recourse

We introduce a unified framework for the study of multilevel mixed integer linear optimization problems and multistage stochastic mixed integer linear optimization problems with recourse. The framework highlights the common mathematical structure of the two problems and allows for the development of a common algorithmic framework. Focusing on the two-stage case, we investigate, in particular, … Read more

Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

Published: 2020/04/02, Updated: 2022/07/09

Stefano Coniglio

Fabio Furini

Ivana Ljubić

Cutting Plane Approaches, Integer Programming, Nonlinear Optimization benders decomposition, branch-and-cut, submodular maximization

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function … Read more

The SCIP Optimization Suite 7.0

Published: 2020/03/30

Matthias Miltenberger

(Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming benders decomposition, branch-and-cut, branch-and-price, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization, presolving, steiner tree optimization, tree size estimation

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

Computational study of a branching algorithm for the maximum k-cut problem

Published: 2020/02/13

Miguel F. Anjos

Sébastien Le Digabel

Vilmar Jefté Rodrigues de Sousa

Branch and Cut Algorithms, Graphs and Matroids, Semi-definite Programming branch-and-cut, eigenvalue constraint, graph partitioning, maximum k-cut, semidefinite programming

This work considers the graph partitioning problem known as maximum k-cut. It focuses on investigating features of a branch-and-bound method to efficiently obtain global solutions. An exhaustive experimental study is carried out for two main components of a branch-and-bound algorithm: computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood … Read more

Compact Formulations for Split Delivery Routing Problems

Published: 2019/12/01, Updated: 2021/10/15

Pedro Munari

Martin Savelsbergh

Branch and Cut Algorithms, Production and Logistics, Transportation branch-and-cut, Compact models, split-delivery, vehicle routing

Split delivery routing problems are concerned with serving the demand of a set of customers with a fleet of capacitated vehicles at minimum cost, where a customer can be served by more than one vehicle if beneficial. They generalize traditional variants of routing problems and have applications in commercial as well as humanitarian logistics. Previously, … Read more

Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework

Published: 2019/09/24, Updated: 2019/09/25

Stephen J. Maher

Integer Programming, Optimization Software and Modeling Systems benders decomposition, branch-and-cut, constraint integer programming, mixed-integer programming, optimisation software

Benders’ decomposition is a popular mathematical and constraint programming algorithm that is widely applied to exploit problem structure arising from real-world applications. While useful for exploiting structure in mathematical and constraint programs, the use of Benders’ decomposition typically requires significant implementation effort to achieve an effective solution algorithm. Traditionally, Benders’ decomposition has been viewed as … Read more

Hub Location and Route Dimensioning: Strategic and Tactical Intermodal Transportation Hub Network Design

Published: 2019/07/12

Oya Ekin Karasan

Hande Yaman

Barış Yıldız

Applications - OR and Management Sciences, Combinatorial Optimization, Transportation branch-and-cut, hub location, multimodal transport, network design, next day delivery, route dimensioning

We propose a novel hub location model that jointly eliminates the traditional assumptions on the structure of the network and on the discount due to economies of scale in an effort to better reflect real-world logistics and transportation systems. Our model extends the hub literature in various facets: instead of connecting non-hub nodes directly to … Read more

A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints

Published: 2019/06/21, Updated: 2022/09/27

Dimitris Bertsimas

Ryan Cory-Wright

Jean Pauphilet

(Mixed) Integer Nonlinear Programming, Cutting Plane Approaches branch-and-cut, mixed-integer programming, non-linear optimization, outer approximation

We propose a unified framework to address a family of classical mixed-integer optimization problems with logically constrained decision variables, including network design, facility location, unit commitment, sparse portfolio selection, binary quadratic optimization, sparse principal component analysis and sparse learning problems. These problems exhibit logical relationships between continuous and discrete variables, which are usually reformulated linearly … Read more

Arc routing with electric vehicles: dynamic charging and speed-dependent energy consumption

Published: 2019/06/21, Updated: 2020/07/17

(Mixed) Integer Linear Programming, Branch and Cut Algorithms, Production and Logistics arc routing, branch-and-cut, electric vehicles, heuristics, integer programming, non-linear charging, speed-dependent energy consumption

Concerns about greenhouse gas emissions and government regulations foster the use of electric vehicles. Several recently published articles study the use of electric vehicles (EVs) in node-routing problems. In contrast, this article considers EVs in the context of arc routing while also addressing practically relevant aspects that have not been addressed sufficiently so far. These … Read more