Software Tool to Find the Bounds of Objective Functions
for a Class of One-Dimensional Bin Packing Problems
Gennady Fedulov
I. Vekua Institute of Applied Mathematics, Tbilisi State University
0186, Tbilisi, 2 University str., Georgia
Konstantin Babalyan
Moscow Institute of Physics and Technology
141700, Moscow Region, Dolgoprudniy, Institute lane, 9, Russia
Abstract
We present a software tool solving 22 combinatorial models that are semantically close to a known One-Dimensional Bin Packing Problem. All models have a large number of practical applications in the different areas. The goal is to deliver a comfortable tool to the users to solve their packing problems. Tool gives several important results, whereof main two are the following: the best approximate solution and the best objective function bound, that the tool can produce within a given time limit. Using the bounds we evaluate a quality of approximate solutions as a measure of closeness to the optimal solutions. The tool consists of four parts: User Interface, Solver, Interactive Packing and Intelligent Games (12 games) for children of any age.
Currently, the software tool can be accepted on the link http://www.fedulov.ge .
Keywords: bin packing, objective function bound, approximate solution,
initial reduction, estimation corridor, software tool
1. Introduction
We present a Software Tool solving 22 combinatorial models that are semantically close to a known One-Dimensional Bin Packing Problem (1DBPP). We called our set of models "One-Dimensional Bin Packing Class". All the models have a large practical application in the different areas: one-dimensional cutting stock, packing the musical files on CDs, packing the files to the different formats, pasting the stamps into the covers, RAM fragmentation, schedule theory, container packing, loading the objects to the knapsacks and others. General description of the class is the following. Given a set of items , each item has a weight and a cost , . We need to divide the initial set into disjoint subsets with the given properties, where , , . All subsets are independent to each other and order of items within each subset is arbitrary. We assume that initial data contains only non-negative integer numbers. The initial set of weights can be presented in a more compact form: }, where, , is group of equal weights , is a frequency. Parameter is a number of different weights and plays an important role in solving a problem to optimality: as a rule, the more is the more is the total time of finding an optimal solution. In Section 2 we present the One-Dimensional Bin Packing Class. In Section 3 we describe our Solution Approach. In Section 4 we give a description of Software Tool. Our results and conclusions are presented in Sections 5 and 6.
2. One-Dimensional Bin Packing Class
Model 1. Basic model I.
Given a fixed set , , is a a capacity of th bin, , where and . The task is to pack into : , , where is a content of th bin. An answer is YES if we can pack into and NO otherwise.
Model 2. Basic model II.
Given a fixed list of pairs , , , the and are a capacity and a quota of th bin respectively, , where and . The task is to pack into : , .
An answer is YES if we can pack into and NO otherwise. If we set all then we get Model 1.
Model 3. Classical Bin Packing.
We need to divide into a minimum number of disjoint subsets: , , where is a bin capacity as a maximum threshold.
Model 4. Bin Covering.
We need to divide into a maximum number of disjoint subsets: ,
, where is a bin quota as minimum threshold.
Model 5. Bin Packing & Bin Covering I.
We need to divide into a minimum number of disjoint subsets:
, , where and are the lower and upper thresholds, respectively. If we setthen we get Model 3.
Model 6. Bin Packing & Bin Covering II.
This model is similar to Model 5 but the task is to find a maximum number of disjoint subsets. If we set then we get Model 4.
Model 7. Schedule Theory I.
In this model a number of bins is fixed. The task is to find a minimal bin size in order to divide into disjoint subsets: , .
Model 8. Schedule Theory II.
Given a list of positive real numbers . The task is to find a minimum positive integer number in order to pack into , where .
In case of all we get Model 7.
Model 9. Bin Packing with the decreasing capacities.
Given a sequence of bin capacities , ,
We need to find a minimal number in order to pack into
: , .
If we set all = then we get Model 3.
Model 10. Bin Covering with the decreasing quotas.
Given a sequence of bin quotas , ,
We need to find a maximal number in order to pack into
: , . If we set all = then we get Model 4.
Model 11. Bin Packing with a range of bin capacities.
Given a range of bin capacities. The task is to find an optimal bin capacity : , where is a result of solving Model 3.
Model 12. Maximal loading of weights.
Given a fixed set , , is a capacity of th bin, . The task is to find a subset in order to pack into and a total weight , where, , ,
is a content of subset .
Model 13. Maximal loading of costs.
This model is similar to Model 12. Given a fixed set ,
, is a capacity of th bin, . The task is to find a subset in order to pack into and a total cost , where , , .
Model 14. Minimal covering of weigths.
Given a fixed set , , is a capacity of th bin, . The task is to find a subset in order to pack into and , where , , .
Model 15. Maximal covering of costs.
This model is similar to Model 14. Given a fixed set , , is a capacity of th bin, . The task is to find a subset in order to pack into and a total cost , where , , .
Model 16. Minimal total capacity of subset of bins.
Given a fixed set , , is a capacity of th bin, . The task is to find a subset in order to pack into and a total bin capacity , where, , ,
,
Model 17. Minimal total cost of subset of bins.
This model is similar to Model 16. Given two fixed sets and , , and is a capacity and a cost of th bin respectively, , The task is to find a subset in order to pack into and a total bin cost , where , is a cost of subset ,
, , ,
Model 18. Maximal total quota of subset of bins.
Given a fixed set , , is a quota of th bin.
The task is to find a subset in order to cover with and a total bin
quota, where ,
We need to divide into disjoint subsets : .
Model 19. Maximal total cost of subset of bins.
This model is similar to Model 18. Given two fixed lists and , , and is a quota and cost of th bin respectively. The task is to find a subset in order to cover with and a total bin cost , where ,
, , ,
Model 20. Bin Packing with a range of weight frequencies. We consider a multiset with a range . We hold fixed , for a given bin capacity and solve the Model 3. We need to find such a set so that a total waste , where .
Model 21. Bin Packing & Bin Covering with the decreasing capacities and quotas I.
Given a decreasing sequence of bin capacities and quotas , , , , , . The task is to find a minimal number in order to pack into a list of pairs , . If we set all and then we get Model 3. If we set all and then we get Model 5. If we set all then we get Model 9.
Model 22. Bin Packing & Bin Covering with the decreasing capacities and quotas II.
This model is similar to Model 21 but the task is to find a maximum number of disjoint subsets. If we set all and then we get Model 4. If we set all and then we get Model 6. If we set all then we get Model 10.
Two models of 22 are the basic ones. We called these models “Basic Model I “ and "Basic Model II". The basic models are NP-complete in strong sense with two possible results: YES if the model can be solved and NO otherwise. The rest of the models (3-22) are the optimization ones of finding the maximum or the minimum of the objective functions. These models are NP-hard in strong sense to find an optimal solution for any initial data. Models 3,7,8,9,11,12,13,16,17,20 can be reduced to the Basic Model I and models 4,5,6,10,14,15,18,19,21,22 can be reduced to the Basic Model II. Models 4,5,21,22 can either have solution or not. In practice, we can solve the problems to optimality within a given time limit for the small parameters and (Belov & Scheithauer, 2006), (Fukunaga & Korf, 2007), (Martello & Toth, 1990), (Schoenfield, 2002). For medium and large we use, as a rule, approximation algorithms. But here the problem of evaluating of the quality of the approximate solutions arises. In this case we find the bounds of objective function: a lower bound for the problems to minimum and an upper bound for the problems to maximum, where is an initial data of the model. For example, for the Model 3 we will write or , where .
We can write " approximate solution” for the minimization tasks and
“approximate solution" for the maximization tasks. Thus, we get a correlation for the both cases. Since is not known, we consider a value as a measure of closeness to . In case of we get an optimal solution. Finding of both fast and high-quality bounds has a practical importance, especially for the tasks with large. That’s why the problem of finding of the objective function bounds within a given time limit arises. We want to find different bounds and . Then the best lower and upper bounds will be chosen. Most of the models were chosen from (Coffman et al.,1998), (Csiric et al., 2001),
(Fukunaga & Korf, 2007), (Martello & Toth, 1990). We added new models 5,6,9,10,20,21,22.
At present Classical Bin Packing is a more known model. There are many exact and approximation algorithms of solving this problem. It would be quite interesting to evaluate a behavior of Aproximation Agorithms () in worst case for any initial data by formula , where and are the real numbers, , . For example, there is a theoretical result (Johnson, 1974) for a well-known fast approximation algorithm (First Fit by Decreasing). A complexity of is equal to and measure of closeness in worst case. A survey of Bin Packing theoretical results is presented in (Coffman et al.,1997). However, most of the effective approximation algorithms don't have theoretical results for worst case. Now a question arises: how to find an asymptotic constant in an experimental way for any approximation algorithm? Our way of solving this problem is to find an experimental constant for any , .
3. Solution Approach
Our main goal is to find the best approximate solution and objective function bound within a given time limit. For each model, we find a bound: a lower bound for the models to minimum and an upper bound for the models to maximum. This bound is found within time, where is a given time limit and is a fraction of , . In case of we use the whole time limit to find the bound of objective function only. This bound can be found in a time . From here on we find the best approximate solution within the time limit . This solution can be found in a time too. Our algorithms produce a sequence of the bounds and approximate solutions for the models to minimum and a sequence of the approximate solutionsand bounds for the models to maximum, where and . The and are the trivial lower bound and approximate solution for the models to minimum and the trivial both approximate solution and upper bound for the models to maximum. For example, for Model 3 (Classical Bin Packing) we set the , and . Then we try to find an optimal solution within a time limit . An optimal solution obviously cannot always be found in . Thus our strategy is of three consecutive steps: finding of the best objective function bound within , best approximate solution within and optimal solution within . We developed a problem-oriented estimation technology of building of the objective function bounds for each of the models. This technology can be used as a basis to form the bounds for the other models that use an idea of dividing an initial set into disjoint subsets with the given properties. The technology is of two parts: Initial Reduction and Estimation Corridor. These parts are interlinked closely. The results of the first part are used in the second part and vice versa. The Initial Reduction part is of a series of algorithms to reduce an initial data to a reduced data. We called these algorithms , , , , and .