Search

This paper introduces the three‐dimensional case picking problem (3D‐CPP) and proposes a multistart biased‐randomized algorithm (BRA) to solve it. The 3D‐CPP combines two important topics in modern warehouse logistics: the pallet loading problem and the routing of pickers in manual warehouses. The proposed optimization procedure aims at minimizing the overall distance traveled by the pickers, and is achieved by combining a routing problem (i.e., the order in which picking positions are visited) with a loading problem (i.e., the way in which cases are placed onto the pallet). We also consider additional constraints regarding the weight, vertical support, and strength of the cases. In order to solve this problem, we first propose a constructive heuristic which combines routing and packing procedures. This initial heuristic is then extended into a multistart BRA by employing a skewed probability distribution to introduce a certain degree of randomness during the solution‐construction process. A series of computational experiments allow us to assess the quality of the proposed approach, through a comparison with other algorithms as well as using real‐life data provided by an industrial partner. [ABSTRACT FROM AUTHOR]

The Algorithm Selection Problem (ASP) considers the use of previous knowledge regarding problem features and algorithm performance to recommend the best strategy to solve a previously unseen problem. In the application context, the usual ASP for optimization considers recommending the best heuristics, whenever it faces a new similar problem instance, also known as the Per-Instance ASP. Although ASP for heuristic recommendation is not new, selecting heuristics and also their parameters, or the Per-instance Algorithm Configuration Problem, is still considered a challenging task. This paper investigates the use of meta-learning to recommend six different stochastic local searches and their parameters to solve several instances of permutation flowshop problems. The proposed approach uses several problem features, including fitness landscape metrics, builds the performance database using irace, and trains different multi-label recommendation models on a data set with more than 6000 flowshop problem instances. Experiments show that decision tree-based machine learning models achieve good performance, and the quality of the recommendations is capable of outperforming the state-of-the-art algorithm with tuned configuration. [ABSTRACT FROM AUTHOR]

A software product line (SPL) is a software engineering reusability approach used to create different applications from a shared set of common software features. The product configuration problem (PCP) consists in finding the product, among all the products allowed by the SPL, that best fits the customer's preferences and requirements. PCP is a generalization of the tree knapsack problem (TKP) with additional AND, XOR, and OR constraints. Therefore, this problem is also NP‐hard. Previous work in the literature could solve only instances with up to 500 features. In this paper, we propose a pseudo‐polynomial time dynamic programming algorithm that solves PCP in O(nH)$O(nH)$, where n is the number of features and H is the customer's budget. We also propose an integer linear programming formulation for PCP, which is solved by the CPLEX's branch‐and‐bound algorithm. Computational experiments, performed on realistic instances from the literature, showed that the proposed algorithms were able to find optimal solutions for all the instances with up to 10,000 features. [ABSTRACT FROM AUTHOR]

In financial markets, investors may be forced to unwind their portfolios to meet a determined leverage ratio within regulatory policy or risk management requirements. This paper studies the optimal portfolio liquidation problem with market impact. Some new insights are given into this problem, and trading orders are discussed for various financial parameters. Specifically, we establish the equivalence between equity and liability maximization. This means if one wants to maximize the equity, it is to maximize the liability and vice versa. The computational complexity of the problem is examined to be NP‐hard. We expose the hidden convexity through monotonicity analysis and linearization techniques. Although good properties are established for the Lagrangian algorithm, a counter‐example is constructed to show one deficiency of this algorithm. Therefore, we propose an augmented Lagrangian algorithm for solving the problem. The inverse Hessian of the augmented Lagrangian function is explicitly calculated for the subproblem solved by the projected Newton method. Meanwhile, we consider how to choose a good initial point, which is essential for seeking a high‐quality solution. Some numerical results are presented, which validate the usefulness of the augmented Lagrangian algorithm. [ABSTRACT FROM AUTHOR]

Value‐at‐risk (VaR) is a widely acceptable risk measure in finance and particularly, in the portfolio selection problem (PSP). However, due to the non‐convexity, its incorporation into an optimization model makes it challenging and difficult to solve. Hence, the development of iterative‐based heuristic algorithms (IBHAs) utilizing the problem structure would be valuable. The existing IBHAs are either inefficient in terms of solution quality and running time or are just applicable to solve simple PSPs without any real‐world constraint (i.e., cardinality, position size, and transaction cost constraints). To overcome these shortcomings, in this paper, we present a novel IBHA to efficiently solve the PSP with real‐world constraints under VaR measure. Our method is based on iterative resolution of two restricted versions of the original model in which some of the binary variables utilized in the formulation of VaR measure are fixed at specific values. Computational experiments over real‐world instances indicate that not only the running time of our algorithm is short, but also its solution quality is much better than the existing IBHAs in 97% of instances with an average improvement of about 10%. [ABSTRACT FROM AUTHOR]

