Combinatorial Optimization

A Computational Study of Constraint Programming Approaches for Resource-Constrained Project Scheduling with Autonomous Learning Effects

  • Alessandro Hill
  • Jordan Ticktin
  • Thomas Vossen
    • Categories Combinatorial Optimization, Scheduling

    It is well-known that experience can lead to increased efficiency, yet this is largely unaccounted for in project scheduling. We consider project scheduling problems where the duration of activities can be reduced when scheduled after certain other activities that allow for learning relevant skills. Since per-period availabilities of renewable resources are limited and precedence requirements … Read more

    An Almost Exact Multi-Machine Scheduling Solution for Homogeneous Processing

  • Stefano Nasini
  • Rabia Nessah
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Scheduling

    In the context of job scheduling in parallel machines, we present a class of asymptotically exact binary programs for the minimization of the $\tau$-norm of completion time variances. Building on overlooked properties of the min completion time variance in a single machine and on an equivalent bilevel formulation, our approach provides an asymptotic approximation (with … Read more

    Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints

  • Simge Küçükyavuz
  • Qimeng Yu
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Polyhedra Tags , ,

    We study the polyhedral convex hull structure of a mixed-integer set which arises in a class of cardinality-constrained concave submodular minimization problems. This class of problems has an objective function in the form of $f(a^\top x)$, where $f$ is a univariate concave function, $a$ is a non-negative vector, and $x$ is a binary vector of … Read more

    Sequential Competitive Facility Location: Exact and Approximate Algorithms

  • Mingyao Qi
  • Ruiwei Jiang
  • Siqian Shen
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Facility Planning and Design Tags , , , , ,

    We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation … Read more

    A tailored Benders decomposition approach for last-mile delivery with autonomous robots

  • Laurent Alfandari
  • Ivana Ljubić
  • Marcos de Melo da Silva
    • Categories Branch and Cut Algorithms, Network Optimization, Transportation Tags , , ,

    This work addresses an operational problem of a logistics service provider that consists of finding an optimal route for a vehicle carrying customer parcels from a central depot to selected facilities, from where autonomous devices like robots are launched to perform last-mile deliveries. The objective is to minimize a tardiness indicator based on the customer … Read more

    An Adaptive and Near Parameter-free BRKGA Using Q-Learning Method

  • Antonio Chaves
  • Luiz Henrique Lorena
    • Categories Meta Heuristics Tags , , ,

    The Biased Random-Key Genetic Algorithm (BRKGA) is an efficient metaheuristic to solve combinatorial optimization problems but requires parameter tuning so the intensification and diversification of the algorithm work in a balanced way. There is, however, not only one optimal parameter configuration, and the best configuration may differ according to the stages of the evolutionary process. … Read more

    Scaling Up Exact Neural Network Compression by ReLU Stability

  • Abhinav Kumar
  • Srikumar Ramalingam
  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Combinatorial Optimization

    We can compress a neural network while exactly preserving its underlying functionality with respect to a given input domain if some of its neurons are stable. However, current approaches to determine the stability of neurons in networks with Rectified Linear Unit (ReLU) activations require solving or finding a good approximation to multiple discrete optimization problems. … Read more

    Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees

  • Salar Fattahi
  • Andrés Gómez
    • Categories Combinatorial Optimization, Statistics Tags , ,

    In this paper, we study the problem of inferring time-varying Markov random fields (MRF), where the underlying graphical model is both sparse and changes sparsely over time. Most of the existing methods for the inference of time-varying MRFs rely on the regularized maximum likelihood estimation (MLE), that typically suffer from weak statistical guarantees and high … Read more

    An exact price-cut-and-enumerate method for the capacitated multi-trip vehicle routing problem with time windows

  • Yu Yang
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation Tags , , ,

    We consider the capacitated multi-trip vehicle routing problem with time windows (CMTVRPTW), where vehicles are allowed to make multiple trips. The ability to perform multiple trips is necessary for some real-world applications where the vehicle capacity, the trip duration, or the number of drivers or vehicles is limited. However, it substantially increases the solution difficulty … Read more

    Set characterizations and convex extensions for geometric convex-hull proofs

  • Andreas Bärmann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Polyhedra Tags , , , ,

    In the present work, we consider Zuckerberg’s method for geometric convex-hull proofs introduced in [Geometric proofs for convex hull defining formulations, Operations Research Letters 44(5), 625–629 (2016)]. It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. … Read more