Abstract
The chapter presents a new approach to improve the verification process of optimality for the general knapsack linear integer problem. The general knapsack linear integer problem is very difficult to solve. A solution for the general knapsack linear integer problem can be accurately estimated, but it can still be very difficult to verify optimality using the brach and bound related methods. In this chapter, a new objective function is generated that is also used as a more binding equality constraint. This generated equality constraint can be shown to significantly reduce the search region for the branch and bound-related algorithms. The verification process for optimality proposed in this chapter is easier than most of the available branch and bound-related approaches. In addition, the proposed approach is massively parallelizable allowing the use of the much needed independent parallel processing.
TopIntroduction
The general linear integer programming (LIP) problem has numerous real life applications. Linear integer problems are common as practical problems and include:
Knapsack models have many applications in real life and in this paper we select, land conservation, prioritizing conservation projects, optimizing environmental economic policies in a protection zone, maximizing benefits in environmental project selection and plastic bag waste management as examples
A consistent efficient general purpose algorithm for the general LIP is still at large. In other words we are not aware of any efficient consistent general purpose algorithm for this problem as given in Taha(2017). The fact is that this problem is very difficult to solve and heuristics are normally used to approximate solutions in reasonable times (Kumar et. al, 2018). Research on linear integer programming is a very active ongoing process because of the very important applications in real life. The first exact method was a cutting plane approach proposed by Gomory and is given in Gomory (1958), Mitchell (2002) and Salkin (1991). Land and Doig (1960) came up with the branch and bound algorithm. Dakin (1965) improved the branch and bound and this is also explained Bealie (1979). Padberg and Rinald (1991) combined the branch and bound and cuts to come up with a better method which is now called the branch and cut. See Brunetta, Conforti and Rinaldi (1997) and Mitchell (2001) for more on branch and cut algorithms. Salvelsbergh (1997) used pricing within the context of a branch and bound to come up with a good procedure (branch and price) for the linear integer models. See Barnhart et. al (1998) for more on branch and price algorithms. Ladányi, Ralphs and Trotter (2001) combined pricing and cuts and used these in a branch and boud setting. See Barnhart, Hane and Vance (2000) and Fukasawa (2006) for more on branch, cut and price procedure.
TopThe Knapsack Problem And The Known Integer Solution
Suppose the solution of knapsack linear integer problem is known and this solution satisfies (2).
(2) Where
Z0 is the optimal value, We can verify the optimality of this solution by solving (3).
Key Terms in this Chapter
Variable: Is a quantity that needs to be determined in order to solve the linear or nonlinear problem.
Combinatoral Explosion: Is the rapid growth of the complexity of a problem is affected by the number variables, constraints, and bounds of the problem.
Algorithm: A procedure or set of rules to be followed in problem-solving operations, specifically by a computer.
Objective Function: Is a mathematical expression that minimizes or maximizes a linear or nonlinear problem.
Parallel Processing: Is a method of simultaneously breaking up and running program tasks on multiple microprocessors, thereby reducing processing time.
Optimal Solution: A feasible solution at the point where the objective function reaches its maximum/minimum value.
Branch and Bound Method: This is a solution method which partitions the feasible solution space into smaller subsets of solutions.
Knapsack Problem: Is a problem in combinatorial optimization with an objective function and only one constraint.