![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The paper presents a new approach to significantly reduce the number of sub-problems required to verify optimality in the branch and bound algorithm. The branch and bound algorithm is used to solve linear integer models and these models have application in areas such as scheduling, resource allocation, transportation, facility allocation and capital budgeting. The single constraint of the knapsack linear integer problem (KLIP) is reformulated in such a way that the number of standard branch and bound sub-problems required to verify optimality is significantly reduced. Computational results of the proposed approach on randomly generated KLIPs are also presented.
Public Interest Statement
Resource constraints often arise in all studies. Mathematical classification is generally based on intrinsic property of the situation. One such problem in optimization has been described by a generic name, “Knapsack Problem”, meaning that the knapsack has a finite limited capacity and our interest is to fit in that knapsack as much as possible from the available opportunities. Its applications arise in various areas. A typical knapsack constraint, which deals with only positive numbers, can be written as:
Here, are the known amounts of resource that will be used per unit and
represent the unknown integers to be determined with some objective to be achieved. This paper reformulates the above constraint and reduces the required computational effort. This reformulation may have applications in other areas, which requires further attention.
1. Introduction
The general linear integer programming (LIP) problem has many applications in real life, for example, they arise in set covering, travelling salesman, assignment, transportation, knapsack, capital budgeting, facility location, timetabling and airline scheduling. Many of these applications have been presented in Taha (Citation2004) and Winston (Citation2004), where these problems have been formulated as a linear integer programming (LIP) model. Because of real-life applications, see Chinneck (Citation2004), the LIP model has attracted so much attention from researchers, yet a consistent and efficient general purpose method has not been developed. We are not aware of any polynomial time algorithm for the general LIP model. In fact, the LIP model is NP complete and a polynomial algorithm for the LIP is believed not to exist. This paper presents a new approach, which takes advantage of the presence of a single constraint to solve a knapsack linear integer problem (KLIP). The problem is reformulated in such a way that the number of standard branch and bound sub-problems required to verify optimality is significantly reduced. Computational results of the proposed approach on randomly generated KLIPs are also presented.
A mathematical statement of the knapsack problem is given in Section 2 and in Section 3, a few problems are discussed where the branch and bound (B & B) performance is poor. We have categorized these problems according to the possible source leading to poor performance. These problems have been subdivided in seven classes. Knapsack constraint reformulation is presented in Section . A summary of the computational experiments on randomly generated problems is presented in Section 5 and finally, the paper has been concluded in Section 6.
2. The knapsack linear integer problem
such that:(1)
(1)
where , b and
are given nonnegative constants, and and
are integer valued quantities and
.
3. A collection of LIP models where the B & B method performs poorly
3.1. Standard branch and bound algorithm
The B & B algorithm was first proposed by Land and Doig (Citation1960) for solving integer programs. The algorithm was further modified by Dakin (Citation1965) to solve both pure and mixed integer programs. The B & B algorithm in general relies on the usual strategy of first relaxing the integer problem into a linear programming (LP) model. If the linear programming optimal solution is an integer then, the optimal solution to the integer problem has been obtained and the search concludes. If the LP optimal solution is not an integer, then a variable with a fractional value is selected to create two sub-problems such that part of the feasible region is discarded without eliminating any of the feasible integer solutions. The process is repeated on all variables with fractional values until an integer solution is found, see Bealie (Citation1979), Beasley (Citation1996), Mitchell and Lee (Citation2001), Taha (Citation2004) and Winston (Citation2004). In this paper, the standard B & B refers to that version of the B & B algorithm proposed by Dakin (Citation1965) and we assume that there are no state-of-art branching rules, cuts or pricing.
In the following, several problems have been presented where B & B performance is poor.
3.2. Complexity of the standard B & B method with numerical illustrations
The worst case complexity of the B & B algorithm is discussed for the LIP, which is NP Complete. The number of sub-problems can easily reach unmanageable levels even for very small problems. In this section, we present some classes of the LIP models that cause serious challenges for the standard B & B algorithm.
Class 1: Knapsack binary linear problem, taken from Kumar, Munapo, and Jones (Citation2007) .
such that:
where or
and n is even.
The behaviour of the standard branch and bound method for n = 4, 6, 8, 16 and 40 is given in Table .
Table 1. Complexity of the problem as n value increases
Class 2: Step pattern formed by negative signs
The second class is the integer problems that have constraints with negative signs forming a step pattern. Also, the coefficients in the objective function as well as the constants on the right-hand side of the constraints are significantly different. The standard B & B algorithm on this class of problems can behave in a very bizarre way if the branching is not properly managed. The following three numerical illustrations 3.2.1–3.2.2 were taken from Kumar et al. (Citation2007). Numerical illustration 3.2.3 was slightly modified.
Numerical illustration 3.2.1
such that:
where and integer.
Note the step formed by the minus signs and the fluctuating values of constants in the right-hand side. Using the standard B & B algorithm, it generated 209 sub-problems to verify optimality. The optimal solution is: and
.
Numerical illustration 3.2.2(2)
(2)
such that:
where and integer.
Using the standard B & B algorithm, it generated 605 sub-problems to verify optimality. The optimal solution is: and
Numerical illustration 3.2.3
such that:
where and integer.
The standard B & B requires 2101 sub-problems to verify optimality, which is given by: and
.
The other classes of linear integer problems that make the B & B an unreliable method are presented in Classes 3 to 7.
Class 3: Complementary constraints
such that:
where and integer,
and b are integers and constants,
and
Also note that the first constraint in this class of problem contains both positive and negative coefficients. The two constraints are complementary in the sense that when added give a zero on the left-hand side. More examples are given as Class 3.1 and Class 3.2.
Class 3.1
such that:
where and integer.
Class 3.2
such that:
where and integer.
Class 4: Binary knapsack problem
This is an extension of class 1. The problem becomes more difficult for the standard B & B algorithm if it is slightly modified as given in below.
such that:
where or 1
and n are even.
Class 4 has an alternate form also as was the case in Class 1. This alternate form will have the objective function as given below and constraints remain unchanged. This alternative objective is given by: Minimize .
For the Class 4 problem, the behaviour of the B & B method for n = 4, 6, 8 and 16 becomes worse as given in Table .
Table 2. Complexity of the problem as n value increases
Class 5: Knapsack problem: A pure integer case
Mere changing of variables from binary to pure integer makes any LIP worse for the standard B & B algorithm. For example, consider:
such that:
where and integer
,
is odd and n is even.
Once again, an alternate problem for class 5 is when objective function is changed but constraints remain unchanged. This alternative objective function is given by:
The computational behaviour of the standard branch and bound method for n = 4, 6, 8 and 16 is given in Table .
Table 3. Complexity of the problem as n value increases
Class 6: Hard Knapsack Problems
such that:
where and integer
and
are odd and n even. Once again, an alternate problem can be for a minimizing objective function given by: Minimize:
.
The standard B & B method cannot solve most of these problems for large values of . For example, a knapsack problem with the parameters:
, and
becomes
such that:
where and integer
.
The standard B & B method requires 7,449 sub-problems to verify the optimal solution. For large values of , the knapsack problems cannot be solved by standard B & B algorithm on its own.
Class 7: Hard pure integer models
The following general integer model is also very difficult to solve by the standard B & B algorithm on its own.
such that :
where or some large number. There must be one large number in the objective row and
or some large odd number. There must be one large odd number in every row and in every column. Further, it must satisfy
.
A numerical illustration of the above model
such that:
where and integer.
A total of 653 standard B & B sub-problems are required to verify optimality. The optimal solution is: and
.
There are so many other classes of difficult integer models that occur in real life. These include the travelling salesman problem (TSP) and the generalized assignment problem (GAP). At the moment, it may be very difficult to come up with an efficient general purpose algorithm. Instead, it makes sense to study one class and then propose an efficient way of solving it. In this paper, the KLIP is targeted because of its special features.
4. Reformulation of the knapsack problem
The knapsack problem has special features that we can take advantage of for reformulation. This problem has only one constraint and all coefficients are nonnegative. The coefficients in the constraint of any KLIP can be arranged in ascending order i.e.(3)
(3)
This is possible for all KLIP models since all coefficients are nonnegative, and since is the smallest one can rewrite the expression (2) as follows:
Let for
then (2) can be expressed as given by (3).
Repeating the process given in (3), where smallest coefficient is , we obtain
(4)
(4)
If the process repeated until there is no term left, the transformed constraint will become as shown in (5).(5)
(5)
Note, are integer valued quantities and
The KLIP becomes(6)
(6)
such that:(7)
(7)
Once again, are integer value quantities and
Phase 1: Solve reformulated problem (7) using the standard B & B method with the integral restriction on only. If solution is an integer, then it is also optimal to the original KLIP, else go to Phase 2.
Phase 2: Continue with the standard B & B method used in Phase 1 but this time with the integral restriction extended to also.
This reformulated model is easier to solve than the original KLIP. The standard B & B method takes a significantly smaller number of sub-problems to verify optimality on the reformulated model than the original KLIP. The proposed approach works better if are different.
Numerical Illustrations 4.1
such that:(8)
(8)
where and integer
.
The standard B & B method takes 231 sub-problems to verify the optimal solution of (8), which is given by: and
Note the coefficients, when arranged in an increasing order are given by 12, 18, 20, 24 and 29. Thus, we have and
After the reformulation, the KILP (8) becomes (9).
Such that :(9)
(9)
Note that the coefficients 12, 6, 2, 4 and 5 are different.
Phase 1: Where and integer
. In phase 1, there is no integral restriction on the variables
. The number of sub-problems necessary to verify the optimal solution reduces to 37, resulting once again in the solution given by:
and
.
Note that Phase 2 was not necessary since Phase 1 solution was optimal and the number of sub-problems required to reach the optimal solution dropped from 231 to 37, which is a significant reduction. This shows that the reformulation is effective for the KLIP. Here are two more illustrations before we present a summary of computational experiments.
Numerical illustration 4.2
Such that :(10)
(10)
where and integer
This KLIP is a special case from Class 6. The number of sub-problems reduces from 7449 to only 5 after reformulation. Optimal solution was obtained in Phase 1.
Numerical illustration 4.3
such that:(11)
(11)
where and integer
and
.
This KLIP comes from Class 1 but in this case, variables are integer and not necessarily binary. The number of sub-problems reduces from over 30, 000 to only 11 after reformulation and the optimal solution was obtained in Phase 1.
5. Computational experiments
Fifty randomly generated knapsack problems of different sizes were used in the analysis. The objective of the computational experiments was to determine whether the number of sub-problems decrease after the reformulation. The computational results were tabulated as given in Tables and . MATLAB R2013 (version 8.2) running on an Intel Pentium Dual desktop (Dual core G2020 2.9 GHz CPU, 2GB DDR3 1333 RAM) was used for the computational experiments. In all the fifty cases, it was observed that the number of standard B & B sub-problems decreased significantly after reformulation, as can be seen from the results in Tables and .
Table 4. Computational experiments on randomly generated Knapsack problems
Table 5. More computational experiments on randomly generated Knapsack problems
6. Conclusions
What has emerged from the computational experiments is that the number of standard B & B sub-problems required to verify optimality can be significantly reduced by reformulation. In all the fifty cases analysed, the number of sub-problems were significantly reduced after reformulation. So many improvements have been done on the branch and bound algorithm in terms of addition of cuts to get the branch and cut algorithm (Brunetta, Conforti, & Rinaldi, Citation1997; Mitchell, Citation2001; Padberg & Rinaldi, Citation1991), pricing to get the branch and price algorithm (Barnhart, Johnson, Nemhauser, Savelsbergh, & Vance, Citation1998; Salvelsbergh, Citation1997) and also combining the two improved versions to get the branch cut and price hybrid algorithm (Barnhart, Hane, & Vance, Citation2010; Fukasawa et al., Citation2006; Ladnyi, Ralphs, & Trotter, Citation2001). Here, in this paper, we have we have achieved improvement in the standard B & B algorithm on its own before combining it with other approaches. In addition to using cuts and pricing within the context of a branch and bound algorithm, preprocessing given in Savelsbergh (Citation1994) can reduce the number of sub-problems needed to verify optimality. Reformulation proposed in this paper significantly reduces the number of B & B sub-problems required to verify optimality.
In subsequent publications, attempt will be made to:
(1) | Extend the proposed constraint reformulation to the general LIP model, when applicable. | ||||
(2) | Search for the mathematical reasons that give rise to the efficiency observed. | ||||
(3) | Extend the reformaulation concept to other situations. |
Acknowledgements
Authors are grateful to the referees for their constructive suggestions for improving this paper.
Additional information
Funding
Notes on contributors
Elias Munapo
Elias Munapo and Santosh Kumar have interest in discrete optimization methods and they have put forward several ideas that may provide further insight into discrete optimization and linear programming methodology. Their approaches need an appropriate software support, which is a challenge not only for the authors but for the field of optimization. They have made direct contributions to the field of integer programming and special models like quadratic assignment, travelling salesman, network routing by link weight modification. The current paper on knapsack constraint reformulation opens up many interesting questions that can only be answered provided this paper reaches researchers in discrete optimization. We believe, our work challenges software developers to raise funds, support university research for higher degrees. We can provide supervision, if required and hope universities will welcome such a move from the software companies.
References
- Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch and price column generation for solving huge integer programs. Operations Research, 46, 316–329.
- Barnhart, C., Hane, C. A., & Vance, P. H. (2010). Using branch-and-price-and-cut to solve origin--destination integer multicommodity flow problems. Operations Research, 48, 318–326.
- Bealie, E. M. L. (1979). Branch and bound methods for mathematical programming systems. Annals of Discrete Mathematics, 5, 201–219.
- Beasley, J. E. (Ed.). (1996). Advances in linear and integer programming. New York, NY: Oxford University Press.
- Benders, J. F. (1962). Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik, 4, 238–252.
- Brunetta, L., Conforti, M., & Rinaldi, G. (1997). A branch and cut algorithm for the equicut problem. Mathematical Programming, 78, 243–263.
- Chinneck, J. W. (2004). Practical optimization: A gentle introduction lecture notes. Retrieved from http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf
- Dakin, R. J. (1965). A tree search algorithm for mixed integer programming problems. The Computer Journal, 8, 250–255.
- Fukasawa, R., Longo, H., Lysgaard, J., Poggi de Aragao, M., Uchoa, E., & Werneck, R. F. (2006). Robust branch-and-cut-price for the capacitated vehicle routing problem. Mathematical Programming Series A, 106, 491–511.
- Kumar, S., Munapo, E., & Jones, B. C. (2007). An integer equation controlled descending path to a protean pure integer program. Indian Journal of Mathematics, 49, 211–237.
- Land, A. H., & Doig, A. G. (1960). An automatic method for solving discrete programming problems. Econometrica, 28, 497–520.
- Ladanyi, L., Ralphs, T. K., & Trotter, L. E. (2001). Branch, cut and price: Sequential and parallel. In N. Naddef & M. Jenger (Eds.), Computational combinatorial optimization (p. 223–260). Berlin: Springer.
- Mitchell, J. E., & Lee, E. K. (2001). Branch and bound methods for integer programming. In C. A. Floudas & P. M. Pardalos (Eds.), Encyclopedia of optimization. Dordrecht: Kluwer Academic Publishers.
- Mitchell, J. E. (2001). Branch and cut algorithms for integer programming. In C. A. Floudas & P. M. Pardalos (Eds.), Encyclopedia of optimization. Kluwer Academic Publishers.
- Padberg, M., & Rinaldi, G. (1991). A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33, 60–100.
- Savelsbergh, M. W. P. (1994). Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing, 6, 445–454.
- Salvelsbergh, M. W. P. (1997). A branch and price algorithm to solve the generalized assignment problem. Operations Research, 45, 381–841.
- Taha, H. A. (2004). Operations research: An introduction (7th ed.).Upper Saddle River, NJ: Pearson Educators.
- Winston, W. L. (2004). Operations research applications and algorithms (4th ed.).Belmont, CA: Duxbury Press.