Search

We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a new heuristic framework, which we call the iterated dual substitution (iDS) algorithm. The iDS algorithm iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best-scenario-based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best known records for a number of benchmark instances., 36 pages (20-page appendices included), 5 figures

This chapter discusses the rectangle packing problem and its variations and introduces coding schemes for the rectangle packing problem, which are used to represent solutions. It presents heuristic algorithms, from the traditional to the latest ones, for the rectangle packing problem. The chapter also introduces techniques to enumerate all the bottom-left stable positions in a layout. It also discusses metaheuristic algorithms for the rectangle packing problem and explores various schemes used to represent solutions to the rectangle packing problem and explains algorithms based on these coding schemes. The chapter considers the following two-dimensional rectangle packing problem. For some packing problems including the two-dimensional irregular packing problem, algorithms with compaction and separation operations were proposed. Cutting and packing problems can be classified using different criteria. F. G. Ortmann et al. proposed several new and improved level algorithms for the strip packing problem and a bin packing problem with different-sized bins.

This chapter reviews heuristic and metaheuristic algorithms for generalized assignment problem and explores the problem formally and introduces some related problems and their complexities. It explains basic strategies of greedy method and local search and describes Lagrangian relaxation problems. The chapter provides some basic ideas of Lagrangian heuristics and also describes the basics of branch-and-bound. It analyses some computational results of various metaheuristic algorithms and branch-and-bound methods. The chapter focuses on polynomial-time approximation algorithms with performance guarantees. There are several useful tools used to design approximation algorithms. Metaheuristic algorithms are widely recognized as one of the most practical approaches for hard combinatorial optimization problems. Algorithm path relinking with ejection chains applies ejection chains probes to solutions generated by path relinking, which is a methodology to generate solutions from two or more solutions.

This paper focuses on a two-dimensional strip packing problem where a set of arbitrarily shaped rectilinear blocks need be packed into a larger rectangular container without overlap. A rectilinear block is a polygonal block whose interior angles are either 90∘or 270∘. This problem involves many industrial applications, such as VLSI design, timber/glass cutting, and newspaper layout. We generalized a bottom-left and a best-fit algorithms to the rectilinear block packing problem in our previous paper. Based on the analysis of the strength and weakness of these algorithms, we propose a new construction heuristic algorithm called the partition-based best-fit algorithm (PBF algorithm), which takes advantages of both the bottom-left and the best-fit algorithms. The basic idea of the PBF algorithm is that it partitions all the items into groups and then packs the items in a group-by-group manner. The best-fit algorithm is taken as the internal tactics for each group. The proposed algorithm is tested on a series of instances, which are generated from benchmark instances. The computational results show that the proposed algorithm significantly improves the performance of the existing construction heuristic algorithms and is especially effective for the instances having large differences in the sizes of given shapes.

ILS and GDA metaheuristics for the linear ordering problem are introduced.They are able to tackle large instances in line with real applications.Introduced methods are the first of their kind ever applied to large-sized instances.All best known solutions of the large-sized instances are improved. This paper presents iterated local search and great deluge trajectory metaheuristics for the linear ordering problem (LOP). Both metaheuristics are based on the TREE local search method introduced in Sakuraba and Yagiura (2010) that is the only method ever applied to a set of large-sized instances that are in line with the scale of nowadays real applications. By providing diversification and intensification features, the introduced methods improve all best known solutions of the large-sized instances set. Extensive numerical experiments show that the introduced methods are capable of tackling sparse and dense large-scale instances with up to 8000 vertices and 31,996,000 edges in a reasonable amount of time; while they also performs well in practice when compared with other state-of-the-art methods in a benchmark with small and medium-scale instances.

We consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. This problem models many real-world applications in which jobs must be assigned to agents but the costs of assignment may vary after the decision has been taken. We computationally examine two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. We also examine exact algorithmic approaches (Benders-like decomposition and branch-and-cut) and further introduce a more sophisticated algorithm that incorporates various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances., ファイル公開：2021-11-01

The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container, where a rectilinear block is a polygonal block whose interior angle is either 90? or 270?. There exist many applications of this problem, such as VLSI design, timber/glass cutting, and newspaper layout. In this paper, we design efficient implementations of two construction heuristics for rectilinear block packing. The proposed algorithms are tested on a series of instances, which are generated from nine benchmark instances. The computational results show that the proposed algorithms are especially efficient for large instances with repeated shapes.

Robust optimization motivated by practical applications deals with optimization problems in which some input parameters are uncertain. In this paper, we consider Γ-robust combinatorial optimization problems under max-min criterion. For this type of problems, we propose and prove a general lemma that we call the worst case scenario lemma; it specifies a worst case scenario for a given solution. Based on the worst case scenario lemma, we propose an exact dynamic programming algorithm for the Γ-robust knapsack problem under max-min criterion.

This paper presents an efficient algorithm that enumerates all the bottom-left stable positions for a given layout of rectangles. Its time complexity is O((n +K) log n), where n is the number of placed rectangles (i.e., input size) and K is the number of bottom-left stable positions (i.e., output size). This is the first non-trivial algorithm that works for layouts without bottom-left stability and with overlap. In addition to the theoretical analysis of the time complexity, we evaluate the computation time of the proposed algorithm via computational experiments and confirm that it is applicable to very large-scale instances having one million rectangles.

Vehicle routing and scheduling problems have a wide range of applications and have been intensively studied in the past half century. The condition that enforces each vehicle to start service at each customer in the period specified by the customer is called the time window constraint. This paper reviews recent results on how to handle hard and soft time window constraints, putting emphasis on its different definitions and algorithms. With these diverse time windows, the problem becomes applicable to a wide range of real-world problems.

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods. Highlights? Introducing node capacities to a spanning arborescence packing problem on digraphs. ? Generating in-trees by the column generation method. ? Solving the minimum weight rooted arborescence problem as the pricing problem. ? Packing in-trees by a greedy algorithm with efficient data structures. ? The approximation guarantee of LP-based algorithms.