ABSTRACT. We study a general class of single-machine scheduling problems with setup time/cost and no idle time in the schedule. It includes a variety of other scheduling and routing problems as special cases. A polynomial size mixed-integer linear programming (MILP) formulation is presented. A tabu search (TS) algorithm, built upon a novel composite-move neighborhood structure, is developed for solving the addressed problem effectively and efficiently.

ABSTRACT. Scheduling conflicting jobs on parallel identical machines is gaining increasing attention in the scientific literature. Among the several possible objective functions proposed so far, we investigate the makespan minimization.

As solution approach we propose a Multi-Neighborhood Search method, which uses three neighborhoods (Move, Swap and 2-Opt, adapted from the Vehicle Routing literature) on an implicit solution representation. The search is guided by a Simulated Annealing metaheuristic.

Experiments show that our method solves small instances consistently to the optimum and outperforms a constraint programming model on larger or highly conflicted instances, in much shorter runtimes.

ABSTRACT. Hexaly Optimizer, formerly known as LocalSolver, is a "model and run" mathematical optimization solver based on various exact and heuristic methods. The presentation will introduce the different components of Hexaly Optimizer’s local search through disjunctive scheduling problems. We will first show how its modeling formalism can be used to express various academic and industrial scheduling problems using interval and list decision variables. The detection of non-overlap constraints in the model provides the solver with valuable information, which can be exploited through various scheduling-specific movements implemented in Hexaly Optimizer’s local search. However, due to the tightness of precedence and non-overlap constraints in good solutions to disjunctive scheduling problems (Job Shop Scheduling Problem, for example), such a small-neighborhood search alone struggles to obtain good performance. Hexaly Optimizer overcomes this issue by reinforcing its local search component with a solution repair algorithm based on constraint propagation. When a move renders the solution infeasible, it is gradually repaired, one constraint at a time, by heuristically shifting the variables just enough to repair. To extend the local transformation rather than cancel it, and to ensure the procedure is fast, we impose never to backtrack on a previous decision to increase or decrease a variable’s value.

ABSTRACT. This is intended to be a technical companion presenting some achievements recently published about the usage of quantum algorithms for the selection of relevant features in a given data set. Based on the paradigm of machine learning, such methods use the concept of mutual information between pairs of observables and between observables and the inferred class, in the special case of a simple classification task. Those probabilistic quantities have been discussed a number of times in several works on information theory. Starting from the paper (Mücke et al., 2023), we provide some further inside about the technical details of their work, with an additional test done on a gate processor using the same binary quadratic approximation model.

ABSTRACT. Several different types of quantum computers are currently available on the market. In theory, it entails a spectrum of promising approaches for designing heuristics for hard discrete optimization problems. However, this variety of hardware, along with the inherent complexity of quantum science, makes it difficult for an operations research scientist to leverage the emerging technology. In this work, we aim to provide a hands-on comparison of three key quantum optimization technologies: quantum annealers, general gate-based quantum computers (in the context of the QAOA framework), and an approach based on Rydberg atoms on a lattice. Specifically, we attempt to design quantum-powered heuristics for TSP, maximum weighted cut, and maximum independent set. We first discuss key high-level steps, including the problem reformulation, pre- and post-processing, coordination between the classical and quantum processing units, and quantum-specific calculations. We show that these key steps strongly depend on the respective quantum hardware, and present a uniform framework that allows us to compare the main hardware restrictions and discuss methodological issues, such as the required number of qubits and dealing with their connectivity. We illustrate these points with a series of experiments involving the three types of quantum processing units.

ABSTRACT. The Quantum Approximate Optimization Algorithm is a hybrid quantum-classic algorithm used for solving combinatorial optimization. However, this algorithm performs poorly when solving the constrained combinatorial optimization problem. To deal with this issue, we consider the warm-start Quantum Approximate Optimization Algorithm for solving constrained problems. This article presents a new method for improving the performance of the Quantum Approximate Optimization Algorithm, with the Difference of Convex Optimization. Our approach focuses on the warm-start version of the algorithm and uses the Difference of Convex optimization to find the warm-start parameters. To show our method's efficiency, we do several experiments on the edge-weighted maximum clique problem and see a good result.

ABSTRACT. In this work, we study a complex variant of the feeder network design problem (FNDP) from the field of maritime transportation. The problem is about designing routes for ship services between several shipping ports, to deliver cargoes between these ports based on a fixed weekly demand. In many cases, this is done using disjoint networks of services, called feeder networks.

