No description available.

No description available.

Mixed integer programming (MIP) provides an important modeling and decision support tool for a wide variety of real-life problems. Unfortunately, practical MIPs are large-scale in size and pose serious difficulties to the available solution methodology and software. / This thesis presents a novel solution approach for large-scale mixed integer programming that integrates three bodies of research: interior point methods, decomposition techniques and branch-and-bound approaches. The combination of decomposition concepts and branch-and-bound is commonly known as branch-and-price, while the integration of decomposition concepts and interior point methods lead to the analytic centre cutting plane method (ACCPM). Unfortunately, the use of interior point methods within branch-and-bound methods could not compete with simplex based branch-and-bound due to the inability of "warm" starting. / The motivation for this study stems from the success of branch-and-price and ACCPM in solving integer and non-differentiable optimization problems respectively and the quest for a method that efficiently integrates interior-point methods and branch-and-bound. / The proposed approach is called an Interior Point Branch-and-Price method (IP-B&P) and works as follows. First, a problem's structure is exploited using Lagrangean relaxation. Second, the resulting master problem is solved using ACCPM. Finally, the overall approach is incorporated within a branch-and-bound scheme. The resulting method is more than the combination of three different techniques. It addresses and fixes complications that arise as a result of this integration. This includes the restarting of the interior-point methods, the branching rule and the exploitation of past information as a warm start. / In the first part of the thesis, we give the details of the interior-point branch-and-price method. We start by providing, discussing and implementing new ideas within ACCPM, then detail the IP-B&P method and its different components. To show the practical applicability of IP-B&P, we use the method as a basis for a new solution methodology for the production-distribution system design (PDSD) problem in supply chain management. In this second part of the thesis, we describe a two-level Lagrangean relaxation heuristic for the PDSD. The numerical results show the superiority of the method in providing the optimal solution for most of the problems attempted.

We propose an analytic center cutting plane algorithm for semidefinite programming (SDP). Reformulation of the dual problem of SDP into an eigenvalue optimization, when the trace of any feasible primal matrix is a positive constant, is well known. We transform the eigenvalue optimization problem into a convex feasibility problem. The problem of interest seeks a feasible point in a bounded convex set, which contains a full dimensional ball with &egr;(<1) radius and is contained in a compact convex set described by matrix inequalities, known as the set of localization. At each iteration, an approximate analytic center of the set of localization is computed. If this point is not in the solution set, an oracle is called to return a p-dimensional semidefinite cut. The set of localization then, is updated by adding the semidefinite cut through the center. We prove that the analytic center is recovered after adding a p-dimensional semidefinite cut in O(plog(p + 1)) damped Newton's iteration and that the ACCPM with semidefinite cuts is a fully polynomial approximation scheme. We report the numerical result of our algorithm when applied to the semidefinite relaxation of the Max-Cut problem.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.