Branch and Cut Algorithms

The Minimization of the Weighted Completion Time Variance in a Single Machine: A Specialized Cutting-Plane Approach

  • Stefano Nasini
  • Rabia Nessah
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling

    This study addresses the problem of minimizing the weighted completion time variance (WCTV) in single-machine scheduling. Unlike the unweighted version, which has been extensively studied, the weighted variant introduces unique challenges due to the absence of theoretical properties that could guide the design of efficient algorithms. We propose a mathematical programming framework based on a … Read more

    A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

  • Henri Lefebvre
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

    A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization Theory Tags , , , ,

    Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses … Read more

    A Decision Diagram Approach for the Parallel Machine Scheduling Problem with Chance Constraints

  • Nicolás Casassus
  • Margarita P Castro
  • Gustavo Angulo
    • Categories Branch and Cut Algorithms, Scheduling, Stochastic Programming Tags , ,

    The Chance-Constrained Parallel Machine Scheduling Problem (CC-PMSP) assigns jobs with uncertain processing times to machines, ensuring that each machine’s availability constraints are met with a certain probability. We present a decomposition approach where the master problem assigns jobs to machines, and the subproblems schedule the jobs on each machine while verifying the solution’s feasibility under … Read more

    The Undirected Team Orienteering Arc Routing Problem: Formulations, Valid Inequalities, and Exact Algorithms

  • Wenjin Yan
  • Elena Fernandez
  • Ivana Ljubić
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Network Optimization Tags , , ,

    We address the Undirected Team Orienteering Arc Routing Problem (UTOARP). In this problem, demand is placed at some edges of a given undirected graph and served demand edges produce a profit. Feasible routes must start and end at a given depot and there is a time limit constraint on the maximum duration of each route. … Read more

    Accelerating Benders decomposition for solving a sequence of sample average approximation replications

  • Harshit Kothari
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming

    Sample average approximation (SAA) is a technique for obtaining approximate solutions to stochastic programs that uses the average from a random sample to approximate the expected value that is being optimized. Since the outcome from solving an SAA is random, statistical estimates on the optimal value of the true problem can be obtained by solving … Read more

    Partitioning a graph into low-diameter clusters

  • Jack Zhang
  • Lucas Vinícius Silveira de Lima
  • Hamidreza Validi
  • Logan Smith
  • Austin Buchanan
  • Illya V. Hicks
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Network Optimization Tags , , , ,

    This paper studies the problems of partitioning the vertices of a graph G = (V,E) into (or covering with) a minimum number of low-diameter clusters from the lenses of approximation algorithms and integer programming. Here, the low-diameter criterion is formalized by an s-club, which is a subset of vertices whose induced subgraph has diameter at … Read more

    Column Elimination: An Iterative Approach to Solving Integer Programs

  • Anthony Karahalios
  • Willem-Jan van Hoeve
    • Categories Branch and Cut Algorithms, Dynamic Programming, Integer Programming Tags , , , , ,

    We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then … Read more

    Bounding the number and the diameter of optimal compact Black-majority districts

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
  • Tyler Perini
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms, Combinatorial Optimization Tags , , ,

    Section 2 of the Voting Rights Act (VRA) prohibits voting practices that minimize or cancel out minority voting strength. While this section provides no clear framework for avoiding minority vote dilution and creating minority-majority districts, the Supreme Court proposed the Gingles test in the 1986 case Thornberg v Gingles. The Gingles test provides three conditions … Read more

    Spatial branching for a special class of convex MIQO problems

  • Pietro Belotti
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms Tags , ,

    In the branch-and-bound algorithm, branching is the key step to deal with the nonconvexity of the problem. For Mixed Integer Linear Optimization (MILO) problems and, in general, Mixed Integer Nonlinear Optimization (MINLO) problems whose continuous relaxation is convex, branching on integer and binary variables suffices, because fixing all integer variables yields a convex relaxation. General, … Read more