THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.     

Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems

We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios. The approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its deterministic counterpart. Furthermore, we show that common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be adapted to obtain these results.     

A distributed global optimization method for packing problems

Packing optimization problems aim to seek the best way of placing a given set of rectangular cartons within a minimum volume rectangular container. Currently, packing optimization methods either have difficulty in finding a globally optimal solution or are computationally inefficient, because models involve too many 0–1 variables and because use of just a single computer. This study proposes a distributed computation method for solving a packing problem by a set of personal computers via the Internet. First, the traditional packing optimization model is converted into an equivalent model containing many fewer 0–1 variables. Then the model is decomposed into several sub-problems by dividing the objective value into many intervals. Each of these sub-problems is a linearized logarithmic program expressed as a linear mixed 0–1 problem. The whole problem is solvable and reaches a globally optimal solution. The numerical examples demonstrate that the proposed method can obtain the global optimum of a packing problem effectively.     

Fuzzy bin packing problem

This paper deals with the fuzzy bin packing problem that is a packing problem of non-rigid rectangles into an open rectangular bin. This problem is different from the conventional bin packing problem, which considers only rigid rectangles. The goal of the fuzzy bin packing problem is to minimize both the height of a packing and the extra cost due to the reduction of each piece. The total cost of the problem is represented as the sum of the height cost and the extra cost due to reductions of the pieces, which is called reduction cost. Because the conventional bin packing problem itself is an NP-hard problem, the presented optimization method assumes that an initial packing for non-reduced pieces has already been found. A closed form solution is presented for fuzzy bin packing problems, in which fuzzy numbers are triangular and the reduction cost is given by a quadratic function.     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

Evolutionary,constructive and hybrid procedures for the bi-objective set packing problem

The bi-objective set packing problem is a multi-objective combinatorial optimization problem similar to the well-known set covering/partitioning problems. To our knowledge and surprise, this problem has not yet been studied whereas several applications have been reported. Unfortunately, solving the problem exactly in a reasonable time using a generic solver is only possible for small instances. We designed three alternative procedures for approximating solutions to this problem. The first is derived from the original ‘Strength Pareto Evolutionary Algorithm’, which is a population-based metaheuristic. The second is an adaptation of the ‘Greedy Randomized Adaptative Search Procedure’, which is a constructive metaheuristic. As underlined in the overview of the literature summarized here, almost all the recent, effective procedures designed for approximating optimal solutions to multi-objective combinatorial optimization problems are based on a blend of techniques, called hybrid metaheuristics. Thus, the third alternative, which is the primary subject of this paper, is an original hybridization of the previous two metaheuristics. The algorithmic aspects, which differ from the original definition of these metaheuristics, are described, so that our results can be reproduced. The performance of our procedures is reported and the computational results for 120 numerical instances are discussed.     

The steiner tree packing problem in VLSI design

In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.     

A Bicriterial Optimization Problem of Antenna Design

In this paper we consider a special optimization problem withtwo objectives which arises in antenna theory. It is shown that thisabstract bicriterial optimization problem has at least one solution.Discretized versions of this problem are also discussed, and therelationships between these finite dimensional problems and the infinitedimensional problem are investigated. Moreover, we presentnumerical results for special parameters using a multiobjectiveoptimization method.     

Offset-polygon annulus placement problems

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.     

Valid inequalities and facets of the capacitated plant location problem

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, we investigate the polyhedral structure of the capacitated plant location problem. Our purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure.The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem.We also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. We identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.This research was partially supported by Grant # ECS-8316224 from the National Science Foundation's Program in Systems Theory and Operations Research.     

BPPLIB: a library for bin packing and cutting stock problems

The bin packing problem (and its variant, the cutting stock problem) is among the most intensively studied combinatorial optimization problems. We present a library of computer codes, benchmark instances, and pointers to relevant articles for these two problems. The library is available at http://or.dei.unibo.it/library/bpplib. The computer code section includes twelve programs: seven are directly downloadable from the library page, while for the remaining five we provide addresses where they can be obtained or downloaded. Some of the codes for which we provide an original C++ implementation need an integer linear programming solver. For such cases, the library provides two versions: one that uses the commercial solver CPLEX, and one that uses the freeware solver SCIP. The benchmark section provides over six thousands instances (partly coming from the literature and partly randomly generated), together with the corresponding solutions. Instances that are difficult to solve to proven optimality are included. The library also includes a BibTeX file of more than 150 references on this topic and an interactive visual tool to manually solve bin packing and cutting stock instances. We conclude this work by reporting the results of new computational experiments on a number of computer codes and benchmark instances.     

Solving circle packing problems by global optimization: Numerical results and industrial applications

A (general) circle packing is an optimized arrangement of N arbitrary sized circles inside a container (e.g., a rectangle or a circle) such that no two circles overlap. In this paper, we present several circle packing problems, review their industrial applications, and some exact and heuristic strategies for their solution. We also present illustrative numerical results using ‘generic’ global optimization software packages. Our work highlights the relevance of global optimization in solving circle packing problems, and points towards the necessary advancements in both theory and numerical practice.     

Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear optimization