The Multi-Objective Bike Routing Problem (MOBRP) addressed in this paper consists in finding a set of good solutions that represents the trade-off between cyclist preferences when choosing a route. We propose a new genetic approach to solve the MOBRP (NGA-MOBRP) with a new mutation operator. To test the approach, we consider four conflicting criteria: safety, travel distance, travel time, and comfort. The well-known Nondominated Sorting Genetic Algorithm II (NSGA-II) is also implemented in the MOBRP context, and its weaknesses are identified and mitigated in the proposed NGA-MOBRP. The developed approach is compared with other published works in this field, namely another genetic algorithm and a Multi-Objective Simulated Annealing (MOSA) approach. The computational results show that the approach developed in this work obtains better results than the previously mentioned published approaches. [ABSTRACT FROM AUTHOR]

This paper presents a new formulation for the routing problem in which the available fleet consists of trucks and trailers divided into compartments. Solving the model for large instances is computationally expensive. Therefore, we introduce and implemented a two-phase heuristic algorithm. In the first phase, an initial solution is generated through a constructive heuristic algorithm based on concepts from the classic Clarke–Wright algorithm. In the second phase, the initial solution is improved by an iterated tabu search metaheuristic. Our algorithm was tested on 21 instances that were converted from the classic truck and trailer routing problem. The results of our computational study prove the effectiveness of our proposal; the algorithm always finds a feasible solution, which in small-sized problems it is proven to be of good quality. In addition, the algorithm outperforms previous approaches for some truck and trailer routing problem instances. Furthermore, an application of the proposed model and heuristic is demonstrated in the field of agricultural logistics by comparing the obtained results. [ABSTRACT FROM AUTHOR]

The Traveling Purchaser Problem (TPP) is a generalization of the TSP that consists in choosing which nodes (markets) to visit to create a tour that allows to buy a set of products at minimum transportation and purchasing cost. The TPP has gained attention due to the computational challenges it poses and the potential applications it can support in today’s technology-driven industry. This paper presents a GRASP-based methodology for the TPP based on three constructive procedures (route-first, purchase-first, and purchase-and-route) and two local search operators (insert and remove). The methodology is strengthened with a Path Relinking strategy to improve the GRASP performance by re-combining a set of elite solutions and with a Filtering strategy to improve the algorithm’s efficiency by avoiding local search operations on the least promising solutions. The algorithm is tested with 855 instances of the asymmetric TPP and 190 instances of the symmetric TPP. Computational results prove the benefit of including the Path Relinking and Filtering strategies and suggest that the purchase-first constructive procedure is the most competitive in terms of objective function value with little extra effort in execution time with respect to the other constructive procedures. Our results outperform published results for the asymmetric TPP in a statistically significant way and show competitive performance for the symmetric TPP. [ABSTRACT FROM AUTHOR]

Grammar‐based automatic algorithm design has been shown to generate stochastic local search algorithms that compete with or outperform state‐of‐the‐art methods. In such systems, algorithms are divided in components and a grammar is used to describe how to properly combine the components to create a working algorithm. In our approach, the grammar is converted into parameters and an automatic parameter configuration tool is used to find the best configuration. This approach allows us to consider and hybridize different metaheuristic templates producing combinations never tested before, but this flexibility leads to a very large configuration space to explore. Is such complexity really needed to achieve state‐of‐the‐art performance? In this paper, we investigate this question by creating grammars that allow the hybridization of stochastic local search algorithms at most two, one, or zero times. We use these grammars to generate algorithms for the three most studied objectives of the permutation flowshop problem: makespan, total completion time, and total tardiness. The generated algorithms are compared using benchmark sets from the literature as well as a quantitative measure of algorithm complexity using a metric based on concept directed acyclic graphs. The experiments show that our system tends to generate hybridized algorithms only when they can provide a substantial performance improvement. On the contrary, when such algorithms do not improve performance, the system generates simpler algorithms regardless of the grammar used. [ABSTRACT FROM AUTHOR]

In this paper, we propose an extension of the uncapacitated hub location problem where the potential positions of the hubs are not fixed in advance. Instead, they are allowed to belong to a region around an initial discrete set of nodes. We give a general framework in which the collection, transportation, and distribution costs are based on norm‐based distances and the hub‐activation setup costs depend not only on the location of the hub that are opened but also on the size of the region where they are placed. Two alternative mathematical programming formulations are proposed. The first one is a compact formulation while the second one involves a family of constraints of exponential size that we separate efficiently giving rise to a branch‐and‐cut algorithm. The results of an extensive computational experience are reported showing the advantages of each of the approaches. [ABSTRACT FROM AUTHOR]

Probabilistic linguistic large‐group decision‐making (LGDM) is becoming a hot topic in the field of decision science. In general, clustering and consensus‐reaching are the two important processes to deal with LGDM problems. Traditional clustering methods are mainly based on opinion similarity measures and cannot directly control the number of decision makers (DMs) that can be contained in a cluster. Situations of noncooperative behavior toward consensus may be encountered during the consensus‐reaching process. This paper first proposes a distance‐to‐center clustering algorithm to classify the large group. The most important characteristic of the algorithm is that it is based on similarity measures of probabilistic linguistic information, and specifies the upper and lower limits on the number of DMs in the cluster. Then, a novel weight‐determining method is developed that considers the size, external consensus level, and inner consensus level of a cluster. A punishment‐driven consensus model is designed to manage opinion differences and noncooperative behaviors. Finally, the proposed clustering algorithm and consensus model are applied to a case study of car‐sharing platform selection. The results and comparative analysis reveal the potential application and effectiveness of this study. [ABSTRACT FROM AUTHOR]

