Optimization Online


Feasible rounding approaches and diving strategies in branch-and-bound methods for mixed-integer optimization

Christoph Neumann (christoph.neumann***at***kit.edu)
Stefan Schwarze (stefan.schwarze***at***kit.edu)
Oliver Stein (stein***at***kit.edu)
Benjamin Müller (benjamin.mueller***at***zib.de)

Abstract: In this paper, we study the behavior of feasible rounding approaches for mixed-integer linear and nonlinear optimization problems (MILP and MINLP, respectively) when integrated into tree search of branch-and-bound. Our research addresses two important aspects. First, we develop insights into how an (enlarged) inner parallel set, which is the main component for feasible rounding approaches, behaves when we move down a search tree. Our theoretical results show that the number of feasible points obtainable from the inner parallel set is nondecreasing with increasing depth of the search tree. Thus, they hint at the potential benefit of integrating feasible rounding approaches into branch-and-bound methods. Second, based on those insights, we develop a novel primal heuristic for MILPs that fixes variables in a way that promotes large inner parallel sets of child nodes. Our computational study shows that combining feasible rounding approaches with the presented diving ideas yields a significant improvement over their application in the root node. Moreover, the proposed method is able to deliver best solutions for SCIP for a significant share of problems which hints at its potential to support solving MILPs.

Keywords: Variable Fixing, Diving, Granularity, MILP, MINLP, Inner Parallel Set

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Optimization Online, Preprint-ID 2021-10-8630, 2021

Download: [PDF]

Entry Submitted: 10/12/2021
Entry Accepted: 10/12/2021
Entry Last Modified: 10/12/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society