Each feeder network is connected to a main port by a long service called a mother route. Some of the paired demands are delivered by the mother route by itself whereas other demands necessitate daughter routes, which are short services that branch off from some ports visited by the mother route.

In the variant of the FNDP studied, we also allow split deliveries of the demands and the rejection of some of the demands. There are time constraints on the routes and on the travel time for delivery of each cargo. We formulate a mathematical model for the problem and propose a matheuristic framework for obtaining high quality solutions.

ABSTRACT. In this paper, we propose a simulated annealing metaheuristic for efficiently solving the Area Coverage (AC) problem in heterogeneous Multistatic Sonar Networks (hMSNs). In this problem, which is new in the literature, the aim is to determine the optimum location for the various sensors making up an hMSN, which is a particular case of Wireless Sensor Network (WSN). More specifically, these networks are made up of a set of acoustic buoys, or sonobuoys, dropped by an airborne carrier and which can be transmitter-only (Tx), receiver-only (Rx) or transmitter-receiver (TxRx). The bistatic case refers to the pairing between a source from a Tx or TxRx buoy and a receiver from another Rx or TxRx buoy which may be kilometres apart from the former, as opposed to the monostatic case where the source and receiver are co-located within the same buoy (i.e. TxRx). In addition, we take into account a certain number of aspects such as coastlines, probabilistic detection models, an undesirable effect called direct blast and variable performance depending on the source/receiver pair under consideration, with some pairings being impossible due to inter-sensor incompatibility (e.g. different operating frequencies).

ABSTRACT. In this work, a Biased Random Key Genetic Algorithm for solving the α-neighbor p-center (ANPC) problem is proposed. One de- coder and one local search procedure are developed, obtaining compet- itive solutions for the problem. The objective of ANPC is to locate p facilities that provide service to n clients and then assign α facilities to each demand point. The objective function is evaluated as the maximum distance to the farthest facility assigned to each client, and the goal is to minimize this maximum distance. The proposed algorithm is com- pared against the best method found in the literature. The performance of the algorithm is evaluated over an extensive instance set, showing the robustness of the proposal.

ABSTRACT. This work proposes a Large Neighborhood Search Metaheuristic for solving a mixed-model assembly line balancing problem with walking workers and dynamic task assignment. The considered problem is a multi-stage stochastic program with integer recourse. These problems are very hard to solve because the number of binary variables increases exponentially with the number of production cycles. We study different decomposition approaches, and our results suggest that re-optimizing for a sub-tree outperforms other decompositions, such as model-based or station decomposition.

ABSTRACT. As a location-allocation problem, the goal of the p-median problem is to find the optimal selection of p medians that results in the minimum total distance from these medians to their assigned objects. The capacitated p-median problem (CPMP) is a version of the p-median problem that sets maximum values for the capacities of the medians in order to fulfill the demand arising from these objects. Considering the numerous application cases of the CPMP, in this paper we propose a large neighborhood search (LNS) algorithm for solving it. We propose and analyze various destruction operators within the framework of LNS to efficiently explore diverse neighborhoods. A MIP solver is used as a repair operator. We evaluated LNS across different data sets available in the literature and show that this method provides very good results for instances up to 5000 facilities. Additionally, our LNS algorithm found new best-known solutions for several evaluated instances.

ABSTRACT. The Bus Driver Scheduling Problem (BDSP) is a combin- atorial optimisation problem with high practical relevance. The aim is to assign bus drivers to predetermined routes while minimising a specified objective function that con- siders operating costs as well as employee satisfaction. Since we must satisfy several rules from a collective agreement and European regulations, the BDSP is highly constrained. Hence, using exact methods to solve large real-life-based instances is computationally too expensive, while heuristic methods still have a considerable gap to the optimum. Our pa- per presents a Large Neighbourhood Search (LNS) approach to solve the BDSP. We propose several novel destroy operat- ors and an approach using Column Generation to repair the sub-problem. We analyse the impact of the destroy and repair operators and investigate various possibilities to select them, including adaptivity. The proposed approach improves all the upper bounds for larger instances that exact methods cannot solve, as well as for some mid-sized instances, and outper- forms existing heuristic approaches for this problem on all benchmark instances.

