Other Topics

Equivalence of an Approximate Linear Programming Bound with the Held-Karp Bound for the Traveling Salesman Problem

  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming Tags , , ,

    We consider two linear relaxations of the asymmetric traveling salesman problem (TSP), the Held-Karp relaxation of the TSP’s arc-based formulation, and a particular approximate linear programming (ALP) relaxation obtained by restricting the dual of the TSP’s shortest path formulation. We show that the two formulations produce equal lower bounds for the TSP’s optimal cost regardless … Read more

    Effectiveness-Equity Models for Facility Location Problems on Tree Networks

  • Miguel A. Lejeune
  • Srinivas Prasad
    • Categories Convex Optimization, Multi-Criteria Optimization, Production and Logistics

    We propose models to investigate effectiveness-equity tradeoffs in tree network facility location problems. We use the commonly used median objective as a measure of effectiveness, and the Gini index as a measure of (in)equity, and formulate bicriteria problems involving these objectives. We develop procedures to identify an efficient set of solutions to these problems, analyze … Read more

    Well-posedness for Lexicographic Vector Equilibrium Problems

  • L. Q. Anh
  • Alexander Y. Kruger
  • T. Q. Duy
  • Nguyen H. Thao
    • Categories Multi-Criteria Optimization, Nonsmooth Optimization Tags , ,

    We consider lexicographic vector equilibrium problems in metric spaces. Sufficient conditions for a family of such problems to be (uniquely) well-posed at the reference point are established. As an application, we derive several results on well-posedness for a class of variational inequalities. CitationPublished in Constructive Nonsmooth Analysis and Related Topics (Vladimir Demyanov, Panos M. Pardalos, … Read more

    STOCHASTIC OPTIMIZATION OVER A PARETO SET ASSOCIATED WITH A STOCHASTIC MULTI-OBJECTIVE OPTIMIZATION PROBLEM

  • Henri Bonnel
  • Julien Collonge
    • Categories Multi-Criteria Optimization, Stochastic Approaches Tags , , , ,

    We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-Objective Optimization Problem (SMOP) whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation … Read more

    Risk-Averse Control of Undiscounted Transient Markov Models

  • Özlem Cavus
  • Andrzej Ruszczyński
    • Categories Dynamic Programming, Stochastic Programming

    We use Markov risk measures to formulate a risk-averse version of the undiscounted total cost problem for a transient controlled Markov process. We derive risk-averse dynamic programming equations and we show that a randomized policy may be strictly better than deterministic policies, when risk measures are employed. We illustrate the results on an optimal stopping … Read more

    A branch-and-bound algorithm for biobjective mixed-integer programs

  • Pietro Belotti
  • Banu Soylu
  • Margaret Wiecek
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization Tags , , ,

    We propose a branch-and-bound (BB) algorithm for biobjective mixed-integer linear programs (BOMILPs). Our approach makes no assumption on the type of problem and we prove that it returns all Pareto points of a BOMILP. We discuss two techniques upon which the BB is based: fathoming rules to eliminate those subproblems that are guaranteed not to … Read more

    The Subset Sum Game

  • Andreas Darmann
  • Gaia Nicosia
  • Ulrich Pferschy
  • Joachim Schauer
    • Categories Combinatorial Optimization, Game Theory Tags , , ,

    In this work we address a game theoretic variant of the Subset Sum problem, in which two decision makers (agents/players) compete for the usage of a common resource represented by a knapsack capacity. Each agent owns a set of integer weighted items and wants to maximize the total weight of its own items included in … Read more

    Exact Solution of the Robust Knapsack Problem

  • Michele Monaci
  • Ulrich Pferschy
  • Paolo Serafini
    • Categories Combinatorial Optimization, Dynamic Programming, Robust Optimization Tags , ,

    We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight di ffers from the expected one. For this problem, we provide a dynamic programming algorithm … Read more

    Simulation Optimization for the Stochastic Economic Lot Scheduling Problem with Sequence-Dependent Setup Times

  • Nils Löhndorf
  • Stefan Minner
  • Manuel Riel
    • Categories Optimization of Simulated Systems, Scheduling, Stochastic Approaches Tags , , , , ,

    We consider the stochastic economic lot scheduling problem (SELSP) with lost sales and random demand, where switching between products is subject to sequence-dependent setup times. We propose a solution based on simulation optimization using an iterative two-step procedure which combines global policy search with local search heuristics for the traveling salesman sequencing subproblem. To optimize … Read more

    A Generalization of a Theorem of Arrow, Barankin and Blackwell to a Nonconvex Case

  • Refail Kasimbeyli
  • Musa Mammadov
    • Categories Global Optimization, Global Optimization Theory, Multi-Criteria Optimization Tags , , , , , ,

    The paper presents a generalization of a known density theorem of Arrow, Barankin, and Blackwell for properly efficient points defined as support points of sets with respect to monotonically increasing sublinear functions. This result is shown to hold for nonconvex sets of a reflexive Banach space partially ordered by a Bishop–Phelps cone. CitationDepartment of Industrial … Read more