Branch-and-Bound

Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements

  • Xiang Meng
  • Andrés Gómez
  • Rahul Mazumder
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , ,

    We study computational aspects of a key problem in robust statistics—the penalized least trimmed squares (LTS) regression problem, a robust estimator that mitigates the influence of outliers in data by capping residuals with large magnitudes. Although statistically attractive, penalized LTS is NP-hard, and existing mixed-integer optimization (MIO) formulations scale poorly due to weak relaxations and … Read more

    Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching

  • Selin Bayramoglu
  • George L. Nemhauser
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typically with GPU parallelization. In this work, we take a different path by developing interpretable models that are … Read more

    Beyond binarity: Semidefinite programming for ternary quadratic problems

  • Frank de Meijer
  • Veronica Piccialli
  • Renata Sotirov
  • Antonio M. Sudoso
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Tags , , ,

    We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation … Read more

    A Combinatorial Branch-and-Bound Algorithm for the Capacitated Facility Location Problem under Strict Customer Preferences

  • Christina Büsing
  • Felix Engelhardt
  • Sophia Wrede
    • Categories Bilevel Optimization, Branch and Cut Algorithms, Combinatorial Optimization Tags , , , ,

    This work proposes a combinatorial branch-and-bound (B&B) algorithm for the capacitated facility location problem under strict customer preferences (CFLP-SCP). We use combinatorial insights into the problem structure to do preprocessing, model branching implications, enforce feasibility or prove infeasibility in each node, select variables and derive primal and dual bounds in each node of the B&B … Read more

    An Introduction to Decision Diagrams for Optimization

  • Willem-Jan van Hoeve
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming Tags , , , , , ,

    This tutorial provides an introduction to the use of decision diagrams for solving discrete optimization problems. A decision diagram is a graphical representation of the solution space, representing decisions sequentially as paths from a root node to a target node. By merging isomorphic subgraphs (or equivalent subproblems), decision diagrams can compactly represent an exponential solution … Read more

    Probing-Enhanced Stochastic Programming

  • Zhichao Ma
  • Youngdae Kim
  • Jeff Linderoth
  • James R. Luedtke
  • Logan Matthews
    • Categories Stochastic Programming Tags , , ,

    We consider a two-stage stochastic decision problem where the decision-maker has the opportunity to obtain information about the distribution of the random variables $\xi$ that appear in the problem through a set of discrete actions that we refer to as probing. Probing components of a random vector $\eta$ that is jointly-distributed with $\xi$ allows the … Read more

    Interdiction of minimum spanning trees and other matroid bases

  • Noah Weninger
  • Ricardo Fukasawa
    • Categories 0-1 Programming, Dynamic Programming, Graphs and Matroids Tags , , , , , ,

    In the minimum spanning tree (MST) interdiction problem, we are given a graph \(G=(V,E)\) with edge weights, and want to find some \(X\subseteq E\) satisfying a knapsack constraint such that the MST weight in \((V,E\setminus X)\) is maximized. Since MSTs of \(G\) are the minimum weight bases in the graphic matroid of \(G\), this problem … Read more

    Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

  • Yatharth Dubey
  • Gérard Cornuéjols
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , ,

    In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce “skewed $k$-trees” which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also … Read more

    A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming

  • Baha Alzalg
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Second-Order Cone Programming Tags , , , ,

    One of the chief attractions of stochastic mixed-integer second-order cone programming is its diverse applications, especially in engineering (Alzalg and Alioui, {\em IEEE Access}, 10:3522-3547, 2022). The linear and nonlinear versions of this class of optimization problems are still unsolved yet. In this paper, we develop a hybrid optimization algorithm coupling branch-and-bound and primal-dual interior-point … Read more