Alternating control tree search for knapsack/covering problems

The Multidimensional Knapsack/Covering Problem (KCP) is a 0–1 Integer Programming Problem containing both knapsack and weighted covering constraints, subsuming the well-known Multidimensional Knapsack Problem (MKP) and the Generalized (weighted) Covering Problem. We propose an Alternating Control Tree Search (ACT) method for these problems that iteratively transfers control between the following three components: (1) ACT-1, a process that solves an LP relaxation of the current form of the KCP. (2) ACT-2, a method that partitions the variables according to 0, 1, and fractional values to create sub-problems that can be solved with relatively high efficiency. (3) ACT-3, an updating procedure that adjoins inequalities to produce successively more constrained versions of KCP, and in conjunction with the solution processes of ACT-1 and ACT-2, ensures finite convergence to optimality. The ACT method can also be used as a heuristic approach using early termination rules. Computational results show that the ACT-framework successfully enhances the performance of three widely different heuristics for the KCP. Our ACT-method involving scatter search performs better than any other known method on a large set of KCP-instances from the literature. The ACT-based methods are also found to be highly effective on the MKP.     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

Reducing the number of variables in Integer and Linear Programming Problems

Computational difficulties in solving the Integer Programming Problems (IPP) are caused to a considerable degree by the number of variables. If the number of variables is small, then even NP-complete problems usually can be solved with a reasonable expenditure of effort.A procedure is developed for the analysis of large scale IPP with the aim of reducing the number of variables prior to starting the solution method. The procedure is based on comparing pairs of columns of the constraint matrix of the IPP. If a pair of columns thus compared meets certain conditions, then the IPP has an optimal solution, in which a variable corresponding to one of the columns in the pair is equal to zero. Corresponding theorems for Knapsack and Multidimensional Knapsack problems and for general IPP are presented. The procedure is extended to Linear and Mixed Integer Programming Problems. The presented results of computational experiments illustrate the efficiency of the developed procedure.     

A heuristic for BILP problems: The Single Source Capacitated Facility Location Problem

In the Single Source Capacitated Facility Location Problem (SSCFLP) each customer has to be assigned to one facility that supplies its whole demand. The total demand of customers assigned to each facility cannot exceed its capacity. An opening cost is associated with each facility, and is paid if at least one customer is assigned to it. The objective is to minimize the total cost of opening the facilities and supply all the customers. In this paper we extend the Kernel Search heuristic framework to general Binary Integer Linear Programming (BILP) problems, and apply it to the SSCFLP. The heuristic is based on the solution to optimality of a sequence of subproblems, where each subproblem is restricted to a subset of the decision variables. The subsets of decision variables are constructed starting from the optimal values of the linear relaxation. Variants based on variable fixing are proposed to improve the efficiency of the Kernel Search framework. The algorithms are tested on benchmark instances and new very large-scale test problems. Computational results demonstrate the effectiveness of the approach. The Kernel Search algorithm outperforms the best heuristics for the SSCFLP available in the literature. It found the optimal solution for 165 out of the 170 instances with a proven optimum. The error achieved in the remaining instances is negligible. Moreover, it achieved, on 100 new very large-scale instances, an average gap equal to 0.64% computed with respect to a lower bound or the optimum, when available. The variants based on variable fixing improved the efficiency of the algorithm with minor deteriorations of the solution quality.     

Ants can orienteer a thief in their robbery

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.     

A hybrid Tabu-ascent algorithm for the linear Bilevel Programming Problem

The linear Bilevel Programming Problem (BLP) is an instance of a linear hierarchical decision process where the lower level constraint set is dependent on decisions taken at the upper level. In this paper we propose to solve this NP-hard problem using an adaptive search method related to the Tabu Search metaheuristic. Numerical results on large scale linear BLPs are presented.     

Well-tuned algorithms for the Team Orienteering Problem with Time Windows

The Team Orienteering Problem with Time Windows (TOPTW) is the extension of the Orienteering Problem (OP) where each node is limited by a predefined time window during which the service has to start. The objective of the TOPTW is to maximize the total collected score by visiting a set of nodes with a limited number of paths. We propose two algorithms, Iterated Local Search and a hybridization of Simulated Annealing and Iterated Local Search (SAILS), to solve the TOPTW. As indicated in multiple research works on algorithms for the OP and its variants, determining appropriate parameter values in a statistical way remains a challenge. We apply Design of Experiments, namely factorial experimental design, to screen and rank all the parameters thereby allowing us to focus on the parameter search space of the important parameters. The proposed algorithms are tested on benchmark TOPTW instances. We demonstrate that well-tuned ILS and SAILS lead to improvements in terms of the quality of the solutions. More precisely, we are able to improve 50 best known solution values on the available benchmark instances.     