Logistics problems lie at the core of industries' everyday operations. These types of problems are also one of the main points of interest in the operational research field of study. In recent years, the workforce scheduling and routing problems (WSRP) class of optimization problems has gained significant attention from researchers. In this paper, a recently proposed WSRP is studied: the multiperiod WSRP with dependent tasks. In this problem, a given company provides services by means of heterogeneously skilled mobile teams. Service requests are known beforehand and each service is composed of one or more activities. Execution of one activity may depend on the completion of another. A feasible schedule in which the requested activities are completed in the minimum amount of days must be provided. Two matheuristic algorithms are proposed. Several new upper bounds for a set of instances from the literature are discovered. [ABSTRACT FROM AUTHOR]

In this paper, a periodic order‐up‐to‐level policy is developed by using a Markovian approach. Customer demand is modeled by using an empirical distribution. Unmet customer demand is considered as lost sales. The internal storage capacity is limited, and excessive units are stored in external storage space. Replenishment lead time is discrete and stochastic. Because of the characteristics of the demand and lead time, the demand during the lead time and the demand during the protection interval are empirical. The Markovian approach is used to estimate the system measures of performance, including the expected inventory on‐hand, expected lost sales, and expected over‐storage. The successive overrelaxation algorithm is implemented to overcome the dimensional issue of the Markov model. The optimal policy that minimizes the total cost is obtained by using a customized golden section search procedure. The proposed method is applied to a real dataset of consumable products. In addition, the effectiveness of the approach is demonstrated by a comparison with a simulation. The results indicate that the model from our approach can accurately describe the behavior of the periodic order‐up‐to‐level review system. [ABSTRACT FROM AUTHOR]

In market basket analysis (MBA), the goal is to understand human behavior to maximize sales. A clear behavior is buying correlated items. As a consequence, the determination of a set of items with a high correlation with others is a valuable tool for MBA. In this work, we address a combinatorial optimization problem with valuable applications to MBA, especially in marketing and product placement. The focus will be on the combinatorial problem and not on specific applications. For any given undirected graph G=(V,E) (where the nodes are items and the edges represent correlation), we aim to find the clique C⊆V such that the number of edges shared between C and V−C is maximized. This problem is known in the literature as the max cut‐clique (MCC) problem. We can generalize this problem by considering the weights associated with each edge. In this context, we are interested in finding the clique C⊆V such that the weighted sum associated with each edge shared between C and V−C is maximized. The weighted version of the MCC problem is known as the maximum edge‐weight neighborhood clique (MEWNC) problem. The main contributions of this paper are threefold. First, the computational complexity of both the MCC and MEWNC problems is established. Specifically, we prove that the MCC and MEWNC problems belong to the class of NP‐complete problems. Second, an exact integer linear programming (ILP) formulation for the MEWNC problem is proposed. Third, a full greedy randomized adaptive search procedure/variable neighborhood descent methodology enriched with a tabu search is here developed, where the main components are novel neighborhood structures and a restricted candidate list that trade greediness for randomization in a multistart fashion. A dynamic tabu list considers a bounding technique based on the previous analysis. Finally, a fair comparison between our hybrid algorithm and a globally optimal solution using the ILP formulation confirms that a globally optimal solution is found by our heuristic for graphs with hundreds of nodes, but it is more efficient than the exact solution in terms of time and memory requirements. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of multirobot search for a stationary object in an a priori known environment. Two variants of the problem are studied given the working environment represented by a graph. The first variant is an extension of the traveling deliveryman problem for multiple vehicles, while the second variant is a generalization of the graph search problem. A novel algorithm is presented to solve both problems, which is based on a combination of greedy randomized adaptive search procedure with variable neighborhood descent. A set of experimental evaluations were conducted over the benchmark instances derived from the TSPLIB library. For both problems, the results obtained show that the proposed approach is comparable to state‐of‐the‐art heuristics. Moreover, for problems of a few hundred vertices, the solution times suggest that the approach is suitable for online decision‐making in search and rescue. [ABSTRACT FROM AUTHOR]

This paper presents a variable neighborhood search (VNS) algorithm to solve the extension of the orienteering problem known as the generalized orienteering problem (GOP). Our algorithm aims to use a reduced number of neighborhoods without compromising the quality of the results. This reduced number of neighborhoods, together with the precalculation of scores associated with points of interest, allows us, in most cases, to outperform all previous metaheuristics proposed for this problem. This is the first time a VNS is being applied to the GOP, and it provides promising computational results. In particular, in the case studies considered in the paper, we were able to find 35 new best solutions, all of which were found using a shorter computational time. Furthermore, the information regarding other best‐known solutions provided in the literature has also been improved, with corrections to some previously published errors regarding scores and distances. In addition, the benchmark has been extended with the incorporation of new case studies based on real data from three of the most popular tourist cities in Spain. [ABSTRACT FROM AUTHOR]

