branch-and-cut – Page 5 – Optimization Online

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

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

(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

Chance-Constrained Bin Packing Problem with an Application to Operating Room Planning

Published: 2019/02/01, Updated: 2020/06/29

Jinlin Li

Sanjay Mehrotra

Shanshan Wang

Applications - OR and Management Sciences bilinear integer program, bin packing, branch-and-cut, chance-constrained stochastic programming, operating room planning, valid inequalities

We study the chance-constrained bin packing problem, with an application to hospital operating room planning. The bin packing problem allocates items of random size that follow a discrete distribution to a set of bins with limited capacity, while minimizing the total cost. The bin capacity constraints are satisfied with a given probability. We investigate a … Read more

Robust Optimization of a Broad Class of Heterogeneous Vehicle Routing Problems under Demand Uncertainty

Published: 2018/10/07, Updated: 2018/10/17

Chrysanthos E. Gounaris

Anirudh Subramanyam

Panagiotis P. Repoussis

Robust Optimization, Transportation branch-and-cut, demand uncertainty, local search, metaheuristics, robust optimization, vehicle routing

This paper studies robust variants of an extended model of the classical Heterogeneous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles with different capacities, availabilities, fixed costs and routing costs is used to serve customers with uncertain demand. This model includes, as special cases, all variants of the HVRP studied in the literature … Read more

Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem

Published: 2018/07/26, Updated: 2019/06/06

(Mixed) Integer Linear Programming, 0-1 Programming, Branch and Cut Algorithms branch-and-cut, connectivity, max-cut problem, mixed-integer programming

We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The … Read more

Model and exact solution for a two-echelon inventory routing problem

Published: 2018/07/23, Updated: 2019/02/08

Katyanne Farias

Khaled Hadj-Hamou

Claude Yugma

Branch and Cut Algorithms, Supply Chain Management, Transportation branch-and-cut, inventory routing, two-echelon, valid inequalities

The classic version of the Inventory Routing Problem considers a system with one supplier that manages the stock level of a set of customers. The supplier defines when and how much products to supply and how to combine customers in routes while minimizing storage and transportation costs. We present a new version of this problem … Read more

The SCIP Optimization Suite 6.0

Published: 2018/07/02, Updated: 2018/07/03

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, steiner tree optimization

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 6.0 of the SCIP Optimization Suite. Besides performance improvements of the MIP and MINLP core achieved by new primal heuristics and a new selection criterion … Read more

New facets for the consecutive ones polytope

Published: 2018/06/23

Laura Brentegani

Luigi De Giovanni

Mattia Festa

Branch and Cut Algorithms, Cutting Plane Approaches, Polyhedra branch-and-cut, consecutive ones problem, facets

A 0/1 matrix has the Consecutive Ones Property if a permutation of its columns exists such that the ones appear consecutively in each row. In many applications, one has to find a matrix having the consecutive ones property and optimizing a linear objective function. For this problem, literature proposes, among other approaches, an Integer Linear … Read more

Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems

Published: 2018/06/19

Jean-François Cordeau

Fabio Furini

Ivana Ljubić

Branch and Cut Algorithms, Combinatorial Optimization benders decomposition, branch-and-cut, combinatorial optimization, covering, location problems

Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the … Read more

Computing the Spark: Mixed-Integer Programming for the (Vector) Matroid Girth Problem

Published: 2018/03/14

Andreas M. Tillmann

(Mixed) Integer Linear Programming, Branch and Cut Algorithms, Graphs and Matroids branch-and-cut, compressed sensing, matroid girth, mixed-integer programming, spark

We investigate the NP-hard problem of computing the spark of a matrix (i.e., the smallest number of linearly dependent columns), a key parameter in compressed sensing and sparse signal recovery. To that end, we identify polynomially solvable special cases, gather upper and lower bounding procedures, and propose several exact (mixed-)integer programming models and linear programming … Read more