An Evaluation Upon Theoretical Background For Using the Principle of Decomposition Methods For Integer Linear Programming

Within the field of mathematical programming, discrete optimization has become the focus of a vast body of research and development due to the increasing number of industries now employing it to model the decision analysis for their most complex systems. Mixed integer linear programming problems involve minimizing (or maximizing) the value of some linear function over a polyhedral feasible region subject to integrality restrictions on some of the variables. More formally, a mixed integer linear program (MILP) can be defined as

whereis a given cost vector,is the constraint matrix,is the right hand side, andis the index set of variables that are restricted to integer values. Two important special cases are when, which we refer to as a (pure) integer linear-program (ILP) and when, which we refer to as a linear program (LP). Solving an MILP is known to be an-hard problem in general. However, due to recent breakthroughs in both the underlying theory and available computer implementations, discrete optimization is now a viable tool for optimizing some of the most complex systems. We are just now beginning to understand the impact that discrete optimization can have in helping organizations optimize the efficiency of their processes. In the past two decades, MILP has seen widespread adoption in a large and diverse array of industries, including logistics, finance, medical research, engineering design, retail, and many others. In the following paragraphs, we attempt to put into context the direction of our research. For this purpose, we assume the reader has a working knowledge of the theory and practice of integer programming. One of the most successful algorithms developed to date for solving MILPs is the branch-and- bound method. Branch and bound is a divide-and-conquer approach that reduces the original problem to a series of smaller subproblems and then recursively solves each subproblem. This dissertation focuses on improve the performance of branch-and-bound methods. Most bounding procedures for MILPs are based on the iterative construction and improvement of polyhedral approximations of, the convex hull of feasible solutions. Solving an optimization problem over such a polyhedral approximation, provided it fully contains, produces a bound that can be used to drive a branch-and-bound algorithm. The effectiveness of the bounding procedure depends largely on how wellcan be approximated. The most straightforward approximation is the continuous approximation, consisting simply of the linear constraints present in the original formulation. The bound resulting from this approximation is frequently too weak to be effective, however. In such cases, it can be improved by dynamically generating additional polyhedral information that can be used to augment the approximation. Traditional dynamic procedures for augmenting the continuous approximation can be grouped roughly into two categories. Cutting-plane methods improve the approximation by dynamically generating half-spaces that containbut not the continuous approximation, i.e., valid inequalities. These half-spaces are then intersected with the current approximation, thereby improving it. With this approach, valid inequalities are generated by solution of an associated separation problem. Generally, the addition of each valid inequality reduces the hyper volume of the approximating polyhedron, resulting in a potentially improved bound. Because they dynamically generate part of the description of the final approximating polyhedron as the intersection of half-spaces (an outer representation), we refer to cutting-plane methods as outer approximation methods. Traditional column-generation methods, on the other hand, improve the approximation by dynamically generating the extreme points of a polyhedron containing, which is again intersected with the continuous approximation, as in the cutting-plane method, to yield a final approximating polyhedron. In this case, each successive extreme point is generated by solution of an associated optimization problem and at each step, the hypervolume of the approximating polyhedron is increased. Because decomposition methods dynamically generate part of the description of the approximating polyhedron as the convex hull of a finite set (an inner representation), we refer to these methods as inner approximation methods.

We now formalize some of the notions described in the introduction. Implementing a branch-and- bound algorithm for solving an ILP requires a procedure that generates a lower bound on the optimal value. The most commonly used method of bounding is to formulation. The LP bound is given by and is obtained by solving a linear program with the original objective function cover the polyhedron . It is clear that since . This LP relaxation is usually much easier to solve than the original ILP. butmay be arbitrarily far away fromin general, so we need to consider more effective procedures. A description that is represented with a polynomial number of variables and constraints is called compact. In most cases, the description ofis compact, it can be represented explicitly, and the bound computed using a standard linear programming algorithm. To improve the LP bound, decomposition methods construct a second approximating polyhedron that can be intersected with to form a better approximation. Unlike, this second polyhedron usually has a description of exponential size, and we must generate portions of its description dynamically. Such a dynamic procedure is the basis both for cutting-plane methods, which generate an outer approximation, and for column-generation methods, such as the Dantzig-Wolfe method and the Lagrangian method, which generate inner approximations. we consider the relaxation- Where for some and is the convex hull of.

