Month: October 2022

Data-Driven Approximation of Contextual Chance-Constrained Stochastic Programs

  • Hamed Rahimian
  • Bernardo K. Pagnoncelli
    • Categories Stochastic Programming Tags , , ,

    Uncertainty in classical stochastic programming models is often described solely by independent random parameters, ignoring their dependence on multidimensional features. We describe a novel contextual chance-constrained programming formulation that incorporates features, and argue that solutions that do not take them into account may not be implementable. Our formulation cannot be solved exactly in most cases, … Read more

    Inexact Penalty Decomposition Methods for Optimization Problems with Geometric Constraints

  • Christian Kanzow
  • Matteo Lapucci
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , , ,

    This paper provides a theoretical and numerical investigation of a penalty decomposition scheme for the solution of optimization problems with geometric constraints. In particular, we consider some  situations where parts of the constraints are nonconvex and complicated, like cardinality constraints, disjunctive programs, or matrix problems involving rank constraints. By a variable duplication and  decomposition strategy, … Read more

    A Combinatorial Flow-based Formulation for Temporal Bin Packing Problems

  • John Martinovic
  • Nico Strasdat
  • José Valério de Carvalho
  • Fabio Furini
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , , ,

    We consider two neighboring generalizations of the classical bin packing problem: the temporal bin packing problem (TBPP) and the temporal bin packing problem with fire-ups (TBPP-FU). In both cases, the task is to arrange a set of given jobs, characterized by a resource consumption and an activity window, on homogeneous servers of limited capacity. To … Read more

    Vehicle Routing with Heterogeneous Time Windows

  • Petra Mutzel
  • Tim Niemann
  • Sebastian Stiller
  • Andreas M. Tillmann
  • Lukas Schürmann
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , ,

    We consider a novel variant of the heterogeneous vehicle routing problem (VRP) in which each customer has different availability time windows for every vehicle. In particular, this covers our motivating application of planning daily delivery tours for a single vehicle, where customers can be available at different times each day. The existing literature on heterogeneous … Read more

    An integrated assignment, routing, and speed model for roadway mobility and transportation with environmental, efficiency, and service goals

  • Tommaso Giovannelli
  • Luis Nunes Vicente
    • Categories Transportation Tags , , ,

    Managing all the mobility and transportation services with autonomous vehicles for users of a smart city requires determining the assignment of the vehicles to the users and their routing in conjunction with their speed. Such decisions must ensure low emission, efficiency, and high service quality by also considering the impact on traffic congestion caused by … Read more

    RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates

  • Laurent Condat
  • Peter Richtarik
    • Categories Convex and Nonsmooth Optimization

    Proximal splitting algorithms are well suited to solving large-scale nonsmooth optimization problems, in particular those arising in machine learning. We propose a new primal-dual algorithm, in which the dual update is randomized; equivalently, the proximity operator of one of the function in the problem is replaced by a stochastic oracle. For instance, some randomly chosen … Read more

    Inertial Krasnoselskii-Mann Iterations

  • Juan Peypouquet
    • Categories Convex Optimization, Other Topics

    We establish the weak convergence of inertial Krasnoselskii-Mann iterations towards a common fixed point of a family of quasi-nonexpansive operators, along with worst case estimates for the rate at which the residuals vanish. Strong and linear convergence are obtained in the quasi-contractive setting. In both cases, we highlight the relationship with the non-inertial case, and … Read more

    The cost of nonconvexity in deterministic nonsmooth optimization

  • Adrian Lewis
    • Categories Nonsmooth Optimization Tags , , , ,

    We study the impact of nonconvexity on the complexity of nonsmooth optimization, emphasizing objectives such as piecewise linear functions, which may not be weakly convex. We focus on a dimension-independent analysis, slightly modifying a black-box algorithm of Zhang et al. that approximates an $\epsilon$-stationary point of any directionally differentiable Lipschitz objective using $O(\epsilon^{-4})$ calls to … Read more

    A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints

  • Noah Weninger
  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Dynamic Programming Tags , , , ,

    We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the … Read more

    Evaluating Mixed-Integer Programming Models over Multiple Right-hand Sides

  • Rachael M. Alfant
  • Temitayo Ajayi
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming Tags , ,

    A critical measure of model quality for a mixed-integer program (MIP) is the difference, or gap, between its optimal objective value and that of its linear programming relaxation. In some cases, the right-hand side is not known exactly; however, there is no consensus metric for evaluating a MIP model when considering multiple right-hand sides. In … Read more