This special issue is based on the program area "Decision support" of the EURO 2021 conference held online and on-site in Athens, Greece, on July 11-14, 2021. It contains papers presented at the conference and later submitted for this special issue, as well as additional papers submitted in response to an open call for papers after the conference. [Extracted from the article]

The eigenvalues of tensors become more and more important in the numerical multilinear algebra. In this paper, based on the nonmonotone technique, an accelerated Levenberg–Marquardt (LM) algorithm is presented for computing the B‐eigenvalues of symmetric tensors, in which an LM step and an accelerated LM step are computed at each iteration. We establish the global convergence of the proposed algorithm using properties of symmetric tensors and norms. Under the local error‐bound condition, the cubic convergence of the nonmonotone accelerated LM algorithm is derived. Numerical results show that this method is efficient. [ABSTRACT FROM AUTHOR]

Convex semi‐definite semi‐infinite programming problems (SDSIP) represent a special class of distributionally robust optimization (DRO) problems with a wide range of applications in engineering and economics. In this paper, we propose a modified exchange algorithm for convex SDSIP that arises from DRO with matrix moment constraints. We first explore the convergence results of the modified exchange algorithm and perform the efficiency analysis based on a set of benchmark tests. In addition, we apply the SDSIP framework to investigate an optimized certainty bound risk with an ambiguity uncertainty set and implement the algorithm to solve a practical risk minimization problem in portfolio selection. The empirical results show both the efficiency of the algorithm and the robustness of the risk measure. [ABSTRACT FROM AUTHOR]

This paper analyzes the permutation flow‐shop problem with delivery dates and cumulative payoffs (whenever these dates are met) under uncertainty conditions. In particular, the paper considers the realistic situation in which processing times are stochastic. The main goal is to find the permutation of jobs that maximizes the expected payoff. In order to achieve this goal, the paper first proposes a biased‐randomized heuristic for the deterministic version of the problem. Then, this heuristic is extended into a metaheuristic by encapsulating it into a variable neighborhood descent framework. Finally, the metaheuristic is extended into a simheuristic by incorporating Monte Carlo simulations. According to the computational experiments, the level of uncertainty has a direct impact on the solutions provided by the simheuristic. Moreover, a risk analysis is performed using two well‐known metrics: the value‐at‐risk and conditional value‐at‐risk. [ABSTRACT FROM AUTHOR]

In this paper, we demonstrate that, through policy interventions, in the form of subsidies, a system‐optimum for a multiclass human migration network can be achieved, despite the migrants, who can be refugees, behaving in a user‐optimized manner. The formulation and analysis are conducted using variational inequality theory. The policy intervention allows governmental decision‐makers to moderate the flow of migrants while enhancing societal welfare. An algorithm is proposed and applied to compute the solutions to a series of numerical examples, with changes in initial populations and utility functions, inspired by a pandemic, followed by a natural disaster. [ABSTRACT FROM AUTHOR]

Even though it is well known that for most relevant computational problems, different algorithms may perform better on different classes of problem instances, most researchers still focus on determining a single best algorithmic configuration based on aggregate results such as the average. In this paper, we propose integer programming‐based approaches to build decision trees for the algorithm selection problem. These techniques allow the automation of three crucial decisions: (a) discerning the most important problem features to determine problem classes, (b) grouping the problems into classes, and (c) selecting the best algorithm configuration for each class. To evaluate this new approach, extensive computational experiments were executed using the linear programming algorithms implemented in the COIN‐OR branch‐and‐cut solver across a comprehensive set of instances, including all MIPLIB benchmark instances. The results exceeded our expectations. While selecting the single best parameter setting across all instances decreased the total running time by 22%, our approach decreased the total running time by 40% on average across 10‐fold cross‐validation experiments. These results indicate that our method generalizes quite well and does not overfit. [ABSTRACT FROM AUTHOR]

This paper investigates single‐machine scheduling in which the processing time of a job is a function of its position in a sequence, a truncation parameter, and its resource allocation. For a convex resource consumption function, we provide a bicriteria analysis where the first is to minimize total weighted flow (completion) time, and the second is to minimize total resource consumption cost. If the weights are positional‐dependent weights, we prove that three versions of considering the two criteria can be solved in polynomial time, respectively. If the weights are job‐dependent weights, the computational complexity of the three versions of the two criteria remains an open question. To solve the problems with job‐dependent weights, we present a heuristic (an upper bound) and a branch‐and‐bound algorithm (an exact solution). [ABSTRACT FROM AUTHOR]

The prize‐collecting generalized minimum spanning tree problem consists of finding a minimum cost spanning tree in an undirected graph, considering that the vertices are divided into clusters, that there is a nonnegative cost associated with each edge, that there is a prize to be collected on each vertex, and that only one vertex of each cluster belongs to the tree. Due to its NP‐hardness, this problem remains a computational challenge even for small instances, and the practical applications that arise in telecommunication networks can attain large dimensions. The state‐of‐the‐art algorithm finds good solutions for several instances; however, the quality of solutions and the computing time for large instances remain to be improved. We propose an iterated local search algorithm that works on a two‐level solution approach, taking advantage of the structure of the problem. The first‐level subproblem aims to select a vertex for each cluster, and the second‐level subproblem addresses the determination of the minimum spanning tree covering such vertices. The performance of the resulting algorithm is evaluated with the most challenging instances from the literature, comparing the results with the state‐of‐the‐art algorithm. The computational experiment conducted shows that, both in existing instances and in a new group of instances presented in this paper, the proposed algorithm outperforms the state‐of‐the‐art algorithm. [ABSTRACT FROM AUTHOR]

