Meta Heuristics

A hybrid Lagrangean metaheuristic for single machine scheduling problem with sequence-dependent setup times and due dates

  • Carlos Roberto Venâncio de Carvalho
  • Thiago Henrique Nogueira
  • Martín Gómez Ravetti
  • Gabriel Pinheiro Alves Santos
    • Categories Meta Heuristics, Scheduling Tags , , , ,

    In this article, a hybrid Lagrangean metaheuristic is proposed for single machine scheduling problems with sequence-dependent setup times and due dates. The objective function considered throughout this work, is to minimize the total tardiness. Related works and taxonomies for hybrid metaheuristics are analyzed, through a thorough historical overview. The proposed hybrid Lagrangean metaheuristic is a … Read more

    Nonmonotone GRASP

  • Marianna De Santis
  • Paola Festa
  • Giampaolo Liuzzi
  • Stefano Lucidi
  • Francesco Rinaldi
    • Categories Meta Heuristics Tags , , , , ,

    A Greedy Randomized Adaptive Search Procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications … Read more

    Directional Sensor Control: Heuristic Approaches

  • Edwin K.P. Chong
  • Hans D Mittelmann
  • Shankarachary Ragi
    • Categories Control Applications, Meta Heuristics Tags , , ,

    We study the problem of controlling multiple 2-D directional sensors while maximizing an objective function based on the information gain corresponding to multiple target locations. We assume a joint prior Gaussian distribution for the target locations. A sensor generates a (noisy) measurement of a target only if the target lies within the field-of-view of the … Read more

    A Primal Heuristic for MINLP based on Dual Information

  • Armin Fügenschuh
  • Jesco Humpola
  • Thomas Lehmann
    • Categories Applications - Science and Engineering, Constrained Nonlinear Optimization, Meta Heuristics

    We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network’s capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the … Read more

    Optimization Methods for Disease Prevention and Epidemic Control

  • Yan Deng
  • Siqian Shen
  • Yevgeniy Vorobeychik
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Meta Heuristics Tags , , , ,

    This paper investigates problems of disease prevention and epidemic control (DPEC), in which we optimize two sets of decisions: (i) vaccinating individuals and (ii) closing locations, given respective budgets with the goal of minimizing the expected number of infected individuals after intervention. The spread of diseases is inherently stochastic due to the uncertainty about disease … Read more

    Improved Bounds for the Traveling Umpire Problem: A Stronger Formulation and a Relax-and-Fix Heuristic

  • Lucas de Oliveira
  • Cid C. de Souza
  • Tallys H. Yunes
    • Categories Meta Heuristics Tags , , ,

    Given a double round-robin tournament, the traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during the tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team … Read more

    Solving the High School Timetabling Problem to optimality by using ILS algorithms

  • Ademir Aparecido Constantino
  • Haroldo Gambini Santos
  • Wesley Romão
  • Landir Saviniec
    • Categories Meta Heuristics, Scheduling Tags , ,

    The high school timetabling is a classical problem and has many combinatorial variations. It is NP-Complete and since the use of exact methods for this problem is restricted, heuristics are usually employed. This paper applies three Iterated Local Search (ILS) algorithms which includes two newly proposed neighborhood operators to heuristically solve a benchmark of the … Read more

    Biased and unbiased random-key genetic algorithms: An experimental analysis

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
  • Rodrigo F. Toso
    • Categories Meta Heuristics, Optimization Software Benchmark, Stochastic Approaches Tags , , , , , ,

    We study the runtime performance of three types of random-key genetic algorithms: the unbiased algorithm of Bean (1994); the biased algorithm of Gonçalves and Resende (2011); and a greedy version of Bean’s algorithm on 12 instances from four types of covering problems: general-cost set covering, Steiner triple covering, general-cost set K-covering, and unit-cost covering by … Read more

    A Continuous Characterization of the Maximum-Edge Biclique Problem

  • Nicolas Gillis
  • François Glineur
    • Categories Data-Mining, Meta Heuristics Tags , , ,

    The problem of finding large complete subgraphs in bipartite graphs (that is, bicliques) is a well-known combinatorial optimization problem referred to as the maximum-edge biclique problem (MBP), and has many applications, e.g., in web community discovery, biological data analysis and text mining. In this paper, we present a new continuous characterization for MBP. Given a … Read more

    Evolutionary Dynamic Optimization: A Survey of the State of the Art

  • Juergen Branke
  • Trung Thanh Nguyen
  • Shengxiang Yang
    • Categories Meta Heuristics, Optimization Software and Modeling Systems, Other Topics Tags , , , ,

    Optimization in dynamic environments is a challenging but important task since many real-world optimization problems are changing over time. Evolutionary computation and swarm intelligence are good tools to address optimization problems in dynamic environments due to their inspiration from natural self-organized systems and biological evolution, which have always been subject to changing environments. Evolutionary optimization … Read more