Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer Programs (IP) are a class of discrete optimization problems that are utilized commercially to improve the function of various systems. Implementation is often aimed at reaching optimal financial objectives with constraints on resources and operation. While incredibly beneficial, IPs are NP-complete, with many IP models being unsolvable. Branch and bound (BB) is the primary method employed to solve IPs to optimality. BB is an exhaustive approach to enumerating all potential integer solutions for a given IP. By utilizing a hierarchical tree structure to tabulate progression of enumeration, BB can guarantee an optimal solution in finite time. However, BB can take an exponential number of iterations to solve an IP. Computationally, this can result in a tree structure that exceeds a computer’s memory capacity, or a prohibitively long solution time. This thesis introduces a modified version of BB call the Quaternary Hyperplane Branching Algorithm (QHBA). QHBA employs a quaternary branching scheme, utilizes hyperplane branching constraints, and generates internal cutting planes to increase efficiency. Implementation of these advancements theoretically improves QHBA in comparison to traditional BB. It can also be shown that QHBA guarantees an optimal solution in a finite number of iterations. A short computational study shows that QHBA results in a 26.7% decrease in solution times when compared to CPLEX, a commercially available IP solver.

No description available.

In this article a new branch & bound method is described. It uses an artificial target to improve its bounding capabilities. Therefore the new approach is faster compared to the classical one. It is applied to the stochastic problem of optimal scenario tree reduction. The aspects of global optimization are emphasized here. All necessary components for that problem are developed and some experimental results underline the benefits of the new approach. (author's abstract) / Series: Working Papers on Information Systems, Information Business and Operations

Dans ce travail, nous nous intéressons à la résolution exacte de problèmes de localisation de service en variables mixtes. Les problèmes de programmation linéaire bi-objectif en variables mixtes ont été très étudiés dans les dernières années, mais uniquement dans un contexte générique. De même, les problèmes de localisation de services bi-objectif n’ont été étudiés que dans un cas purement discret. Nous considérons dans un premier temps le problème de localisation de services bi-objectif sans capacité. Afin de le résoudre, nous adaptons la méthode de pavage par boîtes proposée pour le cas discret. Les boîtes rectangulaires deviennent triangulaires dans le cas mixte. De plus, leur exploration est grandement facilitée, ce qui déplace la difficulté du problème dans l’énumération et le filtrage de ces boîtes. Différentes stratégies d’énumération sont proposées. Le problème de localisation de services bi-objectif avec capacité est ensuite considéré. Tout d’abord, une adaptation de la méthode de pavage par boîtes triangulaires est réalisée pour le cas avec capacité. Cependant, la nature du problème rend cette méthode beaucoup plus limitée. Nous considérons ensuite une méthode en deux phases dont la principale routine d’exploration repose sur une adaptation d’un algorithme de branch and bound initialement proposé par Beasley, dans le contexte bi-objectif. Les résultats expérimentaux sur des instances aux caractéristiques variées attestent de la pertinence des méthodes que nous proposons. / The purpose of this work is the exact solution of biobjective mixed-integer facility location problems. Biobjective mixed integer linear programming problem have been largely studied in recent years but only in the generic context. The same way, the study of biobjective facility location problems has been restricted to the discrete case. We consider first the bi-objective uncapacitated facility location problem. To solve it, we adapt the box paving method proposed for the discrete case. Rectangular boxes become triangular. Moreover, their exploration becomes considerably easier. The difficulty of the problem is therefore translated to the enumeration and the filtering of these boxes. Different enumeration strategies are proposed. Next, we consider the bi-objective capacitated facility location problem. We first propose an adaptation of the triangular box paving method to the capacitated case. However, the structure of the problem highly limits the method. Thus, we consider a two phase method. The main exploration routine is based on the adaptation of a branch and bound algorithm proposed by Beasley that we adapt to the bi-objective context. Experimental results on various instances show the efficiency of the proposed methods.

by Mei Long. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 93-98). / Abstracts in English and Chinese. / Table of Contents --- p.v / Abstract --- p.viii / Acknowledgements --- p.x / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Satisfiability Problem --- p.1 / Chapter 1.2 --- Motivation of the Research --- p.1 / Chapter 1.3 --- Overview of the Thesis --- p.2 / Chapter 2 --- Satisfiability Problem --- p.4 / Chapter 2.1 --- Satisfiability Problem --- p.5 / Chapter 2.1.1 --- Basic Definition --- p.5 / Chapter 2.1.2 --- Phase Transitions --- p.5 / Chapter 2.2 --- History --- p.6 / Chapter 2.3 --- The Basic Search Algorithm --- p.8 / Chapter 2.4 --- Some Improvements to the Basic Algorithm --- p.9 / Chapter 2.4.1 --- Satz by Chu-Min Li --- p.9 / Chapter 2.4.2 --- Heuristics and Local Search --- p.12 / Chapter 2.4.3 --- Relaxation --- p.13 / Chapter 2.5 --- Benchmarks --- p.14 / Chapter 2.5.1 --- Specific Problems --- p.14 / Chapter 2.5.2 --- Randomly Generated Problems --- p.14 / Chapter 2.6 --- Software and Internet Information for SAT solving --- p.16 / Chapter 2.6.1 --- Stochastic Local Search Algorithms (incomplete) --- p.16 / Chapter 2.6.2 --- Systematic Search Algorithms (complete) --- p.16 / Chapter 2.6.3 --- Some useful Links to SAT Related Sites --- p.17 / Chapter 3 --- Integer Programming Formulation for Logic Problem --- p.18 / Chapter 3.1 --- SAT Problem --- p.19 / Chapter 3.2 --- MAXSAT Problem --- p.19 / Chapter 3.3 --- Logical Inference Problem --- p.19 / Chapter 3.4 --- Weighted Exact Satisfiability Problem --- p.20 / Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.22 / Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.22 / Chapter 4.2 --- Integer Programming Model for 3-SAT --- p.23 / Chapter 4.3 --- The Equivalence of the SAT and the IP --- p.23 / Chapter 4.4 --- Example --- p.24 / Chapter 5 --- Integer Solvability of Linear Programs --- p.27 / Chapter 5.1 --- Unimodularity --- p.27 / Chapter 5.2 --- Totally Unimodularity --- p.28 / Chapter 5.3 --- Some Results on Recognition of Linear Solvability of IP --- p.32 / Chapter 6 --- TU Based Matrix Research Results --- p.33 / Chapter 6.1 --- 2x2 Matrix's TU Property --- p.33 / Chapter 6.2 --- Extended Integer Programming Model for SAT --- p.34 / Chapter 6.3 --- 3x3 Matrix's TU Property --- p.35 / Chapter 7 --- Totally Unimodularity Based Branching-and-Bound Algorithm --- p.38 / Chapter 7.1 --- Introduction --- p.38 / Chapter 7.1.1 --- Enumeration Trees --- p.39 / Chapter 7.1.2 --- The Concept of Branch and Bound --- p.42 / Chapter 7.2 --- TU Based Branching Rule --- p.43 / Chapter 7.2.1 --- How to sort variables based on 2x2 submatrices --- p.43 / Chapter 7.2.2 --- How to sort the rest variables --- p.45 / Chapter 7.3 --- TU Based Bounding Rule --- p.46 / Chapter 7.4 --- TU Based Branch-and-Bound Algorithm --- p.47 / Chapter 7.5 --- Example --- p.49 / Chapter 8 --- Numerical Result --- p.57 / Chapter 8.1 --- Experimental Result --- p.57 / Chapter 8.2 --- Statistical Results of ILOG CPLEX --- p.59 / Chapter 9 --- Conclusions --- p.61 / Chapter 9.1 --- Contributions --- p.61 / Chapter 9.2 --- Future Work --- p.62 / Chapter A --- The Coefficient Matrix A for Example in Chapter 7 --- p.64 / Chapter B --- The Detailed Numerical Information of Solution Process for Exam- ple in Chapter 7 --- p.66 / Chapter C --- Experimental Result --- p.67 / Chapter C.1 --- "# of variables: 20, # of clauses: 91" --- p.67 / Chapter C.2 --- "# of variables: 50, # of clauses: 218" --- p.70 / Chapter C.3 --- # of variables: 75，# of clauses: 325 --- p.73 / Chapter C.4 --- "# of variables: 100, # of clauses: 430" --- p.76 / Chapter D --- Experimental Result of ILOG CPLEX --- p.80 / Chapter D.1 --- # of variables: 20´ة # of clauses: 91 --- p.80 / Chapter D.2 --- # of variables: 50，#of clauses: 218 --- p.83 / Chapter D.3 --- # of variables: 75，# of clauses: 325 --- p.86 / Chapter D.4 --- "# of variables: 100, # of clauses: 430" --- p.89 / Bibliography --- p.93