The runway is a key airport resource and an efficient runway operation is critical to enhance the airport efficiency and to reduce delays. This paper addresses the problem of scheduling aircraft departures incorporating arrival crossings. Constraints for wake turbulence separations, flight time window restrictions, and holding queue capacity at runway threshold are explicitly considered. We present two integer linear programming models and a simulated annealing (SA) algorithm. Comparison tests are conducted for the south side of Paris Charles De Gaulle Airport and show that the three proposed methods can significantly improve the solutions based on the simple first‐come‐first‐served rule. Moreover, SA has sufficiently small computation time for real‐time deployment. [ABSTRACT FROM AUTHOR]

Abstract: Managing ticket reservations in passenger rail transport is a complex task. A hybrid algorithm is developed as a decision support tool. The aim of the proposed algorithm is to provide real‐time decisions on seat inventory allocation taking into account relevant information from the past. This paper considers the revenue management application in passenger rail transport with variable capacity of sleeping cars. Uncertainty of capacity availability is embedded in the developed algorithm through a payoff table, while an Artificial Neural Network is used as a tool for making real‐time decisions. The algorithm is tested on hypothetical data. [ABSTRACT FROM AUTHOR]

In this paper, we consider a vehicle routing problem in which a fleet of homogeneous vehicles, initially located at a depot, has to satisfy customers' demands in a two‐echelon network: first, the vehicles have to visit intermediate nodes (e.g., a retail center or a consolidation center), where they deliver raw materials or bulk products and collect a number of processed items requested by the customers in their route; then, the vehicles proceed to complete their assigned routes, thus delivering the processed items to the final customers before returning to the depot. During this stage, vehicles might visit other intermediate nodes for reloading new items. In some real‐life scenarios, this problem needs to be solved in just a few seconds or even milliseconds, which leads to the concept of "agile optimization." This might be the case in some rescue operations using drones in humanitarian logistics, where every second can be decisive to save lives. In order to deal with this real‐time two‐echelon vehicle routing problem with pickup and delivery, an original constructive heuristic is proposed. This heuristic is able to provide a feasible and reasonably good solution in just a few milliseconds. The constructive heuristic is extended into a biased‐randomized algorithm using a skewed probability distribution to modify its greedy behavior. This way, parallel runs of the algorithm are able to generate even better results without violating the real‐time constraint. Results show that the proposed methodology generates competitive results in milliseconds, being able to outperform other heuristics from the literature. [ABSTRACT FROM AUTHOR]

Abstract: This paper deals with power flow optimization with security constraints, focusing on the problem of short‐term hydroelectric scheduling, called predispatch. Since the energy demand varies throughout the day, the generation must satisfy daily targets, established by long‐term scheduling models. This study considers that the hydroelectric plants and transmission systems must provide an optimal flow of energy under security constraints that allow meeting energy demands for normal operating conditions and when disturbances happen. Algebraic techniques are used to exploit the sparse structure of the problem, targeting the design of an interior point algorithm, efficient in terms of robustness and computational time. Case studies compare the proposed approach with a general purpose optimization solver for quadratic problems and an algorithm for the predispatch problem that does not consider security constraints. The results show the benefits of using the method proposed in the paper, obtaining optimal power flow that is suitable to consider contingencies, with numerical stability and appropriate computational time. [ABSTRACT FROM AUTHOR]

The low-frequency array, LOFAR, is the world's largest connected low-frequency (LF) radio telescope, combining antenna arrays from across Western Europe into a single telescope. A major extension of an existing LOFAR component in Nançay, France, is currently being developed. The prototype design for this extension consists of a network of 96 LF radio telescope antenna arrays distributed across a 400 × 450 m area. A significant portion of the project's cost involves connecting each antenna array directly to a central control facility via a buried coaxial cable. In his 2013 doctoral dissertation, Girard proposed a cabling layout with the goal of minimizing the total cost to dig the trenches and lay the cables, by modeling the problem as a cable-trench problem (CTP). In this paper, we will discuss Girard's approach and then formulate the problem as a generalized CTP (GCTP) in order to handle physical obstacles more efficiently. To improve upon Girard's solution, we will first apply variations of Prim's algorithm to analyze a number of different GCTPs, based on a variety of cost parameters. Next, we will show that the mixed-integer linear programming formulation of the GCTP finds even better cable and trench layouts using CPLEX. Finally, we will use a new multicommodity flow formulation of the GCTP to find provably optimal solutions using CPLEX. This work has implications beyond the installation in development in Nançay, as any future component of LOFAR can apply the techniques discussed in this paper to significantly reduce construction costs. [ABSTRACT FROM AUTHOR]

