Combinatorial Optimization

Modular-topology optimization with Wang tilings: An application to truss structures

  • Martin Doskar
  • Martin Kružík
  • Matej Lepš
  • Marek Tyburec
  • Jan Zeman
    • Categories Civil and Environmental Engineering, Convex Optimization, Meta Heuristics Tags , , , ,

    Modularity is appealing for solving many problems in optimization. It brings the benefits of manufacturability and reconfigurability to structural optimization, and enables a trade-off between the computational performance of a Periodic Unit Cell (PUC) and the efficacy of non-uniform designs in multi-scale material optimization. Here, we introduce a novel strategy for concurrent minimum-compliance design of … Read more

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

  • Hussein Hazimeh
  • Rahul Mazumder
  • Ali Saab
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Second-Order Cone Programming Tags , , , ,

    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

    Solving the distance-based critical node problem

  • Austin Buchanan
  • Hosseinali Salemi
    • Categories 0-1 Programming, Branch and Cut Algorithms, Network Optimization

    In critical node problems, the task is identify a small subset of so-called critical nodes whose deletion maximally degrades a network’s “connectivity” (however that is measured). Problems of this type have been widely studied, e.g., for limiting the spread of infectious diseases. However, existing approaches for solving them have typically been limited to networks having … Read more

    On the exact solution of prize-collecting Steiner tree problems

  • Thorsten Koch
  • Daniel Rehfeldt
    • Categories Combinatorial Optimization Tags

    The prize-collecting Steiner tree problem (PCSTP) is a well-known generalization of the classic Steiner tree problem in graphs, with a large number of practical applications. It attracted particular interest during the 11th DIMACS Challenge in 2014, and since then, several PCSTP solvers have been introduced in the literature. Although these new solvers further, and often … Read more

    Energy-Efficient Timetabling in a German Underground System

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
  • Alexander Martin
  • Frederik Nöth
    • Categories Graphs and Matroids, Polyhedra, Scheduling Tags , , , ,

    Timetabling of railway traffic and other modes of transport is among the most prominent applications of discrete optimization in practice. However, it has only been recently that the connection between timetabling and energy consumption has been studied more extensively. In our joint project VAG Verkehrs-Aktiengesellschaft, the transit authority and operator of underground transport in the … Read more

    On a class of stochastic programs with exponentially many scenarios

  • Gustavo Angulo
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Stochastic Programming Tags , ,

    We consider a class of stochastic programs whose uncertain data has an exponential number of possible outcomes, where scenarios are affinely parametrized by the vertices of a tractable binary polytope. Under these conditions, we propose a novel formulation that introduces a modest number of additional variables and a class of inequalities that can be efficiently … Read more

    Dynamic Node Packing

  • Christopher Muir
  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming, Polyhedra Tags , , , ,

    We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable … Read more

    Stability in the the Hospitals / Residents problem with Couples and Ties: Mathematical models and computational studies

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , ,

    In the well-known Hospitals/Residents problem (HR), the objective is to find a stable matching of doctors (or residents) to hospitals based on their preference lists. In this paper, we study HRCT, the extension of HR in which doctors are allowed to apply in couples, and in which doctors and hospitals can include ties in their … Read more

    Continuous Cubic Formulations for Cluster Detection Problems in Networks

  • Vladimir Boginski
  • Austin Buchanan
  • Sergiy Butenko
  • Vladimir Stozhkov
    • Categories Combinatorial Optimization, Global Optimization, Integer Programming Tags , , , , , ,

    The celebrated Motzkin-Straus formulation for the maximum clique problem provides a nontrivial characterization of the clique number of a graph in terms of the maximum value of a nonconvex quadratic function over a standard simplex. It was originally developed as a way of proving Tur\'{a}n’s theorem in graph theory, but was later used to develop … Read more

    Orbital Conflict: Cutting Planes for Symmetric Integer Programs

  • Jeff Linderoth
  • James Ostrowski
  • Jose Nunez-Ares
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories Branch and Cut Algorithms, Integer Programming Tags

    Cutting planes have been an important factor in the impressive progress made by integer programming (IP) solvers in the past two decades. However, cutting planes have had little impact on improving performance for symmetric IPs. Rather, the main breakthroughs for solving symmetric IPs have been achieved by cleverly exploiting symmetry in the enumeration phase of … Read more