Combinatorial Optimization

Polynomial-Time Algorithms for Setting Tight Big-M Coefficients in Transmission Expansion Planning with Disconnected Buses

  • Behnam Jabbari Marand
  • Adolfo Escobedo
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Energy Tags , , ,

    The increasing penetration of renewable energy into power systems necessitates the development of effective methodologies to integrate initially disconnected generation sources into the grid. This paper introduces the Longest Shortest-Path-Connection (LSPC) algorithm, a graph-based method to enhance the mixed-integer linear programming disjunctive formulation of Transmission Expansion Planning (TEP) using valid inequalities (VIs). Traditional approaches for … Read more

    A Generalized Voting Game for Categorical Network Choices

  • Lin Yueh
  • Stefano Nasini
  • Martine Labbé
    • Categories Combinatorial Optimization, Data Science Algorithms, Game Theory Tags , , ,

    This paper presents a game-theoretical framework for data classification and network discovery, focusing on pairwise influences in multivariate choices. The framework consists of two complementary games in which individuals, connected through a signed weighted graph, exhibit network similarity. A voting rule captures the influence of an individual’s neighbors, categorized as attractive (friend-like) or repulsive (enemy-like), … Read more

    On parametric formulations for the Asymmetric Traveling Salesman Problem

  • Gustavo Angulo
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra

    The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations … Read more

    A folding preprocess for the max k-cut problem

  • Ramin Fakhimi
  • Hamidreza Validi
  • Illya V. Hicks
  • Tamás Terlaky
  • Luis F. Zuluaga
    • Categories Combinatorial Optimization, Graphs and Matroids, Network Optimization

    Given graph G = (V,E) with vertex set V and edge set E, the max k-cut problem seeks to partition the vertex set V into at most k subsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number … Read more

    Unboundedness in Bilevel Optimization

  • Bárbara Rodrigues
  • Margarida Carvalho
  • Miguel F. Anjos
    • Categories (Mixed) Integer Nonlinear Programming, Nonlinear Optimization, Polyhedra Tags , , ,

    Bilevel optimization has garnered growing interest over the past decade. However, little attention has been paid to detecting and dealing with unboundedness in these problems, with most research assuming a bounded high-point relaxation. In this paper, we address unboundedness in bilevel optimization by studying its computational complexity and developing algorithmic approaches to detect it. We … Read more

    An analytical lower bound for a class of minimizing quadratic integer optimization problems

  • Christian Schmitt
  • Bismark Singh
    • Categories Combinatorial Optimization, Integer Programming, Quadratic Programming Tags , , ,

    Lower bounds on minimization problems are essential for convergence of both branching-based and iterative solution methods for optimization problems. They are also required for evaluating the quality of feasible solutions by providing conservative optimality gaps. We provide an analytical lower bound for a class of quadratic optimization problems with binary decision variables. In contrast to … 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

    Single-Scenario Facet Preservation for Stochastic Mixed-Integer Programs

  • Aysenur Karagoz
    • Categories Integer Programming, Polyhedra, Stochastic Programming Tags , , ,

    We consider improving the polyhedral representation of the extensive form of a stochastic mixed-integer program (SMIP). Given a facet for a single-scenario version of an SMIP, our main result provides necessary and sufficient conditions under which this inequality remains facet-defining for the extensive form. We then present several implications, which show that common recourse structures … 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

    On the Complexity of Finding Locally Optimal Solutions in Bilevel Linear Optimization

  • Oleg A. Prokopyev
  • Ted K. Ralphs
    • Categories Combinatorial Optimization, Game Theory, Other Topics

    We consider the theoretical computational complexity of finding locally optimal solutions to bilevel linear optimization problems (BLPs), from the leader’s perspective. We show that, for any constant \(c > 0\), the problem of finding a leader’s solution that is within Euclidean distance \(c^n\) of any locally optimal leader’s solution, where \(n\) is the total number … Read more