Applications – OR and Management Sciences

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

    A Hybrid Relax-and-Cut/Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem

  • Alexandre Cunha
  • Abílio Lucena
    • Categories Branch and Cut Algorithms, Telecommunications Tags , , ,

    A new exact solution algorithm is proposed for the Degree-Constrained Minimum Spanning Tree Problem. The algorithm involves two combined phases. The first one contains a Lagrangian Relax-and-Cut procedure while the second implements a Branch-and-Cut algorithm. Both phases rely on a standard formulation for the problem, reinforced with Blossom Inequalities. An important feature of the proposed … Read more

    An exact algorithm for solving the ring star problem

  • Safia Kedad-Sidhoum
  • Viet Hung Nguyen
    • Categories Branch and Cut Algorithms, Network Optimization, Telecommunications Tags , , , ,

    This paper deals with the ring star problem that consists in designing a ring that pass through a central depot, and then assigning each non visited customer to a node of the ring. The objective is to minimize the total routing and assignment costs. A new chain based formulation is proposed. Valid inequalities are proposed … Read more

    Linear Programming for Mechanism Design: An Application to Bidder Collusion at First-Price Auctions

  • Giuseppe Lopomo
  • Peng Sun
  • Leslie Marx
    • Categories Applications - OR and Management Sciences, Game Theory, Linear Programming Tags , , ,

    We demonstrate the use of linear programming techniques in the analysis of mechanism design problems. We use these techniques to analyze the extent to which a first-price auction is robust to collusion when, contrary to some prior literature on collusion at first-price auctions, the cartel cannot prevent its members from bidding at the auction. In … Read more

    Integrated Forecasting and Inventory Control for Seasonal Demand: a Comparison with the Holt-Winters Approach

  • Gokhan Metan
  • Aurelie Thiele
    • Categories Production and Logistics Tags ,

    We present a data-driven forecasting technique with integrated inventory control for seasonal data and compare it to the traditional Holt-Winters algorithm. Results indicate that the data-driven approach achieves a 2-5% improvement in the average regret. CitationTechnical Report, Lehigh University, Department of Industrial and Systems Engineering, Bethlehem, PA.ArticleDownload View PDF

    Tractable Robust Expected Utility and Risk Models for Portfolio Optimization

  • Karthik Natarajan
  • Melvyn Sim
  • Joline Uichanco
    • Categories Finance and Economics, Robust Optimization, Second-Order Cone Programming

    Expected utility models in portfolio optimization is based on the assumption of complete knowledge of the distribution of random returns. In this paper, we relax this assumption to the knowledge of only the mean, covariance and support information. No additional assumption on the type of distribution such as normality is made. The investor’s utility is … Read more

    An improved Benders decomposition applied to a multi-layer network design problem

  • Bernard Fortz
  • Michael Poss
    • Categories Branch and Cut Algorithms, Telecommunications Tags , ,

    Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bilayer networks, comparing with Knippel’s previous results. CitationTechnical Reports of the ULB Computer Science Department, … Read more

    Clinic Scheduling Models with Overbooking for Patients with Heterogeneous No-show Probabilities

  • Mark Lawley
  • Ayten Turkcan
  • Bo Zeng
  • Ji Lin
    • Categories Production and Logistics, Scheduling Tags , , ,

    Clinical overbooking is intended to reduce the negative impact of patient no-shows on clinic operations and performance. In this paper, we study the clinical scheduling problem with overbooking for heterogeneous patients, i.e. patients who have different no-show probabilities. We consider the objective of maximizing expected profit, which includes revenue from patients and costs associated with … Read more

    A Two Stage Stochastic Equilibrium Model for Electricity Markets with Two Way Contracts

  • Yue Wu
  • Huifu Xu
  • Dali Zhang
    • Categories Applications - OR and Management Sciences, Complementarity and Variational Inequalities

    This paper investigates generators’ strategic behaviors in contract signing in the forward market and power transaction in the electricity spot market. A stochastic equilibrium program with equilibrium constraints (SEPEC) model is proposed to characterize the interaction of generators’ competition in the two markets. The model is an extension of a similar model proposed by Gans, … Read more

    Pricing with uncertain customer valuations

  • Aurelie Thiele
    • Categories Bound-constrained Optimization, Robust Optimization, Yield Management Tags , ,

    Uncertain demand in pricing problems is often modeled using the sum of a linear price-response function and a zero-mean random variable. In this paper, we argue that the presence of uncertainty motivates the introduction of nonlinearities in the demand as a function of price, both in the risk-neutral and risk-sensitive models. We motivate our analysis … Read more