The objective of this thesis is to develop and computationally test a new algorithm for the class of network models with generalized upper bound (GUB) side constraints. Various algorithms have been developed to solve the network with arbitrary side constraints problem; however, no algorithm that exploits the special structure of the GUB side constraints previously existed. The proposed algorithm solves the network with GUB side constraints problem using two sequences of problems. One sequence yields a lower bound on the optimal value for the problem by using a Lagrangean relaxation based on relaxing copies of some subset of the original variables. This is achieved by first solving a pure network subproblem and then solving a set of single constraint bounded variable linear programs. Because only the cost coefficients change from one pure network subproblem to another, the optimal solution for one subproblem is at least feasible, if not optimal, for the next pure network subproblem. The second sequence yields an upper bound on the optimal value by using a decomposition of the problem based on changes in the capacity vector. Solving for the decomposed problem corresponds to solving for pure network subproblems that have undergone changes in lower and/or upper bounds. Recently developed reoptimization techniques are incorporated in the algorithm to find an initial (artificial) feasible solution to the pure network subproblem. A program is developed for solving the network with GUB side constraints problem by using the relaxation and decomposition techniques. The algorithm has been tested on problems with up to 200 nodes, 2000 arcs and 100 GUB constraints. Computational experience indicates that the upper bound procedure seems to perform well; however, the lower bound procedure has a fairly slow convergence rate. It also indicates that the lower bound step size, the initial lower bound value, and the lower and upper bound iteration strategies have a significant effect on the convergence rate of the lower bound algorithm. / Graduation date: 1990

Thesis (M.S.)--University of Missouri-Columbia, 2003. / Typescript. Includes bibliographical references (leaves 110-113). Also available on the Internet.

Thesis (M.S.)--University of Missouri-Columbia, 2003. / Typescript. Includes bibliographical references (leaves 110-113). Also available on the Internet.

No description available.

Zugl.: Hamburg, Techn. Univ., Diss., 2006