A hybrid heuristic algorithm for the open-pit-mining operational planning problem

This paper deals with the Open-Pit-Mining Operational Planning problem with dynamic truck allocation. The objective is to optimize mineral extraction in the mines by minimizing the number of mining trucks used to meet production goals and quality requirements. According to the literature, this problem is NP-hard, so a heuristic strategy is justified. We present a hybrid algorithm that combines characteristics of two metaheuristics: Greedy Randomized Adaptive Search Procedures and General Variable Neighborhood Search. The proposed algorithm was tested using a set of real-data problems and the results were validated by running the CPLEX optimizer with the same data. This solver used a mixed integer programming model also developed in this work. The computational experiments show that the proposed algorithm is very competitive, finding near optimal solutions (with a gap of less than 1%) in most instances, demanding short computing times.     

The Parallel Variable Neighborhood Search for the p-Median Problem

The Variable Neighborhood Search (VNS) is a recent metaheuristic that combines series of random and improving local searches based on systematically changed neighborhoods. When a local minimum is reached, a shake procedure performs a random search. This determines a new starting point for running an improving search. The use of interchange moves provides a simple implementation of the VNS algorithm for the p-Median Problem. Several strategies for the parallelization of the VNS are considered and coded in C using OpenMP. They are compared in a shared memory machine with large instances.     

Binary Accelerated Particle Swarm Algorithm (BAPSA) for discrete optimization problems

The majority of Combinatorial Optimization Problems (COPs) are defined in the discrete space. Hence, proposing an efficient algorithm to solve the problems has become an attractive subject in recent years. In this paper, a meta-heuristic algorithm based on Binary Particle Swarm Algorithm (BPSO) and the governing Newtonian motion laws, so-called Binary Accelerated Particle Swarm Algorithm (BAPSA) is offered for discrete search spaces. The method is presented in two global and local topologies and evaluated on the 0–1 Multidimensional Knapsack Problem (MKP) as a famous problem in the class of COPs and NP-hard problems. Besides, the results are compared with BPSO for both global and local topologies as well as Genetic Algorithm (GA). We applied three methods of Penalty Function (PF) technique, Check-and-Drop (CD) and Improved Check-and-Repair Operator (ICRO) algorithms to solve the problem of infeasible solutions in the 0–1 MKP. Experimental results show that the proposed methods have better performance than BPSO and GA especially when ICRO algorithm is applied to convert infeasible solutions to feasible ones.     

A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times

This paper describes a generalized variable neighborhood search heuristic for the Capacitated Vehicle Routing Problem with Stochastic Service Times, in which the service times at vertices are stochastic. The heuristic is tested on randomly generated instances and compared with two other heuristics and with an alternative solution strategy. Computational results show the superiority and effectiveness of the proposed heuristic.     

Local search intensified: Very large-scale variable neighborhood search for the multi-resource generalized assignment problem

We introduce a heuristic for the Multi-Resource Generalized Assignment Problem (MRGAP) based on the concepts of Very Large-Scale Neighborhood Search and Variable Neighborhood Search. The heuristic is a simplified version of the Very Large-Scale Variable Neighborhood Search for the Generalized Assignment Problem. Our algorithm can be viewed as a k-exchange heuristic; but unlike traditional k-exchange algorithms, we choose larger values of k resulting in neighborhoods of very large size with high probability. Searching this large neighborhood (approximately) amounts to solving a sequence of smaller MRGAPs either by exact algorithms or by heuristics. Computational results on benchmark test problems are presented. We obtained improved solutions for many instances compared to some of the best known heuristics for the MRGAP within reasonable running time. The central idea of our heuristic can be used to develop efficient heuristics for other hard combinatorial optimization problems as well.     

Heuristics for the container loading problem

The knapsack container loading problem is the problem of loading a subset of rectangular boxes into a rectangular container of fixed dimensions such that the volume of the packed boxes is maximized. A new heuristic based on the wall-building approach is proposed, which decomposes the problem into a number of layers which again are split into a number of strips. The packing of a strip may be formulated and solved optimally as a Knapsack Problem with capacity equal to the width or height of the container. The depth of a layer as well as the thickness of each strip is decided through a branch-and-bound approach where at each node only a subset of branches is explored.Several ranking rules for the selection of the most promising layer depths and strip widths are presented and the performance of the corresponding algorithms is experimentally compared for homogeneous and heterogeneous instances. The best ranking rule is then used in a comprehensive computational study involving large-sized instances. These computational results show that instances with a total box volume up to 90% easily may be solved to optimality, and that average fillings of the container volume exceeding 95% may be obtained for large-sized instances.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

An exact algorithm for the Capacitated Total Quantity Discount Problem