ABSTRACT. In this work we consider a new variant of the Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP). The proposed variant incorporates two different features which are frequently present in many real projects: time-dependent resource costs and time-varying resource capacities. The former entails that costs depend on the time a resource is used, while the latter implies that resource availability is given for each period of the planning horizon. Furthermore, we adopt a multi-objective framework, with the objectives of minimizing the makespan and the total cost for resource usage. A mathematical formulation is presented for this problem, and an attempt is made to solve it using an exact method to find the Pareto front (PF). Nonetheless, the intractability of the optimization model underlying the problem motivates the development of a metaheuristic to approximate the PF. Building upon a previously proposed genetic algorithm for the MRCPSP, we design the solution encoding and genetic operators to accommodate the new elements of the problem. Moreover, we enhance the fitness function for infeasible individuals in the current multi-objective scenario. We have conducted computational experiments using instances built from those available in the literature. The results illustrate the good performance of the algorithm proposed.

ABSTRACT. Inspired by the well-known ``Feasibility Pump'' heuristic designed for the single objective optimization, we have introduced in 2021 a primal matheuristic, named ``Gravity Machine'' (GM) for computing an upper bound set for generic multi-objective linear optimization problems defined by binary variables and p objectives (p-01LP).

GM does not exploit any information coming from the combinatorial structure of the problem. Sober in memory and computational resources, and given a time limit, the algorithm explores a p-01LP problem in order to discover a tight upper bound set, without guarantee of returning such a set.

The contributions discussed here a twice. First, we extend the single objective heuristic by replacing the LP relaxation by mixed LP relaxation which is stronger with extra among of CPU time and adding pseudo cuts to it in order to avoid cycling. Next, we exploit this version of the heuristic in solving a sequence of mono-objective optimization problems, obtained by aggregating the original p objectives, bounded by cones constraints.

Finally, the experimented variants of GM algorithm are described, and numerical results obtained on instances of set partitioning problem available on the OR-library, extended to two objectives, are reported.

ABSTRACT. Julia is a programming language suitable for data analysis and scientific computing that combines simplicity of productivity languages with characteristics of performance-oriented languages. In this paper, we are interested in studying the use of Julia to implement Multi-Objective MetaHeuristics. Concretely, we use the Java-based jMetal framework as a reference support and investigate how Julia could be used to design and develop the component-based architecture for multi-objective evolutionary algorithms that jMetal provides. By using the NSGA-II algorithm as an example, we analyze the advantages and shortcomings of using Julia in this context, including aspects related to reusing jMetal code and a performance comparison.

ABSTRACT. Search Trajectory Networks (STNs) are visualizations of directed graphs designed to analyze the behavior of stochastic optimization algorithms such as metaheuristics. Their purpose is to provide researchers with a tool that allows them to gain a deeper understanding of the behavior exhibited by multiple algorithms when applied to a specific instance of an optimization problem. In this short paper, we present two examples of our work in which STN graphics have helped us to discover interesting and useful algorithm/problem characteristics.

ABSTRACT. This study explores the use of Autoregressive Integrated Moving Average (ARIMA) and Long Short-Term Memory (LSTM) machine learning models in metaheuristic algorithms, with a focus on a modified General Variable Neighborhood Search (GVNS) for the Capacitated Vehicle Routing Problem (CVRP). We analyze the historical chain of actions in GVNS to demonstrate the predictive potential of these models for guiding future heuristic applications or parameter settings in metaheuristics such as Genetic Algorithms and Simulated Annealing. This "optimizing the optimizer" approach reveals that, the history of actions in metaheuristics provides valuable insights for predicting and enhancing heuristic selections. Our preliminary findings suggest that machine learning models, using historical data, offer a pathway to more intelligent and data-driven optimization strategies in complex scenarios, marking a significant advancement in the field of combinatorial optimization.

ABSTRACT. In the realm of optimization, where intricate landscapes conceal possibly hidden pathways to high-quality solutions, STNWeb serves as a beacon of clarity. This novel web-based visualization platform empowers researchers to delve into the intricate interplay between algorithms and optimization problems, uncovering the factors that influence algorithm performance across diverse problem domains, be they discrete/combinatorial or continuous. By leveraging the inherent power of visual data representation, STNWeb transcends traditional analytical methods, providing a robust foundation for dissecting algorithm behavior and pinpointing the mechanisms that elevate one algorithm above another. This visually-driven approach fosters a deeper understanding of algorithmic strengths and weaknesses, ultimately strengthening the discourse surrounding algorithm selection and refinement for complex optimization tasks.

