Spelling suggestions: "subject:"branchandbound"" "subject:"branchesaround""
11 |
Theoretically and computationally improving branch and bound through multivariate branching with internal cutting planesLee, Jin Hua January 1900 (has links)
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.
|
12 |
An investigation of algorithms for the solution of integer programming problemsAbdul-Hamid, Fatimah January 1995 (has links)
No description available.
|
13 |
Stochastic branch & bound applying target oriented branch & bound method to optimal scenario tree reductionStix, Volker January 2002 (has links) (PDF)
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
|
14 |
Résolution exacte de problèmes de localisation de services bi-objectifs en variables mixtes / Exact algorithm for multi-objective mixed integer programming problemsDelmée, Quentin 19 October 2018 (has links)
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.
|
15 |
A solution scheme of satisfiability problem by active usage of totally unimodularity property.January 2003 (has links)
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
|
16 |
Network models with generalized upper bound side constraintsBolouri, Maryam 27 July 1989 (has links)
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
|
17 |
Computational investigation of cutting techniques for integer programming /Puttapanom, Sutanit. January 2003 (has links)
Thesis (M.S.)--University of Missouri-Columbia, 2003. / Typescript. Includes bibliographical references (leaves 110-113). Also available on the Internet.
|
18 |
Computational investigation of cutting techniques for integer programmingPuttapanom, Sutanit. January 2003 (has links)
Thesis (M.S.)--University of Missouri-Columbia, 2003. / Typescript. Includes bibliographical references (leaves 110-113). Also available on the Internet.
|
19 |
Progressive disaggregation for fixed charge network flow problemsAdaniya, Oscar 05 1900 (has links)
No description available.
|
20 |
Verification of branch and bound algorithms applied to water distribution network designHailer, Angelika Christina January 2006 (has links)
Zugl.: Hamburg, Techn. Univ., Diss., 2006
|
Page generated in 0.0424 seconds