In this paper we analyze the procurement problem of a company that needs to purchase a number of products from a set of suppliers to satisfy demand. The suppliers offer total quantity discounts and the company aims at selecting a set of suppliers so to satisfy product demand at minimum purchasing cost. The problem, known as Total Quantity Discount Problem (TQDP), is strongly NP-hard. We study different families of valid inequalities and provide a branch-and-cut approach to solve the capacitated variant of the problem (Capacitated TQDP) where the quantity available for a product from a supplier is limited. A hybrid algorithm, called HELP (Heuristic Enhancement from LP), is used to provide an initial feasible solution to the exact approach. HELP exploits information provided by the continuous relaxation problem to construct neighborhoods optimally searched through the solution of mixed integer subproblems. A streamlined version of the proposed exact method can optimally solve in a reasonable amount of time instances with up to 100 suppliers and 500 products, and largely outperforms an existing approach available in the literature and CPLEX 12.2 that frequently runs out of memory before completing the search.     

Tabu Search for Frequency Assignment in Mobile Radio Networks

The main goal of the Frequency Assignment Problem in mobile radio networks consists of assigning a limited number of frequencies to each radio cell in a cellular network while minimizing electromagnetic interference due to the reuse of frequencies. This problem, known to be NP-hard, is of great importance in practice since better solutions will allow a telecommunications operator to manage larger cellular networks. This paper presents a new Tabu Search algorithm for this application. The algorithm is tested on realistic and large problem instances and compared with other methods based on simulated annealing, constraint programming and graph coloring algorithms. Empirical evidence shows that the Tabu algorithm is very competitive by giving the best solutions to the tested instances.     

A cut-and-solve based algorithm for the single-source capacitated facility location problem

In this paper, we present a cut-and-solve (CS) based exact algorithm for the Single Source Capacitated Facility Location Problem (SSCFLP). At each level of CS’s branching tree, it has only two nodes, corresponding to the Sparse Problem (SP) and the Dense Problem (DP), respectively. The SP, whose solution space is relatively small with the values of some variables fixed to zero, is solved to optimality by using a commercial MIP solver and its solution if it exists provides an upper bound to the SSCFLP. Meanwhile, the resolution of the LP of DP provides a lower bound for the SSCFLP. A cutting plane method which combines the lifted cover inequalities and Fenchel cutting planes to separate the 0–1 knapsack polytopes is applied to strengthen the lower bound of SSCFLP and that of DP. These lower bounds are further tightened with a partial integrality strategy. Numerical tests on benchmark instances demonstrate the effectiveness of the proposed cutting plane algorithm and the partial integrality strategy in reducing integrality gap and the effectiveness of the CS approach in searching an optimal solution in a reasonable time. Computational results on large sized instances are also presented.     

A Bound and Bound algorithm for the zero-one multiple knapsack problem

By the term “Bound and Bound” we define a particular tree-search technique for the ILP, which, for a maximization problem, makes use of a lower bound to determine the branches to follow in the decision tree. This technique is applied to the solution of the Zero-One Multiple Knapsack Problem and an algorithm is derived; an illustrative example of the procedure is provided. We present extensive computational results showing that the method is capable of solving problems up to 4 knapsacks and 200 variables with running times considerably smaller than those of the most commonly utilized algorithms.     

Kernel search for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is among the most studied problems in the OR literature. Each customer demand has to be supplied by one or more facilities. Each facility cannot supply more than a given amount of product. The goal is to minimize the total cost to open the facilities and to serve all the customers. The problem is $\mathcal{NP}$ -hard. The Kernel Search is a heuristic framework based on the idea of identifying subsets of variables and in solving a sequence of MILP problems, each problem restricted to one of the identified subsets of variables. In this paper we enhance the Kernel Search and apply it to the solution of the CFLP. The heuristic is tested on a very large set of benchmark instances and the computational results confirm the effectiveness of the Kernel Search framework. The optimal solution has been found for all the instances whose optimal solution is known. Most of the best known solutions have been improved for those instances whose optimal solution is still unknown.     

Solving feature subset selection problem by a Parallel Scatter Search

The aim of this paper is to develop a Parallel Scatter Search metaheuristic for solving the Feature Subset Selection Problem in classification. Given a set of instances characterized by several features, the classification problem consists of assigning a class to each instance. Feature Subset Selection Problem selects a relevant subset of features from the initial set in order to classify future instances. We propose two methods for combining solutions in the Scatter Search metaheuristic. These methods provide two sequential algorithms that are compared with a recent Genetic Algorithm and with a parallelization of the Scatter Search. This parallelization is obtained by running simultaneously the two combination methods. Parallel Scatter Search presents better performance than the sequential algorithms.