constraintssuch that . We denote bythe polyhedron described by the inequalitiesand bythe polyhedron described by the inequalities. Thus,And . We often refer toas the relaxed polyhedron. For the decomposition to be effective, we must have that, so that the bound obtained by optimizing overis at least as good as the LP bound and strictly better for some objective functions. The description ofmust also be

optimizing overand thereby, for separating arbitrary real vectors from. We are deliberately using the term effective here to denote an algorithm that has an acceptable average-case running time, since this is more relevant than worst-case behavior in our computational framework. Note, throughout this research, we are assuming that the efficiency of the algorithm used for solving OPTis not affected by the structure of the cost vector. Traditional decomposition methods can all be viewed as techniques for iteratively computing the bound

Sometime around the late 1980s, the recognition of mixed integer programming models as an important paradigm for solving real business problems had encouraged a number of commercial software vendors towards a large investment in tackling the solution of bigger and more difficult MILPs. The computational strides made in developing methods for solving generic MILPs throughout the 1990s were dramatic. Despite this, there are still many classes of important MILPs that are extremely difficult for today's best solvers. Exploiting the special structure of certain models has long been an active field of research. In the early 1990s, several research groups recognized the potential of abstracting the general branch-and-cut framework in the form of a software framework with user hooks for adding problem- specific routines. This led to the development of several popular frameworks, for example, MINTO, MIPO , bc-opt , SIP , ABACUS , and SYMPHONY. The majority of these frameworks are focused on providing an infrastructure for implementing branch-and-bound algorithms in which the user could provide their own specific methods for customizing both the branching and the bounding operations. In the 1990s, most of the work using these frameworks focused on problem-specific cutting planes that were incorporated into the framework to produce a branch-and-cut algorithm. At the same time, column-generation methods were also gaining popularity. Of the list above, the only frameworks that provided some facility for branch-and-price were MINTO. ABACUS, and SYMPHONY In all cases, the end-goal was to automate the most common elements of the branch- and-cut (or price) algorithm, allowing the user to focus on the problem- generic manner to allow- complete flexibility for the user to override just about every algorithmic function. This added to the wide array of problem types and methods that could be implemented within the frameworks. Much less common in these frameworks was support for integrated methods like branch-and-price- and-cut. Although there is some early mention of these ideas, there are very few implementations discussed in the literature that use any of these frameworks.

In this paper, we present two major categories of methods for generating bounds by iterative construction of polyhedral approximations of the convex hull of feasible solutions to some MILP. Traditional Decomposition Methods - In this paper, we review three classical approaches that take advantage of implicit generation of a polyhedral approximation. By finding the common threads among each of these methods, we have generalized the overall approach into four steps. The first step is an initialization step where we define the initial polyhedral approximation of. This is done using either valid inequalities, in the case of outer methods, or using extreme points, in the case of inner methods. In the second step, the master problem is solved which generates primal and or dual solution information over the current approximation. Then, in the third step, a subproblem is solved which will be used to improve the approximation. In the case of outer methods, the subproblem is a separation problem, where we try to find valid inequalities (for) that are violated by the current primal solution. In the case of inner methods, the subproblem is an optimization problem where we try to find extreme points ofusing the current dual solution. In the fourth and final step, we use the inequalities (or extreme points) found in step three and update the current approximation. By viewing all of these methods within the same conceptual framework, we are able to draw several connections among the methods. Integrated Decomposition Methods - While traditional decomposition approaches build either an inner or an outer approximation, integrated decomposition methods build both an inner and an outer approximation. These methods follow the same basic logic as traditional decomposition methods, except that the master problem is required to generate both primal and dual solution information, Decompose-and-Cut - In this paper we extend this idea to the traditional cutting-plane method and examine a relatively unknown decomposition-based algorithm we refer to as decompose-cind- cut. First, we review the well-known template paradigm for separation and introduce a concept called structured separation. Then, we describe a separation algorithm called decompose-and-cut that is closely related to the integrated decomposition methods.

