Month: April 2008

First-order algorithm with (ln(1/\epsilon))$ convergence for $\epsilonhBcequilibrium in two-person zero-sum games

  • Andrew Gilpin
  • Javier F. Peña
  • Tuomas Sandholm
    • Categories Convex Optimization, Game Theory Tags , ,

    We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x\in Q_1} \max_{y\in Q_2} \ip{x}{Ay} = \max_{y\in Q_2} \min_{x\in Q_1} \ip{x}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an $\epsilon$-equilibrium to this min-max problem in $\Oh(\kappa(A) \ln(1/\epsilon))$ first-order iterations, … Read more

    Copositive programming motivated bounds on the stability and the chromatic numbers

  • Igor Dukanovic
  • Franz Rendl
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , ,

    The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the … Read more

    Passenger Name Record Data Mining Based Cancellation Forecasting for Revenue Management

  • Dolores Romero Morales
  • Jingbo Wang
    • Categories Data-Mining, Yield Management Tags , , , ,

    Revenue management (RM) enhances the revenues of a company by means of demand-management decisions. An RM system must take into account the possibility that a booking may be canceled, or that a booked customer may fail to show up at the time of service (no-show). We review the Passenger Name Record data mining based cancellation … Read more

    Exact and heuristic solutions of the global supply chain problem with transfer pricing

  • Pierre Hansen
  • Sébastien Le Digabel
  • Sylvain Perron
  • Nenad Mladenovic
    • Categories Applications - OR and Management Sciences, Nonlinear Optimization, Supply Chain Management Tags , , , , ,

    We examine the example of a multinational corporation that attempts to maximize its global after tax profits by determining the flow of goods, the transfer prices, and the transportation cost allocation between each of its subsidiaries. Vidal and Goetschalckx (2001) proposed a bilinear model of this problem and solved it by an Alternate heuristic. We … Read more

    OrthoMADS: A deterministic MADS instance with orthogonal directions

  • Mark A. Abramson
  • Charles Audet
  • John E. Dennis, Jr.
  • Sébastien Le Digabel
    • Categories Applications - OR and Management Sciences, Nonsmooth Optimization Tags , , , ,

    he purpose of this paper is to introduce a new way of choosing directions for the mesh adaptive direct search (Mads) class of algorithms. The advantages of this new OrthoMads instantiation of Mads are that the polling directions are chosen deterministically, ensuring that the results of a given run are repeatable, and that they are … Read more

    Parallel Space Decomposition of the Mesh Adaptive Direct Search algorithm

  • Charles Audet
  • John E. Dennis, Jr.
  • Sébastien Le Digabel
    • Categories Applications - OR and Management Sciences, Nonsmooth Optimization, Parallel Algorithms Tags , , , ,

    This paper describes a parallel space decomposition PSD technique for the mesh adaptive direct search MADS algorithm. MADS extends a generalized pattern search for constrained nonsmooth optimization problems. The objective of the present work is to obtain good solutions to larger problems than the ones typically solved by MADS. The new method PSD-MADS is an … Read more

    Metaheuristic hybridization with GRASP

  • Mauricio G.C. Resende
    • Categories Meta Heuristics

    GRASP or greedy randomized adaptive search procedure is a multi-start metaheuristic that repeatedly applies local search starting from solutions constructed by a randomized greedy algorithm. In this paper we consider ways to hybridize GRASP to create new and more effective metaheuristics. We consider several types of hybridizations: constructive procedures, enhanced local search, memory structures, and … Read more

    Geometric Rounding: A Dependent Rounding Scheme for Allocation Problems

  • Dongdong Ge
  • Yinyu Ye
  • Shuzhong Zhang
  • Simai He
  • Zizhuo Wang
    • Categories Applications - OR and Management Sciences, Approximation Algorithms

    This paper presents a general technique to develop approximation algorithms for allocation problems with integral assignment constraints. The core of the method is a randomized dependent rounding scheme, called geometric rounding, which yields termwise rounding ratios (in expectation), while emphasizing the strong correlation between events. We further explore the intrinsic geometric structure and general theoretical … Read more

    Maximizing a Class of Submodular Utility Functions

  • Shabbir Ahmed
  • Alper Atamturk
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , ,

    Given a finite ground set N and a value vector a in R^N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S)= f (sum_{i in S} a_i), S subseteq N, where f is a strictly concave, increasing, differentiable function. This function appears frequently in combinatorial optimization problems when … Read more

    Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces

  • Anatoli Juditsky
  • Arkadi Nemirovski
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    In this paper, we derive exponential bounds on probabilities of large deviations for “light tail” martingales taking values in finite-dimensional normed spaces. Our primary emphasis is on the case where the bounds are dimension-independent or nearly so. We demonstrate that this is the case when the norm on the space can be approximated, within an … Read more