ABSTRACT

A large number of real-world planning problems called Combinatorial Optimization Problems share the following properties: They are Optimization Problems, are easy to state, and have a finite but usually very large number of feasible solutions. Lexi-Search is by far the mostly used tool for solving large scale NP-hard Combinatorial Optimization problems. Lexi-Search is, however, an algorithm paradigm, which has to be filled out for each specific problem type, and numerous choices for each of the components exist. Even then, principles for the design of efficient Lexi-Search algorithms have emerged over the years. Although Lexi-Search methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. The motivation of the calculation of the lower bounds is based on ideas frequently used in solving problems. Computationally, the algorithm extended the size of problem and find better solution.