Abstract: If production trade‐offs—which represent simultaneously feasible exchanges in the inputs and outputs of decision‐making units (DMUs)—are added to an integer production possibility set (IPPS), a new IPPS is produced; conventional axioms of production do not generate a new IPPS, however. This paper develops the axiomatic foundation for data envelopment analysis (DEA) for integer‐value inputs and outputs in the presence of production trade‐offs by introducing a new axiom of “natural trade‐offs.” First, a mixed‐integer linear programming formula called an integer DEA trade‐off (IDEA‐TO) is presented for computing efficiency scores and reference points. The numeration algorithm (NA) method presented in this concept is improved, and an improved numeration algorithm (INA) method for solving integer DEA (IDEA) models is developed. Finally, comparison between the two methods and a generalized INA method for solving the IDEA‐TO model are presented. [ABSTRACT FROM AUTHOR]

This paper addresses the multiobjective hybrid flow shop (MOHFS) scheduling problem. In the MOHFS problem considered here, we have a set of jobs that must be performed in a set of stages. At each stage, we have a set of unrelated parallel machines. Some jobs may skip stages. The evaluation criteria are the minimizations of makespan, the weighted sum of the tardiness, and the weighted sum of the earliness. For solving it, an algorithm based on the multiobjective general variable neighborhood search (MO‐GVNS) metaheuristic, named adapted MO‐GVNS, is proposed. This work also presents and compares the results obtained by the adapted MO‐GVNS with those of four other algorithms: multiobjective reduced variable neighborhood search, nondominated sorting genetic algorithm II (NSGA‐II), and NSGA‐III, and another MO‐GVNS from the literature. The results were evaluated based on the Hypervolume, Epsilon, and Spacing metrics, and statistically validated by the Levene test and confidence interval charts. The results showed the efficiency of the proposed algorithm for solving the MOHFS problem. [ABSTRACT FROM AUTHOR]

Given an undirected graph G=(V,E) and a weight for each vertex, the maximum weighted independent set problem (MWISP) calls for a maximum weight subset I of V such that no two vertices in I are adjacent. In this paper, we present an algorithm based on an iterated local search for the MWISP. We incorporate a branch‐and‐bound method in our local search, which enables the algorithm to search a very large neighborhood. Moreover, we propose a search method that reduces the number of candidate solutions to be searched in the neighborhood without missing improved solutions. The proposed algorithm also features an adaptive memory strategy in which each vertex is associated with a penalty that is used to explore diverse solutions in the iterated local search. We tested our algorithm on several instances taken from the DIMACS website and their weighted counterparts, which included large instances with more than 3000 vertices. From the results, we observed that our algorithm was competitive with existing algorithms for unweighted instances, and it found better solutions for some weighted instances. [ABSTRACT FROM AUTHOR]

Supporting decision makers in complex problems involving multiple stakeholders, multiple criteria, uncertainty and risk or other factors has been an important goal of Operations Research since the field emerged. New developments in technology have increased the computing power available for problem solving and have made technology and algorithms much more accessible by providing new ways of communicating with models and tools. [Extracted from the article]

Motivated by the recovery of modular‐structured products, this study addresses the flexible design of a reverse supply chain (RSC) over a planning horizon while incorporating the dynamic uncertain behavior of product returns. The stochastic parameter is modeled as a scenario tree and therefore the concerned problem is formulated as a multistage mixed‐integer stochastic program. To alleviate the computational complexity of the proposed model, it is decomposed into smaller scenario cluster submodels associated with a number of subtrees that share a certain number of predecessor nodes in the original scenario tree. The submodels are coordinated into an implementable solution via a Lagrangian‐progressive hedging‐based method that employs a viable Benders decomposition based algorithm for solving each scenario cluster submodel. Based on a realistic scale case, computational results indicate the superiority of the proposed flexible dynamic RSC design model compared to the existing models. Results also demonstrate the efficiency of the proposed solution approach. [ABSTRACT FROM AUTHOR]

Reward-based scheduling of real-time systems of periodic, preemptable, and independent tasks with mandatory and optional parts in homogeneous multiprocessors with energy considerations is a problem that has not been analyzed before. The problem is NP-hard. In this paper, a restricted migration schedule is adopted in which different jobs of the same task may execute in different processors and at different power modes but no migration is allowed after the job has started its execution. An objective function to maximize the performance of the system considering the execution of optional parts, the benefits of slowing down the processor, and a penalty for changing the operation frequency is introduced together with a set of constraints that guarantee the real-time performance of the system. Different algorithms are proposed to find a feasible schedule maximizing the objective function and are compared using synthetic systems of tasks generated following guidelines proposed in previous papers. [ABSTRACT FROM AUTHOR]

