Other Topics

FPBH.jl: A Feasibility Pump Based Heuristic for Multi-objective Mixed Integer Linear Programming in Julia

  • Hadi Charkhgard
  • Aritra Pal
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Optimization Software and Modeling Systems Tags , , , ,

    Feasibility pump is one of the successful heuristic solution approaches developed almost a decade ago for computing high-quality feasible solutions of single-objective integer linear programs, and it is implemented in exact commercial solvers such as CPLEX and Gurobi. In this study, we present the first Feasibility Pump Based Heuristic (FPBH) approach for approximately generating nondominated … Read more

    Dynamic Relaxations for Online Bipartite Matching

  • Alejandro Toriello
  • Alfredo Torrico
    • Categories Dynamic Programming Tags , , ,

    Online bipartite matching (OBM) is a fundamental model underpinning many important applications, including search engine advertisement, website banner and pop-up ads, and ride-hailing. We study the i.i.d. OBM problem, where one side of the bipartition is fixed and known in advance, while nodes from the other side appear sequentially as i.i.d. realizations of an underlying … Read more

    Joint Inventory and Revenue Management with Removal Decisions

  • Alvaro Maggiar
  • Ali Sadighian
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Supply Chain Management Tags , , , , , ,

    We study the problem of a retailer that maximizes profit through joint replenishment, pricing and removal decisions. This problem is motivated by the observation that retailers usually retain rights to remove inventory from their network either by returning it to the suppliers or through liquidation in the face of random demand and capacity constraints. We … Read more

    Payment Mechanisms for Electricity Markets with Uncertain Supply

  • Ryan Cory-Wright
  • Andrew B. Philpott
  • Golbon Zakeri
    • Categories Finance and Economics, Game Theory, Stochastic Programming Tags , , ,

    This paper provides a framework for deriving payment mechanisms for intermittent, flexible and inflexible electricity generators who are dispatched according to the optimal solution of a stochastic program that minimizes the expected cost of generation plus deviation. The first stage corresponds to a pre-commitment decision, and the second stage corresponds to real-time generation that adapts … Read more

    Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional action and scalar state

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming, Supply Chain Management Tags , , , ,

    We propose a Fully Polynomial-Time Approximation Scheme (FPTAS) for stochastic dynamic programs with multidimensional action, scalar state, convex costs and linear state transition function. The action spaces are polyhedral and described by parametric linear programs. This type of problems finds applications in the area of optimal planning under uncertainty, and can be thought of as … Read more

    Coordination of a two-level supply chain with contracts under complete or asymmetric information

  • Safia Kedad-Sidhoum
  • Fanny Pascual
  • Siao-Leu Phouratsamay
    • Categories Dynamic Programming, Supply Chain Management Tags , , , , ,

    We consider the coordination of planning decisions of a single product in a supply chain composed of one supplier and one retailer by using contracts. We assume that the retailer has the market power to impose his optimal replenishment plan to the supplier. Our concern is on the minimization of the supplier’s cost. In order … Read more

    Inexact cuts for Deterministic and Stochastic Dual Dynamic Programming applied to convex nonlinear optimization problems

  • Vincent Guigues
    • Categories Convex Optimization, Dynamic Programming, Stochastic Programming

    We introduce an extension of Dual Dynamic Programming (DDP) to solve convex nonlinear dynamic programming equations. We call Inexact DDP (IDDP) this extension which applies to situations where some or all primal and dual subproblems to be solved along the iterations of the method are solved with a bounded error. We show that any accumulation … Read more

    Bi-objective autonomous vehicle repositioning problem with travel time uncertainty

  • Hadi Charkhgard
  • Zulqarnain Haider
  • Mahdi Takalloo
    • Categories Multi-Criteria Optimization, Stochastic Programming, Transportation Tags , ,

    We study the problem of repositioning autonomous vehicles in a shared mobility system in order to simultaneously minimize the unsatisfied demand and the total operating cost. We first present a mixed integer linear programming formulation for the deterministic version of the problem, and based on that we develop an extended formulation that is easier to … Read more

    Semidefinite Programming and Nash Equilibria in Bimatrix Games

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Game Theory, Semi-definite Programming Tags , ,

    We explore the power of semidefinite programming (SDP) for finding additive epsilon-approximate Nash equilibria in bimatrix games. We introduce an SDP relaxation for a quadratic programming formulation of the Nash equilibrium (NE) problem and provide a number of valid inequalities to improve the quality of the relaxation. If a rank-1 solution to this SDP is … Read more

    New algorithms for discrete vector optimization based on the Graef-Younes method and cone-monotone sorting functions

  • Christian Günther
  • Nicolae Popovici
    • Categories Constrained Nonlinear Optimization, Multi-Criteria Optimization

    The well-known Jahn-Graef-Younes algorithm, proposed by Jahn in 2006, generates all minimal elements of a finite set with respect to an ordering cone. It consists of two Graef-Younes procedures, namely the forward iteration, which eliminates a part of the non-minimal elements, followed by the backward iteration, which is applied to the reduced set generated by … Read more