Applications – OR and Management Sciences

An Efficient Decomposition Algorithm for Static, Stochastic, Linear and Mixed-Integer Linear Programs with Conditional-Value-at-Risk Constraints

  • Pu Huang
  • Dharmashankar Subramanian
    • Categories Applications - OR and Management Sciences, Robust Optimization

    We present an efficient decomposition algorithm for single-stage, stochastic linear programs, where conditional value at risk (CVaR) appears as a risk measure in multiple constraints. It starts with a well-known nonlinear, convex reformulation of conditional value at risk constraints, and establishes the connection to a combinatorially large polyhedral representation of the convex feasible set induced … Read more

    On the complexity of maximizing the minimum Shannon capacity in wireless networks by joint channel assignment and power allocation

  • Mikael Fallgren
    • Categories Telecommunications Tags ,

    We consider wireless telecommunications systems with orthogonal frequency bands, where each band is referred to as a channel, e.g., orthogonal frequencydivision multiple access (OFDMA). For a snap-shot in time, a joint channel assignment and power allocation optimization problem is presented, both in downlink and in uplink, where the objective is to maximize the minimum total … Read more

    The Balanced Academic Curriculum Problem Revisited

  • Marco Chiarandini
  • Luca Di Gaspero
  • Stefano Gualandi
  • Andrea Schaerf
    • Categories Meta Heuristics, Scheduling

    The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by the universities. In this article, we introduce a … Read more

    Expected Future Value Decomposition Based Bid Price Generation for Large-Scale Network Revenue Management

  • Laureano F. Escudero
  • Dolores Romero Morales
  • Juan F. Monge
  • Jingbo Wang
    • Categories Stochastic Programming, Yield Management Tags , , , ,

    This paper studies a multi-stage stochastic programming model for large-scale network revenue management. We solve the model by means of the so-called Expected Future Value (EFV) decomposition via scenario analysis, estimating the impact of the decisions made at a given stage on the objective function value related to the future stages. The EFV curves are … Read more

    On generalized network design polyhedra

  • Corinne Feremans
  • Martine Labbé
  • Adam N. Letchford
  • Juan-José Salazar-González
    • Categories 0-1 Programming, Polyhedra, Telecommunications Tags , ,

    In recent years, there has been an increased literature on so-called Generalized Network Design Problems, such as the Generalized Minimum Spanning Tree Problem and the Generalized Traveling Salesman Problem. In such problems, the node set of a graph is partitioned into clusters, and the feasible solutions must contain one node from each cluster. Up to … Read more

    A Limited Memory Steepest Descent Method

  • Roger Fletcher
    • Categories Applications - OR and Management Sciences, Unconstrained Optimization Tags , , ,

    The possibilities inherent in steepest descent methods have been considerably amplified by the introduction of the Barzilai-Borwein choice of step-size, and other related ideas. These methods have proved to be competitive with conjugate gradient methods for the minimization of large dimension unconstrained minimization problems. This paper suggests a method which is able to take advantage … Read more

    A Note on Complexity of Traveling Tournament Problem

  • Rishiraj Bhattacharyya
    • Categories Scheduling Tags ,

    Sports league scheduling problems have gained considerable amount of attention in recent years due to its huge applications and challenges. Traveling Tournament problem, proposed by Trick et. al. (2001), is a problem of scheduling round robin leagues which minimizes the total travel distance maintaining some constraints on consecutive home and away matches. No good algorithm … Read more

    A Multi-Product Risk-Averse Newsvendor with Law Invariant Coherent Measures of Risk

  • Sungyong Choi
  • Andrzej Ruszczyński
  • Yao Zhao
    • Categories Production and Logistics, Supply Chain Management Tags , , , ,

    We consider a multi-product newsvendor under the law-invariant coherent risk measures. We first establish a few fundamental properties of the model regarding the convexity of the problem, the symmetry of the solution and the impact of risk aversion. Specifically, we show that for identical products with independent demands, increased risk aversion leads to decreased orders. … Read more

    A Computational Framework for Uncertainty Quantification and Stochastic Optimization in Unit Commitment with Wind Power Generation

  • Mihai Anitescu
  • Emil M. Constantinescu
  • Victor M. Zavala
  • S. Lee
  • M. Rocklin
    • Categories Control Applications, Scheduling, Stochastic Programming Tags , , ,

    We present a computational framework for integrating a state-of-the-art numerical weather prediction (NWP) model in stochastic unit commitment/energy dispatch formulations that account for wind power uncertainty. We first enhance the NWP model with an ensemble-based uncertainty quantification strategy implemented in a distributed-memory parallel computing architecture. We discuss computational issues arising in the implementation of the … Read more

    Exact Solution of Emerging Quadratic Assignment Problems

  • Monique Guignard
  • Peter M. Hahn
  • J. MacGregor Smith
  • Yi-Rong Zhu
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Facility Planning and Design Tags , , ,

    We report on a growing class of assignment problems that are increasingly of interest and very challenging in terms of the difficulty they pose to attempts at exact solution. These problems address economic issues in the location and design of factories, hospitals, depots, transportation hubs and military bases. Others involve improvements in communication network design. … Read more