Given a connected digraph, a vertex designated as the root, and an integer p$p$, the p$p$‐arborescence star problem is to choose p$p$ vertices besides the root and define a reverse arborescence spanning them. Each vertex outside the arborescence must be assigned to one vertex inside it. The objective of the problem is to minimize arborescence and assignment costs. We propose two formulations for the problem and prove theoretical results about their strength. Moreover, we develop branch‐and‐cut algorithms based on each one of the formulations and improve an earlier branch‐and‐cut algorithm for the problem with an exact separation method. Additionally, we show that finding a feasible solution for an arbitrary instance is NP‐hard and introduce preprocessing procedures for the problem. The proposed algorithms are evaluated with a set of benchmark instances from the literature. For small and medium‐sized instances, our proposed algorithms provide the best results when compared to the existing algorithm from the literature. For large instances, the proposed algorithms are shown to be competitive with the existing approach. [ABSTRACT FROM AUTHOR]

The amount of big data collected during human-computer interactions requires natural language processing (NLP) applications to be executed efficiently, especially in parallel computing environments. Scalability and performance are critical in many NLP applications such as search engines or web indexers. However, there is a lack of mathematical models helping users to design and apply scheduling theory for NLP approaches. Moreover, many researchers and software architects reported various difficulties related to common NLP benchmarks. Therefore, this paper aims to introduce and demonstrate how to apply a scheduling model for a class of keyword extraction approaches. Additionally, we propose methods for the overall performance evaluation of different algorithms, which are based on processing time and correctness (quality) of answers. Finally, we present a set of experiments performed in different computing environments together with obtained results that can be used as reference benchmarks for further research in the field. [ABSTRACT FROM AUTHOR]

This paper investigates a periodic review fuzzy inventory model with lead time, reorder point, and cycle length as decision variables. The main goal of this study is to minimize the expected total annual cost by simultaneously optimizing cycle length, reorder point, and lead time for the whole system based on fuzzy demand. Two models are considered in this paper: one with normal demand distribution and another with a distribution-free approach. The model assumes a logarithmic investment function for lost-sale rate reduction. Furthermore, two separate efficient computational algorithms are explained to obtain the optimal solution. Some numerical examples are given to illustrate the model. [ABSTRACT FROM AUTHOR]

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which 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. Since 1989, numerous papers on the basic aspects of GRASP, as well as enhancements to the basic metaheuristic, have appeared in the literature. GRASP has been applied to a wide range of combinatorial optimization problems, ranging from scheduling and routing to drawing and turbine balancing. This is the second of two papers with an annotated bibliography of the GRASP literature from 1989 to 2008. In the companion paper, algorithmic aspects of GRASP are surveyed. In this paper, we cover the literature where GRASP is applied to scheduling, routing, logic, partitioning, location, graph theory, assignment, manufacturing, transportation, telecommunications, biology and related fields, automatic drawing, power systems, and VLSI design. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present a comprehensive framework for multiattribute group decision making considering that neither information about individual preferences nor the importance of individual decision makers for the group is available in exact form. We study several different forms of incomplete preference information, including a ranking of attribute weights, ranking of values of alternatives in each attribute, and ranking of value differences. Our approach is based on relative volumes in parameter space and allows for probabilistic statements about different results, including optimality or quasi‐optimality of alternatives, or relations between alternatives. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, the admissible region of a biobjective knapsack problem is our main interest. Although the reduction of feasible region has been studied by some authors, yet more investigation has to be done in order to deeply explore the domain before solving the problem. We propose, however, a new technique based on extreme supported efficient solutions combined with the dominance relationship between items' efficiency. An illustration of the algorithm by a didactic example is given and some experiments are presented, showing the efficiency of the procedure compared to the previous techniques found in the literature. [ABSTRACT FROM AUTHOR]

Supporting decision makers in complex problems involving multiple stakeholders, multiple criteria, uncertainty and risk or other factors has been an important goal of Operations Research since the field emerged. New developments in technology have increased the computing power available for problem solving and have made technology and algorithms much more accessible by providing new ways of communicating with models and tools. [Extracted from the article]

New developments in technology have increased the computing power available for problem solving and have made technology and algorithms much more accessible by providing new ways of communicating with models and tools. Supporting decision makers in complex problems involving multiple stakeholders, multiple criteria, uncertainty and risk or other factors has been an important goal of Operations Research since the field emerged. [Extracted from the article]

We study a class of mixed integer optimization problems with linear constraints and a multilinear objective function, the so‐called mixed integer linear maximum multiplicative programs (MIL‐MMPs). Such a problem can be transformed into a second‐order cone program (SOCP) and can be solved effectively by a commercial solver such as CPLEX. However, MIL‐MMPs can also be viewed as special cases of the problem of optimization over the set of efficient solutions in multiobjective optimization. Using this observation, we develop a criterion space search algorithm for solving any MIL‐MMP. An extensive computational study on around 2000 instances illustrates that the proposed algorithm significantly outperforms not only the CPLEX mixed integer SOCP solver but also a state‐of‐the‐art algorithm that is capable of solving special cases of MIL‐MMPs. Moreover, the computational study illustrates that even if we linearize the objective function and solve the linearized problem by CPLEX, the proposed algorithm still performs significantly better. [ABSTRACT FROM AUTHOR]

