From: randyp@visionplace.com (Randy Poe) Subject: Re: Optimization problem Date: Tue, 19 Sep 2000 05:22:55 GMT Newsgroups: sci.math Summary: Bin-packing problems On Mon, 18 Sep 2000 15:07:45 -0600, Virgil wrote: >In article <8q5n4g$1rv@sarangi.cs.columbia.edu>, >bhat@sarangi.cs.columbia.edu (Dinkar Bhat) wrote: > >> Hi, >> >> I have an optimization problem, and I am sure it is a standard >> type. I just dont know what it is , and would appreiate info/pointers >> to the problem. >> >> There are n objects each of some size, and the size >> varies from object to object. They have to be put into >> fixed size bins, the number of bins is not specified apriori. >> The problem is to come up with the minimum number of bins such that all >> objects have been put into some bin. No object is of size >size >> of a bin. >> >> >> Thanks >> Dinkar > >These kind of problem is called packing problems. I took a course in combinatorial optimization (of which this is one example). Many such problems are very hard in the sense of computational complexity, i.e., it is not feasible to find a best solution in reasonable time. What I remember being especially interesting is that there is often a pretty good solution which can be achieved with fairly naive algorithms. Furthermore, there are often results putting bounds on just how good the pretty good solution is. For instance, even though the exact solution is not known, it can be proved that a given algorithm gets you within sqrt(2) of the optimum value. It seems to me that packing problems came into this class of problems with provably-good solutions. As I recall (this was all a long time ago) there are two common approaches to simple-minded algorithms: (1) "Greedy". In this case, it means pack the biggest object first. Then pack the biggest object that will still fit in that first bin, unless it's full. Proceed in any obvious way. (2) Linear Programming. When you write down the equations for a combinatorial problem, you often get something that looks like a linear program (linear objective function, linear inequality constraints), except that the variables are required to be integers. Well, if you remove the integer constraint, you can solve the problem with any good LP solver. Then round off to a valid integer solution. Remember, the solutions you get this way are good but not optimal. - Randy > >AFAIK, there is no complete solution method for such problems other that >a method of exhaustion, but there are some methods for finding fairly >good solutions in a short time. > > > >For example, for n objects, start with n bins numbered 1 to n (this is >clearly enough bins). Store the objects one at a time taken in >decreasing order of size into the lowest numbered bin into which they >will fit. When all objects are stored, count the number of non-empty >boxes. > >This method will not necessarily give the best packing, but it almost >always gives a fairly good one. ============================================================================== From: "Sébastien-Jérôme Hew" Subject: Re: Optimization problem Date: Tue, 19 Sep 2000 23:56:02 +1000 Newsgroups: sci.math Yes, based on the partition problem, this is an NP-hard combinatorial optimisation problem. There are exact methods which find the solution using integer programming, e.g., branch and bound, but the number of steps in such algorithms invariably increase drastically with problem size. In order to find a good, although possibly non-optimal solution, in a reasonable time, heuristic methods are used. There are many possible methods, e.g., best fit, first fit, sorted first fit, sorted best fit, etc. Sébastien Hew. [Non-quoted portions of previous post were quoted here --djr] ============================================================================== From: "glenn" Subject: Re: Optimization problem Date: Tue, 19 Sep 2000 17:20:48 +0300 Newsgroups: sci.math [Previous post was quoted in entirety --djr] In this case a possible formulation goes as follows: Let the lenghts of the objects form the vector a=(a_1, a_2,..., a_n). Let L be the length of the bin. Now a possible bin (not fully filled) has the form c.a, where "." denotes the inner product, and c is a n-vector. The i-th component of c is 1 iff the i-th object is being putted in the bin, 0 otherwise. Of course we have the restriction c.a<=L. What we want to find a a matrix C, having as rows vectors like c with the following restrictions: 1) Every row of C has 1's and 0's only. 1) In every column of C one and only one 1 exists. 2) If C_i is a row vector of C then C_i . a <=L, i=1,2,...,n. 3) The number of non-zero rows of C is minimal. If such a nxn matrix C is found, then the product C.a will give an optimal packing. ============================================================================== From: Ray Vickson Subject: Re: Optimization problem Date: Tue, 19 Sep 2000 11:50:53 -0400 Newsgroups: sci.math Dinkar Bhat wrote: > Hi, > > I have an optimization problem, and I am sure it is a standard > type. I just dont know what it is , and would appreiate info/pointers > to the problem. > > There are n objects each of some size, and the size > varies from object to object. They have to be put into > fixed size bins, the number of bins is not specified apriori. > The problem is to come up with the minimum number of bins such that all > objects have been put into some bin. No object is of size >size > of a bin. This "bin-packing" problem has some variants, one of which is the exact version you have given. These problems are NP-hard, but there are reasoably effective heuristics for obtaining approximation solutions. Typically, the best general-purpose methods are "first-fit" and "first-fit-decreasing". In "first-fit" method you start with object 1 and put it into bin 1, then go to object 2 and put in into bin 1 if you can, otherwise, put it into a new bin, etc. Always put the next object into the lowest numbered bin into which it will fit, or else into a new bin. In "first-fit-decreasing" you first sort the items into descending order of size and then do first fit. These have provable worst-case error bounds, in terms of which first-fit decreasing is a bit better than plain first-fit. See, eg., "Computers and Intractability;", by Garey and Johnson, Freeman (1979). > > Thanks > Dinkar -- R. G. Vickson Department of Management Sciences University of Waterloo Waterloo, Ontario, CANADA