ABSTRACT. The Flow-Shop Scheduling Problem (FSSP) is one of the most famous scheduling problems. The Flow-Shop scheduling problem is a disjunctive problem, meaning that a solution is fully described by an oriented disjunc-tive graph where the earliest starting times are computed with a longest path algorithm. We propose a new approach based on Quantum Approximate Op-timization Algorithm (QAOA) to find high quality solutions to FSSP in-stances using a vector representation. This approach permits to solve the well-known Carlier's instances with 64 operations to schedule. All the exper-iments have been achieved using the Qiskit library and carried on the IBM simulator. Presently, quantum methods cannot compete with classical ones because we lack quantum computers capable of solving large instances, and we have yet to figure out how to integrate the vast body of research results accumulated in flow-shop resolution over the last few decades into quantum algorithms. The ability of quantum approaches to effectively solve optimiza-tion problems in the future depends both on technical advancements in quantum machines and on the capacity to incorporate theoretical findings from scheduling into quantum optimization strategies.

ABSTRACT. We consider solving the Job Shop Scheduling Problem with machine unavailability constraints using an analog quantum machine running the quantum annealing metaheuristic. We propose a technique to handle these new constraints, whether the unavailability periods are known or variable, in order to integrate them into the same type of disjunctive model processed by the analog machine: Binary, Unconstrained, and Quadratic. We present results on small-scale instances corresponding to what these quantum machines can handle.

ABSTRACT. The Quantum Approximate Optimization Algorithm is the hybrid classic-quantum algorithm that is used for solving the combinatorial optimization problem. However, the algorithm performs poorly in the constrained combinatorial optimization problem because it considers all solutions with the same initial probability. In this article, we propose a new quantum state that improves the QAOA performance and does not require slack variables for inequality constraints. We also introduce some properties of our new quantum state in solving a constrained combinatorial optimization problem. To see our method's efficiency, we use our method to solve the quadratic knapsack problem and compare it with the quantum state of Hao \cite{hao2022exploiting} which is one of the best methods for solving the constrained combinatorial optimization.

ABSTRACT. Obnoxious facility location problems are devoted to choose the best location for a given set of facilities considering that, despite they should not be close to population communities, their service is needed, like the case of airports, paper factories or nuclear plants. In this paper we study the planar multiple obnoxious facility location problem. Our approach is based on a first discretization of the instance where a Basic Variable Neighborhood Search algorithm is applied. Our results improve the state of the art spending less than a third of the execution time of the second best algorithm.

ABSTRACT. Facility layout problems represent a challenge to the operations research community. These problems are closely related to real-world scenarios in industry and society, such as the design of production factories or the layout of facilities in medical centers, to name a few. These scenarios have been studied from the theoretical point of view as different optimization problems. Among them, we have studied the T-Row Facility Layout Problem, which considers a layout formed by two orthogonal rows where facilities have to be placed minimizing the material handling cost. To efficiently solve this problem we propose a Variable Neighborhood Search algorithm which is able to reach all the optimal solutions reported in the literature spending a fraction of the execution time of the previous algorithm.

ABSTRACT. Variable Neighborhood Search (VNS) has reached its 25th anniversary as an effective and accessible metaheuristic for combinato- rial optimization. This paper explores how VNS’s ingenious method to escape local optima exhibits the properties of interpretability, adaptabil- ity and scalability, making it well-suited for tackling large and complex real-world problems. We first outline how the simple, modular design of VNS lends itself to insightful problem analysis and systematic formula- tion of the search space. We then discuss how VNS organically integrates with other methods as a hybrid and readily leverages parallelization and AI/ML capabilities for scalability. Finally, we propose recommendations to further advance VNS through establishing public code repositories and problem libraries, documenting challenges and successes with real-world implementations, actively engaging across metaheuristics, and popular- izing VNS as an accessible optimization technique.

ABSTRACT. Metaheuristic hybrids equipped with multiple restarts have shown promise in complex optimization problems. A critical challenge in this domain, particularly for exploration-only exploitation-only hybrids, is determining optimal transition points between algorithms and restart locations. Each component of these hybrids excels in a specific task but may underperform in others, making transition and restart decisions crucial. This paper introduces an innovative solution to these challenges using reinforcement learning. We apply this approach to the UES-CMAES hybrid, training reinforcement learning agents to intelligently manage algorithm transitions and restarts. Evaluation on the CEC'13 benchmark suite demonstrates the efficacy of this method, indicating significant improvements in optimization performance. Our findings not only confirm the potential of reinforcement learning in enhancing metaheuristic hybrids but also pave the way for new research directions in intelligent optimization strategies.

