Applications – OR and Management Sciences

Dynasearch neighborhood for the earliness-tardiness scheduling problem with release dates and setup constraints

  • Francis Sourd
    • Categories Scheduling Tags , ,

    The one-machine scheduling problem with sequence-dependent setup times and costs and earliness-tardiness penalties is addressed. This problem is NP-complete, so that local search approaches are very useful to efficiently find good feasible schedules. In this paper, we present an extension of the dynasearch neighborhood for this problem. Finding the best schedule in this neighborhood is … Read more

    Optimization of Convex Risk Functions

  • Andrzej Ruszczyński
  • Alexander Shapiro
    • Categories Finance and Economics, Stochastic Programming Tags , , , ,

    We consider optimization problems involving convex risk functions. By employing techniques of convex analysis and optimization theory in vector spaces of measurable functions we develop new representation theorems for risk models, and optimality and duality theory for problems involving risk functions. CitationPreprintArticleDownload View PDF

    Solving the uncapacitated multiple allocation hub location problem by means of a dual-ascent technique

  • Lázaro Cánovas
  • Sergio García
  • Alfredo Marín
    • Categories Combinatorial Optimization, Transportation

    This problem deals with the uncapacitated multiple allocation hub location problem. The dual problem of a four-indexed formulation is considered and a heuristic method, based on a dual-ascent technique, is designed. This heuristic, which is reinforced with several specifical subroutines and does not require any external linear problem solver, is the core tool embedded in … Read more

    Solving the Hub Location Problem with Modular Link Capacities

  • Giuliana Carello
  • Hande Yaman
    • Categories Branch and Cut Algorithms, Meta Heuristics, Telecommunications Tags , ,

    This paper deals with a capacitated hub location problem arising in the design of telecommunications networks. The problem is different from the classical hub location problem in two ways: the cost of using an edge is not linear but stepwise and the capacity of an hub restricts the amount of traffic transiting through the hub … Read more

    Envelope Theorems For Finite Choice Sets

  • Somdeb Lahiri
    • Categories Finance and Economics, Game Theory, Multi-Criteria Optimization Tags , , ,

    This paper is concerned with the study of envelope theorems for finite choice sets. More specifically, we consider the problem of differentiability of the value function arising out of the maximization of a parametrized objective function, when the set of alternatives is non-empty and finite. The parameter is confined to the closed interval [0,1] and … Read more

    A Statistical Test for Comparing Success Rates

  • Eric Taillard
    • Categories Applications - OR and Management Sciences Tags ,

    This article presents a non-parametric statistical test that is very interesting for those who want to compare different heuristic algorithms that do not necessarily end with feasible (or satisfying) solutions. This test has been specially designed for working with very small sample sizes, meaning that a substantial computational effort can be saved when conducting numerical … Read more

    Two new proofs of Afriat’s theorem

  • A. Fostel
  • H.E. Scarf
  • Michael J. Todd
    • Categories Finance and Economics, Graphs and Matroids, Linear Programming Tags , ,

    We provide two new, simple proofs of Afriat’s celebrated theorem stating that a finite set of price-quantity observations is consistent with utility maximization if, and only if, the observations satisfy a variation of the Strong Axiom of Revealed Preference known as the Generalized Axiom of Revealed Preference. CitationTechnical Report No. 1381, School of Operations Research … Read more

    The Network Packing Problem in Terrestrial Broadcasting

  • Carlo Mannino
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories Telecommunications Tags , , , , , ,

    The introduction of digital technology all over Europe requires a complete and challenging re-planning of the actual terrestrial broadcasting system. In fact, in order to implement digital networks, transmitters and frequencies must be removed from the current analog networks. On the other hand, the service level (territory coverage) of analog networks must be preserved until … Read more

    New criss-cross type algorithms for linear complementarity problems with sufficient matrices

  • Zsolt Csizmadia
  • Tibor Illés
    • Categories Applications - OR and Management Sciences Tags , , ,

    We generalize new criss-cross type algorithms for linear complementarity problems (LCPs) given with sufficient matrices. Most LCP solvers require apriori information about the input matrix. The sufficiency of a matrix is hard to be checked (no polynomial time method is known). Our algorithm is similar to Zhang’s linear programming, and Akkeleº-Balogh-Illés’s criss-cross type algorithm for … Read more