We further improve our methodology for solving irregular packing and cutting problems. We deal with an accurate representation of objects bounded by circular arcs and line segments and allow their continuous rotations and translations within rectangular and circular containers. We formulate a basic irregular placement problem which covers a wide spectrum of packing and cutting problems. We provide an exact non-linear programming (NLP) model of the problem, employing ready-to-use phi-functions. We develop an efficient solution algorithm to search for local optimal solutions for the problem in a reasonable time. The algorithm reduces our problem to a sequence of NLP subproblems and employs optimization procedures to generate starting feasible points and feasible subregions. Our algorithm allows us to considerably reduce the number of inequalities in NLP subproblems. To show the benefits of our methodology we give computational results for a number of new challenger and the best known benchmark instances.     

Random sampling and greedy sparsification for matroid optimization problems

Random sampling is a powerful tool for gathering information about a group by considering only a small part of it. We discuss some broadly applicable paradigms for using random sampling in combinatorial optimization, and demonstrate the effectiveness of these paradigms for two optimization problems on matroids: finding an optimum matroid basis and packing disjoint matroid bases. Application of these ideas to the graphic matroid led to fast algorithms for minimum spanning trees and minimum cuts. An optimum matroid basis is typically found by agreedy algorithm that grows an independent set into an optimum basis one element at a time. This continuous change in the independent set can make it hard to perform the independence tests needed by the greedy algorithm. We simplify matters by using sampling to reduce the problem of finding an optimum matroid basis to the problem of verifying that a givenfixed basis is optimum, showing that the two problems can be solved in roughly the same time. Another application of sampling is to packing matroid bases, also known as matroid partitioning. Sampling reduces the number of bases that must be packed. We combine sampling with a greedy packing strategy that reduces the size of the matroid. Together, these techniques give accelerated packing algorithms. We give particular attention to the problem of packing spanning trees in graphs, which has applications in network reliability analysis. Our results can be seen as generalizing certain results from random graph theory. The techniques have also been effective for other packing problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Some of this work done at Stanford University, supported by National Science Foundation and Hertz Foundation Graduate Fellowships, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation and Xerox Corporation. Also supported by NSF award 962-4239.     

Knapsack problems with sigmoid utilities: Approximation algorithms via hybrid optimization

We study a class of non-convex optimization problems involving sigmoid functions. We show that sigmoid functions impart a combinatorial element to the optimization variables and make the global optimization computationally hard. We formulate versions of the knapsack problem, the generalized assignment problem and the bin-packing problem with sigmoid utilities. We merge approximation algorithms from discrete optimization with algorithms from continuous optimization to develop approximation algorithms for these NP-hard problems with sigmoid utilities.     

A hybrid heuristic algorithm for the 2D variable-sized bin packing problem

In this paper, we consider the two-dimensional variable-sized bin packing problem (2DVSBPP) with guillotine constraint. 2DVSBPP is a well-known NP-hard optimization problem which has several real applications. A mixed bin packing algorithm (MixPacking) which combines a heuristic packing algorithm with the Best Fit algorithm is proposed to solve the single bin problem, and then a backtracking algorithm which embeds MixPacking is developed to solve the 2DVSBPP. A hybrid heuristic algorithm based on iterative simulated annealing and binary search (named HHA) is then developed to further improve the results of our Backtracking algorithm. Computational experiments on the benchmark instances for 2DVSBPP show that HHA has achieved good results and outperforms existing algorithms.     

LP-based online scheduling: from single to parallel machines

We study classic machine sequencing problems in an online setting. Specifically, we look at deterministic and randomized algorithms for the problem of scheduling jobs with release dates on identical parallel machines, to minimize the sum of weighted completion times: Both preemptive and non-preemptive versions of the problem are analyzed. Using linear programming techniques, borrowed from the single machine case, we are able to design a 2.62-competitive deterministic algorithm for the non-preemptive version of the problem, improving upon the 3.28-competitive algorithm of Megow and Schulz. Additionally, we show how to combine randomization techniques with the linear programming approach to obtain randomized algorithms for both versions of the problem with competitive ratio strictly smaller than 2 for any number of machines (but approaching two as the number of machines grows). Our algorithms naturally extend several approaches for single and parallel machine scheduling. We also present a brief computational study, for randomly generated problem instances, which suggests that our algorithms perform very well in practice. A preliminary version of this work appears in the Proceedings of the 11th conference on integer programming and combinatorial optimization (IPCO), Berlin, 8–10 June 2005.     

On nonsmooth V-invexity and vector variational-like inequalities in terms of the Michel–Penot subdifferentials

In this paper, we establish some results which exhibit an application for Michel–Penot subdifferential in nonsmooth vector optimization problems and vector variational-like inequalities. We formulate vector variational-like inequalities of Stampacchia and Minty type in terms of the Michel–Penot subdifferentials and use these variational-like inequalities as a tool to solve the vector optimization problem involving nonsmooth V-invex function. We also consider the corresponding weak versions of the vector variational-like inequalities and establish various results for the weak efficient solutions.     

A Relaxation of a Min-Cut Problem in an Anisotropic Continuous Network

Strang [18] introduced optimization problems on a Euclidean domain which are closely related with problems in mechanics and noted that the problems are regarded as continuous versions of famous max-flow and min-cut problems. In [15] we generalized the problems and called the generalized problems max-flow and min-cut problems of Strang's type. In this paper we formulate a relaxed version of the min-cut problem of Strang's type and prove the existence of optimal solutions under some suitable conditions. The conditions are essential. In fact, there is an example of the relaxed version which has no optimal solutions if the conditions are not fulfilled. We give such an example in the final section. Accepted 8 October 1998