ABSTRACT. This work leverages reinforcement learning for designing a new variant of Construct, Merge, Solve and Adapt (CMSA), a rather new hybrid metaheuristic for combinatorial optimization. We demonstrate a twofold improvement over the standard CMSA. Firstly, the new variant simplifies CMSA by eliminating the need for a greedy function to probabilistically generate solutions. Additionally, it performs better, as we demonstrate in the context of the Minimum Dominating Set (MDS) problem.

ABSTRACT. This study introduces an innovative optimization technique rooted in hybridizing the Golden Sine Algorithm II and the Non - Monopolized Search algorithm tailored to address unconstrained problems. The core concept underlying Golden Sine Algorithm II hinges on leveraging the diminishing pattern of the sine function and the golden ratio to navigate the solution landscape effectively; meanwhile, the Non-Monopolized Search is employed to improve the exploitation as a local search mechanism. Our proposal is called improved Golden Sine Algorithm II with Non-Monopolized Local Search (GSII-LS). Notably, GSII-LS is designed to complement and enhance existing optimization methodologies, working in synergy with non-monopolizing search strategies. To assess its efficacy, GSII-LS is subjected to rigorous testing across 34 benchmark functions for unconstrained optimization. Comparative analysis against optimization algorithms is conducted using established evaluation criteria. Results demonstrate that GSII-LS consistently achieves superior convergence towards global optima across numerous benchmark functions.

ABSTRACT. In the competitive passenger air transport market, low-cost airlines continue strengthening their position, contrasting sharply with traditional carriers. This article delves into the unique operational strategies of these airlines, focusing on their reliance on ancillary services. Among these services, seat selection stands out as a crucial revenue enhancer. The study emphasizes the importance of low-cost carriers ensuring the availability of specific seats for direct purchase, thereby avoiding their allocation through automatic seat assignment algorithms, commonly activated for passengers who do not opt for specific seating. A notable consumer behaviour observed is the preference for passengers on the same booking to be seated together. This work presents a novel approach to the seat assignment problem based on a GRASP algorithm; this approach is beneficial due to its low requirement for extensive parameter calibration, intuitive nature, and adaptability to different airline scenarios. Using an actual flight database of a low-cost Colombian airline, we have compared the airline's rule-based heuristics, a network flow model, and our metaheuristic approach; the results obtained are satisfactory in terms of solution quality and computational cost. The proposed solution offers a viable, cost-effective alternative to specialized software solutions, aligning with the financial constraints typical of low-cost carriers.

ABSTRACT. This paper introduces a problem-independent GRASP metaheuristic for combinatorial optimization implemented as a random-key optimizer (RKO). CGRASP, or continuous GRASP, is an extension of the GRASP metaheuristic for optimization of a general objective function in the continuous unit hypercube. The novel approach extends CGRASP using random keys for encoding solutions of the optimization problem in the unit hypercube and a decoder for evaluating encoded solutions. This random-key GRASP combines a universal optimizer component with a specific decoder for each problem. As a demonstration, it was tested on five NP-hard problems: Traveling salesman problem (TSP); Tree hub location problem in graphs (THLP); Steiner triple set covering problem (STCP); Node capacitated graph partitioning problem (NCGPP); and Job sequencing and tool switching problem (SSP).

ABSTRACT. Introduced in 1989, GRASP is a metaheuristic designed around two steps: construction and improvement of solutions. This talk presents a feedback on three topics related to GRASP that we have investigated.

The first one is issued from a personal discussion held during MIC'97 with Ibrahim Osman about the use of GRASP for multi-objective optimisation. It has given birth to a construction-deconstruction mechanism presented in 1998, with an experimentation on the set covering problem. It has been compared much later with LNS, both presenting some similarities.

The second topic belongs also in the context of multi-objective optimization, where the aim is to exploit the strong features of GRASP in combination of evolutionary algorithms and local search. It has giving birth to a methodology in three steps named peek-shape-grab where the construction step of GRASP is the operational implementation of the peek stage.

The last topic is issued from an in-depth study on Reactive GRASP, the component devoted to the automatic tuning of the alpha parameter value. Experimented on instances of set packing problem, the procedure introduced by Prais and Ribeiro in 2000 is observed and tentatives to strengthen the tuning is investigated.