Branch-and-Bound – Page 4 – Optimization Online

Linearization and Parallelization Schemes for Convex Mixed-Integer Nonlinear Optimization

Published: 2020/05/14, Updated: 2022/02/03

(Mixed) Integer Nonlinear Programming, Parallel Algorithms Branch-and-Bound, convex minlp, linearization techniques, outer approximation, shared-memory parallel

We develop and test linearization and parallelization schemes for convex mixed-integer nonlinear programming. Several linearization approaches are proposed for LP/NLP based branch-and-bound. Some of these approaches strengthen the linear approximation to nonlinear constraints at the root node and some at the other branch-and-bound nodes. Two of the techniques are specifically applicable to commonly found univariate … Read more

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization

Published: 2020/04/13

Hussein Hazimeh

Rahul Mazumder

Ali Saab

(Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Second-Order Cone Programming Branch-and-Bound, first-order methods, l0 regularization, sparse regression, sparsity

We consider the least squares regression problem, penalized with a combination of the L0 and L2 norms (a.k.a. L0 L2 regularization). Recent work presents strong evidence that the resulting L0-based estimators can outperform popular sparse learning methods, under many important high-dimensional settings. However, exact computation of L0-based estimators remains a major challenge. Indeed, state-of-the-art mixed … Read more

Complexity of cutting planes and branch-and-bound in mixed-integer optimization

Published: 2020/03/10

(Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Branch-and-Bound, complexity, cutting planes

We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP … Read more

Achieving Consistency with Cutting Planes

Published: 2020/01/01, Updated: 2022/02/07

Danial Davarnia

Atefeh Rajabalizadeh

John Hooker

0-1 Programming, Cutting Plane Approaches Branch-and-Bound, consistency, constraint programming, cutting planes, integer programming

Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linear programming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching. A partial assignment is inconsistent with a constraint set when … Read more

Assessing the Effectiveness of (Parallel) Branch-and-bound Algorithms

Published: 2019/09/25

Stephen J. Maher

Ted K. Ralphs

Yuji Shinano

(Mixed) Integer Linear Programming, Integer Programming, Parallel Algorithms algorithm assessment, benchmarking, Branch-and-Bound, effectiveness, efficiency, performance, scalability

Empirical studies are fundamental in assessing the effectiveness of implementations of branch-and-bound algorithms. The complexity of such implementations makes empirical study difficult for a wide variety of reasons. Various attempts have been made to develop and codify a set of standard techniques for the assessment of optimization algorithms and their software implementations; however, most previous … Read more

Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models

Published: 2019/08/13

Applications - OR and Management Sciences, Multi-Criteria Optimization bi-objective models, Branch-and-Bound, general linear integer programs, knapsack problem, non-dominated point set, reformulation

In this paper, a reformulation that was proposed for a knapsack problem has been extended to single and bi-objective linear integer programs. A further reformulation by adding an upper bound constraint for a knapsack problem is also proposed and extended to the bi-objective case. These reformulations significantly reduce the number of branch and bound iterations … Read more

Solving Heated Oil Pipeline Problems Via Mixed Integer Nonlinear Programming Approach

Published: 2019/07/26

(Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Branch-and-Bound, convex relaxation, heated oil pipeline problem, mixed-integer nonlinear programming, nonconvex relaxation, outer approximation, warm-start

It is a crucial problem how to heat oil and save running cost for crude oil transport. This paper strictly formulates such a heated oil pipeline problem as a mixed integer nonlinear programming model. Nonconvex and convex continuous relaxations of the model are proposed, which are proved to be equivalent under some suitable conditions. Meanwhile, … Read more

Team as a Service: Team Formation on Social Networks

Published: 2019/03/22

Nihal Berktas

Hande Yaman

0-1 Programming, Applications - OR and Management Sciences Branch-and-Bound, quadratic set covering, reformulation, team as a service, team formation problem

Team as a Service (TaaS) is a new outsourcing service that enables on-demand creation and management of distributed teams for fast growing companies. The companies that use the TaaS model form a team according to the needs of a given project and provide managerial service throughout. Motivated by this new application, we study the Team … Read more

An Enhanced Logical Benders Approach for Linear Programs with Complementarity

Published: 2019/03/11

Francisco Jara-Moroni

John E. Mitchell

Jong-Shi Pang

Complementarity and Variational Inequalities, Global Optimization, Nonlinear Optimization Branch-and-Bound, complementarity constraints, logical benders

This work extends the ones of Hu et al. (2008) and Bai et al. (2013) of a logical Benders approach for globally solving Linear Programs with Complementarity Constraints. By interpreting the logical Benders method as a reversed branch-and-bound method, where the whole exploration procedure starts from the leaf nodes in an enumeration tree, we provide … Read more

Resilient layout, design and operation of energy-efficient water distribution networks for high-rise buildings using MINLP

Published: 2018/10/16, Updated: 2019/02/27

(Mixed) Integer Nonlinear Programming, Mechanical Engineering, Robust Optimization Branch-and-Bound, decentralization, energy-efficiency, mixed-integer nonlinear programming, network, pump system, resilience, water supply

Water supply of high-rise buildings requires pump systems to ensure pressure requirements. The design goal of these systems are energy and cost efficiency, both in terms of fixed cost as well as during operation. In this paper, cost optimal decentralized and tree-shaped water distribution networks are computed, where placements of pumps at different locations in … Read more