Real‐world problems are becoming highly complex and therefore have to be solved with combinatorial optimization (CO) techniques. Motivated by the strong increase in publications on CO, 8393 articles from this research field are subjected to a bibliometric analysis. The corpus of literature is examined using mathematical methods and a novel algorithm for keyword analysis. In addition to the most relevant countries, organizations, and authors as well as their collaborations, the most pertinent CO problems, solution methods, and application areas are presented. Publications on CO focus mainly on the development or enhancement of metaheuristics like genetic algorithms. The increasingly problem‐oriented studies deal particularly with real‐world applications within the energy sector, production sector, or data management, which are of increasing relevance due to various global developments. The demonstration of global research trends in CO can support researchers in identifying the relevant issues regarding this expanding and transforming research area. [ABSTRACT FROM AUTHOR]

The distance between two objects determines how far apart they are with respect to each other. In this paper, we provide an overview of the distance concept in multimedia phylogeny, a novel research field that aims at discovering the phylogenetic relationships among digital objects that belong to the same population. With applications in digital forensics, copyright enforcement, and security, existing approaches are often based on dissimilarity computations among digital objects in a nonmetric space, but with enough information to correctly reconstruct the underlying relationships of these objects. As we discuss throughout the paper, a proper and well-designed dissimilarity is paramount for differentiating whether two multimedia objects are related and, also, the directionality of such relationship. In phylogeny setups, there is also the additional requirement of low complexity: fast and accurate dissimilarity measures to cope with the massive amount of data we often have to handle. [ABSTRACT FROM AUTHOR]

We consider the regularized empirical risk minimization (ERM) of linear predictors, which arises in a variety of problems in machine learning and statistics. After reformulating the original ERM as a bilinear saddle‐point problem, we can apply stochastic primal–dual methods to solve it. Sampling the primal or dual coordinates with a fixed nonuniform distribution is usually employed to accelerate the convergence of the algorithm, but such a strategy only exploits the global information of the objective function. To capture its local structures, we propose an adaptive importance sampling strategy that chooses the coordinates based on delicately designed nonuniform and nonstationary distributions. When our adaptive coordinate sampling strategy is applied to the Stochastic Primal‐Dual Coordinate (SPDC), we prove that the resulting algorithm enjoys linear convergence. Moreover, we show that the ideal form of our adaptive sampling exhibits strictly sharper convergence rate under certain conditions compared with the vanilla SPDC. We also extend our sampling strategy to other algorithms including Doubly Stochastic Primal‐Dual Coordinate (DSPDC) and Stochastic Primal‐Dual with O(1) per‐iteration cost and Variance Reduction (SPD1‐VR), where both primal and dual coordinates are randomly sampled. Our experiment results show that the proposed strategy significantly improves the convergence performance of the methods when compared with existing sampling strategies. [ABSTRACT FROM AUTHOR]

Thus far, the available works on the flexible assembly job‐shop scheduling problem (FAJSP) consider job processing and assembly separately. However, in some real production systems, if equipment is composed of thousands of jobs and assembled in many stages, some jobs and assemblies cannot be processed simultaneously. Therefore, this work proposes an FAJSP with tight job constraints (FAJSP‐JC) in which jobs and assemblies can be processed simultaneously, and each assembly is treated as an operation. A job constraint genetic algorithm (JCGA) is presented to solve the proposed FAJSP‐JC with the goal of minimizing the makespan. In the JCGA, a novel two‐dimensional encoding method (2D‐encoding) is designed to conveniently express the operating constraints and tight job constraints, and an effective decoding method is proposed to decode the 2D‐encoded information. Furthermore, a crossover operator and a mutation operator are designed to improve the computational efficiency and expand the solution space. Ten benchmark instances of the FAJSP‐JC are constructed to test the JCGA. The Taguchi method is used to obtain the best combination of the key parameters that are used in the JCGA. Computational experiments carried out confirm that the JCGA is able to easily obtain better solutions compared to the genetic algorithm (GA) with a division encoding method and the classical GA, demonstrating its superior performance over these algorithms in terms of both solution quality and computational efficiency. [ABSTRACT FROM AUTHOR]

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. It is a multi-start or iterative process, in which 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. Since 1989, numerous papers on the basic aspects of GRASP, as well as enhancements to the basic metaheuristic have appeared in the literature. GRASP has been applied to a wide range of combinatorial optimization problems, ranging from scheduling and routing to drawing and turbine balancing. This is the first of two papers with an annotated bibliography of the GRASP literature from 1989 to 2008. This paper covers algorithmic aspects of GRASP. [ABSTRACT FROM AUTHOR]

This paper describes a practical application of locational analysis to the siting of HIV/AIDS diagnostic equipment in laboratories across South Africa. Classical location analytical techniques were extended to ensure that laboratories are sited as close as possible to major centers of demand from hospitals and clinics. A particular advantage of the modified set covering algorithm developed is that choices between laboratory sites are made in a transparent manner. In order to find appropriate numbers and ideal placement of CD4 laboratories, runs were undertaken for various scenarios based on maximum travel time from health facilities to laboratory sites. Results demonstrated to decision makers showed close comparisons with pilot review projects undertaken in four health districts of South Africa. The research has potential to impact health-care delivery to HIV sufferers in the poorest rural regions of the country. [ABSTRACT FROM AUTHOR]