Meta Heuristics

A General Heuristic Method for Joint Chance-Constrained Stochastic Programs with Discretely Distributed Parameters

  • Eric B. Beier
  • Matthew W. Tanner
    • Categories Basic Sciences Applications, Meta Heuristics, Stochastic Programming Tags , , ,

    We present a general metaheuristic for joint chance-constrained stochastic programs with discretely distributed parameters. We give a reformulation of the problem that allows us to define a finite solution space. We then formulate a novel neighborhood for the problem and give methods for efficiently searching this neighborhood for solutions that are likely to be improving. … Read more

    A novel elitist multiobjective optimization algorithm: multiobjective extremal optimization

  • Min-Rong Chen
  • Yong-Zai Lu
    • Categories Approximation Algorithms, Meta Heuristics, Multi-Criteria Optimization

    Recently, a general-purpose local-search heuristic method called Extremal Optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in multiobjective optimization and proposes a new novel elitist multiobjective algorithm, called Multiobjective Extremal Optimization (MOEO). In order to extend EO to solve the multiobjective … Read more

    Covering models with time-dependent demand

  • Emilio Carrizosa
  • José F. Gordillo
  • Dolores R. Santos-Peñate
    • Categories Applications - OR and Management Sciences, Finance and Economics, Meta Heuristics Tags , , , ,

    In this paper a covering model for locating facilities with time-dependent demand is introduced. Not only the facility locations, but also the instants at which such facilities become operative, are considered as decision variables in order to determine the maximal-profit decision. Expressed as a mixed nonlinear integer program, structural properties are derived for particular demand … Read more

    Hybrid heuristics for the permutation flow shop problem

  • Geraldo R. Mateus
  • Claudio N. Meneses
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • Fabiola G. Nakamura
  • Martín Gómez Ravetti
    • Categories Meta Heuristics, Production and Logistics, Scheduling Tags , , , ,

    The Flow Shop Problem (FSP) is known to be NP-hard when more than three machines are considered. Thus, for non-trivial size problem instances, heuristics are needed to find good orderings. We consider the permutation case of this problem. For this case, denoted by F|prmu|Cmax, the sequence of jobs has to remain the same at each … Read more

    Solving systems of nonlinear equations with continuous GRASP

  • Michael J. Hirsch
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories Global Optimization, Meta Heuristics, Stochastic Approaches Tags , , , , , , , ,

    A method for finding all roots of a system of nonlinear equations is described. Our method makes use of C-GRASP, a recently proposed continuous global optimization heuristic. Given a nonlinear system, we solve a corresponding adaptively modified global optimization problem multiple times, each time using C-GRASP, with areas of repulsion around roots that have already … Read more

    GRASP with path-relinking for network migration scheduling

  • Diogo V. Andrade
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags , , , , , , , ,

    Network migration scheduling is the problem where inter-nodal traffic from an outdated telecommunications network is to be migrated to a new network. Nodes are migrated, one at each time period, from the old to the new network. All traffic originating or terminating at given node in the old network is moved to a specific node … Read more

    A continuous GRASP to determine the relationship between drugs and adverse reactions

  • Michael J. Hirsch
  • Claudio N. Meneses
  • Panos M. Pardalos
  • Mauricio G.C. Resende
  • M. A. Ragle
    • Categories Biomedical Applications, Meta Heuristics, Stochastic Approaches Tags , , , , , , ,

    Adverse drug reactions (ADRs) are estimated to be one of the leading causes of death. Many national and international agencies have set up databases of ADR reports for the express purpose of determining the relationship between drugs and adverse reactions that they cause. We formulate the drug-reaction relationship problem as a continuous optimization problem and … Read more

    A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
    • Categories Applications - OR and Management Sciences, Meta Heuristics Tags , , , , ,

    This paper addresses a constrained two-dimensional (2D) non-guillotine cutting problem, where a fixed set of small rectangles has to be cut from a larger stock rectangle so as to maximize the value of the rectangles cut. The algorithm we propose hybridizes a novel placement procedure with a genetic algorithm based on random keys. We propose … Read more

    Speeding up continuous GRASP

  • Michael J. Hirsch
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories Global Optimization, Meta Heuristics, Stochastic Approaches Tags , , , , , , , ,

    Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2006). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In … Read more

    Approximate resolution of a resource-constrained scheduling problem

  • Jacques Carlier
  • Renaud Sirdey
  • Dritan Nace
    • Categories Meta Heuristics, Scheduling, Telecommunications Tags , , ,

    This paper is devoted to the approximate resolution of a strongly NP-hard resource-constrained scheduling problem which arises in relation to the operability of certain high availability real time distributed systems. We present an algorithm based on the simulated annealing metaheuristic and, building on previous research on exact resolution methods, extensive computational results demonstrating its practical … Read more