Generic cutting planes have long been one of the most important factors in the success of branch- and-cut codes. In the past decade, there have been major advances in increasing the variety and strength of valid inequalities that can be generated and used to solve generic MILPs. Up until now, the use of cutting planes with inner methods such as price-and-cut has been limited to specific applications. When structured cuts are known and provably facet-defining, it is typical for them to dominate generic classes in terms of strength. In real-world applications, however, it is common for the user not to have any knowledge of the polyhedral structure of the model. EVen with knowledge of a specific class of facet-defining valid inequalities, an efficient separation algorithm may not be known, forcing one to rely on heuristics that give no guarantee of quality. In such cases, methods for generating generic classes of valid inequalities may be necessary to solve a given problem. This fact has long been understood with respect to branch-and-cut codes, and all solvers include at least a basic implementation of separation algorithms for the most common classes of valid inequalities. However, until now, there have been no branch-and-price-and-cut frameworks that have successfully allowed for direct integration of generic cutting planes.

The success of decomposition-based methods in real applications shows the potential for this area to make a positive impact on the field of mathematical programming. Until now, the study of these methods has been somewhat disconnected and application-specific. This thesis has provided a way to consider these various methods under one framework. The software framework DIP has the potential for opening the door to various new areas of research related to decomposition methods. The ease-of-use and extensibility of the framework should allow users to compare and contrast these methods, as well as numerous extensions, under one uniform computational environment. From this, computational studies can be easily conducted which with this, we can also gain much insight into further areas of computational research. Specifically, the use of hybrid methods that combine different components of the numerous algorithms seems promising. DIP allows the user to easily experiment with these ideas which should generate several new avenues of research. For every successful application we show in this study, there are twice as many applications we tried where the performance of the inner approximation methods (even with integrated cuts) performs quite poorly when compared to more standard approaches like branch-and-cut.

• A. Schrijver. Theory of Linear and Integer Programming. Wiley, Chichester, 2006.

• D.Applegate, R. Bixby, V. Chv´atal, and W. Cook. Implementing the Dantzig-Fulkerson- Johnson algorithm for large traveling salesman problems. Mathematical Programming, 97:91–153, 2003.

• E.Balas, S. Ceria, and G. Cornu´ejols. Mixed 0-1 programming by lift and-project in a branchand- cut framework. Management Science, 42:1229–1246, 1996.

• G.B. Dantzig and P. Wolfe. Decomposition principle for linear programs. Operations Research, 8(1):101–111, 1960.

• H.Crowder, E. L. Johnson, and M. W. Padberg. Solving large scale zero-one linear programming problems. Operations Research, 31:803–834, 2003.

• J.E. Beasley. Lagrangean relaxation. In C.R. Reeves, editor, Modern Heuristic Techniques for Combinatorial Optimization. Wiley, 1993.

• L.A. Wolsey. Integer Programming. Wiley, New York, 1998.

• M.L. Fisher. The Lagrangian relaxation method for solving integer programming problems. Management Science, 27:1–18, 2001.

 R.Bixby, M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling. MIP: Theory and practice - closing the gap. In Proceedings of the 19th IFIP TC7 Conference on System Modelling and Optimization, pages 19–50, Deventer, The Netherlands, The Netherlands, 2000. Kluwer, B.V.

linear programming. In Proceedings of the Ninth INFORMS Computing Society Conference, pages 61–76, 2005.