Linear and combinatorial programming

Author: Katta G. Murty
Publisher: John Wiley & Sons
ISBN: UOM:39015000495427
Release Date: 1976
Genre: Mathematics

Formulation of linear programs; The simplex method; The geometry of the simplex method; Duality in linear programming; Revised simplex method; The dual simplex method; Parametric linear programs; Sensitivity analysis; Degeneracy in linear programming; Bounded variable linear programs; Primal algorithm for the transportation problem; Network algorithms; Formulation of integer and combinatorial programming problems; Cutting plane methods for integer programming; The branch and bound approach; Complementarity problems; Numerically stable forms of the simplex method; Computational efficiency.

Theory of Linear and Integer Programming

Author: Alexander Schrijver
Publisher: John Wiley & Sons
ISBN: 0471982326
Release Date: 1998-07-07
Genre: Mathematics

Theory of Linear and Integer Programming Alexander Schrijver Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands This book describes the theory of linear and integer programming and surveys the algorithms for linear and integer programming problems, focusing on complexity analysis. It aims at complementing the more practically oriented books in this field. A special feature is the author's coverage of important recent developments in linear and integer programming. Applications to combinatorial optimization are given, and the author also includes extensive historical surveys and bibliographies. The book is intended for graduate students and researchers in operations research, mathematics and computer science. It will also be of interest to mathematical historians. Contents 1 Introduction and preliminaries; 2 Problems, algorithms, and complexity; 3 Linear algebra and complexity; 4 Theory of lattices and linear diophantine equations; 5 Algorithms for linear diophantine equations; 6 Diophantine approximation and basis reduction; 7 Fundamental concepts and results on polyhedra, linear inequalities, and linear programming; 8 The structure of polyhedra; 9 Polarity, and blocking and anti-blocking polyhedra; 10 Sizes and the theoretical complexity of linear inequalities and linear programming; 11 The simplex method; 12 Primal-dual, elimination, and relaxation methods; 13 Khachiyan's method for linear programming; 14 The ellipsoid method for polyhedra more generally; 15 Further polynomiality results in linear programming; 16 Introduction to integer linear programming; 17 Estimates in integer linear programming; 18 The complexity of integer linear programming; 19 Totally unimodular matrices: fundamental properties and examples; 20 Recognizing total unimodularity; 21 Further theory related to total unimodularity; 22 Integral polyhedra and total dual integrality; 23 Cutting planes; 24 Further methods in integer linear programming; Historical and further notes on integer linear programming; References; Notation index; Author index; Subject index

Advances in Combinatorial Optimization

Author: Moustapha Diaby
Publisher: World Scientific
ISBN: 9789814704892
Release Date: 2016-01-28
Genre: Mathematics

' Combinational optimization (CO) is a topic in applied mathematics, decision science and computer science that consists of finding the best solution from a non-exhaustive search. CO is related to disciplines such as computational complexity theory and algorithm theory, and has important applications in fields such as operations research/management science, artificial intelligence, machine learning, and software engineering. Advances in Combinatorial Optimization presents a generalized framework for formulating hard combinatorial optimization problems (COPs) as polynomial sized linear programs. Though developed based on the ''traveling salesman problem'' (TSP), the framework allows for the formulating of many of the well-known NP-Complete COPs directly (without the need to reduce them to other COPs) as linear programs, and demonstrates the same for three other problems (e.g. the ''vertex coloring problem'' (VCP)). This work also represents a proof of the equality of the complexity classes "P" (polynomial time) and "NP" (nondeterministic polynomial time), and makes a contribution to the theory and application of ''extended formulations'' (EFs). On a whole, Advances in Combinatorial Optimization offers new modeling and solution perspectives which will be useful to professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general. Contents:IntroductionBasic IP Model Using the TSPBasic LP Model Using the TSPGeneric LP Modeling for COPsNon-Symmetry of the Basic (TSP) ModelNon-Applicability of Extended Formulations TheoryIllustrations for Other NP-Complete COPs Readership: Professionals, graduate students and researchers who are either involved in routing, scheduling and sequencing decision-making in particular, or in dealing with the theory of computing in general. Key Features:The book offers a new proof of the equality of the complexity classes "P" and "NP"Although our approach is developed using the framework of the TSP, it has natural analogs for the other problems in the NP-Complete class thus providing a unified framework for modeling many combinatorial optimization problems (COPs)The book makes a contribution to the theory and application of Extended Formulations (EFs) refining the notion of EFs by separating the case in which that notion is degenerate from the case in which the notion of EF is well defined/meaningful. It separates the case in which the addition of redundant constraints and variables (for the purpose of establishing EF relations) matters from the case in which the addition of redundant constraints and variables does not matterKeywords:Linear Programming;Convex Optimization;Combinatorial Optimization;Traveling Salesman Problem;NP-Complete Problems;P versus NP'

Combinatorial Optimization

Author: Christos H. Papadimitriou
Publisher: Courier Corporation
ISBN: 9780486320137
Release Date: 2013-04-26
Genre: Mathematics

This graduate-level text considers the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; local search heuristics for NP-complete problems, more. 1982 edition.

Combinatorial Optimization

Author: Bernhard Korte
Publisher: Springer
ISBN: 9783662560396
Release Date: 2018-03-13
Genre: Mathematics

This comprehensive textbook on combinatorial optimization places special emphasis on theoretical results and algorithms with provably good performance, in contrast to heuristics. It is based on numerous courses on combinatorial optimization and specialized topics, mostly at graduate level. This book reviews the fundamentals, covers the classical topics (paths, flows, matching, matroids, NP-completeness, approximation algorithms) in detail, and proceeds to advanced and recent topics, some of which have not appeared in a textbook before. Throughout, it contains complete but concise proofs, and also provides numerous exercises and references. This sixth edition has again been updated, revised, and significantly extended. Among other additions, there are new sections on shallow-light trees, submodular function maximization, smoothed analysis of the knapsack problem, the (ln 4+ɛ)-approximation for Steiner trees, and the VPN theorem. Thus, this book continues to represent the state of the art of combinatorial optimization.

Geometric Algorithms and Combinatorial Optimization

Author: Martin Grötschel
Publisher: Springer Science & Business Media
ISBN: 9783642978814
Release Date: 2012-12-06
Genre: Mathematics

Historically, there is a close connection between geometry and optImization. This is illustrated by methods like the gradient method and the simplex method, which are associated with clear geometric pictures. In combinatorial optimization, however, many of the strongest and most frequently used algorithms are based on the discrete structure of the problems: the greedy algorithm, shortest path and alternating path methods, branch-and-bound, etc. In the last several years geometric methods, in particular polyhedral combinatorics, have played a more and more profound role in combinatorial optimization as well. Our book discusses two recent geometric algorithms that have turned out to have particularly interesting consequences in combinatorial optimization, at least from a theoretical point of view. These algorithms are able to utilize the rich body of results in polyhedral combinatorics. The first of these algorithms is the ellipsoid method, developed for nonlinear programming by N. Z. Shor, D. B. Yudin, and A. S. NemirovskiI. It was a great surprise when L. G. Khachiyan showed that this method can be adapted to solve linear programs in polynomial time, thus solving an important open theoretical problem. While the ellipsoid method has not proved to be competitive with the simplex method in practice, it does have some features which make it particularly suited for the purposes of combinatorial optimization. The second algorithm we discuss finds its roots in the classical "geometry of numbers", developed by Minkowski. This method has had traditionally deep applications in number theory, in particular in diophantine approximation.

A First Course in Combinatorial Optimization

Author: Jon Lee
Publisher: Cambridge University Press
ISBN: 0521010128
Release Date: 2004-02-09
Genre: Business & Economics

A First Course in Combinatorial Optimization is a text for a one-semester introductory graduate-level course for students of operations research, mathematics, and computer science. It is a self-contained treatment of the subject, requiring only some mathematical maturity. Topics include: linear and integer programming, polytopes, matroids and matroid optimization, shortest paths, and network flows. Central to the exposition is the polyhedral viewpoint, which is the key principle underlying the successful integer-programming approach to combinatorial-optimization problems. Another key unifying topic is matroids. The author does not dwell on data structures and implementation details, preferring to focus on the key mathematical ideas that lead to useful models and algorithms. Problems and exercises are included throughout as well as references for further study.

Linear Programming

Author: Saul I. Gass
Publisher: Courier Corporation
ISBN: 9780486432847
Release Date: 2003
Genre: Mathematics

Comprehensive, well-organized volume, suitable for undergraduates, covers theoretical, computational, and applied areas in linear programming. Expanded, updated edition; useful both as a text and as a reference book. 1995 edition.

Understanding and Using Linear Programming

Author: Jiri Matousek
Publisher: Springer Science & Business Media
ISBN: 9783540307174
Release Date: 2007-07-04
Genre: Mathematics

The book is an introductory textbook mainly for students of computer science and mathematics. Our guiding phrase is "what every theoretical computer scientist should know about linear programming". A major focus is on applications of linear programming, both in practice and in theory. The book is concise, but at the same time, the main results are covered with complete proofs and in sufficient detail, ready for presentation in class. The book does not require more prerequisites than basic linear algebra, which is summarized in an appendix. One of its main goals is to help the reader to see linear programming "behind the scenes".

Concepts of Combinatorial Optimization

Author: Vangelis Th. Paschos
Publisher: John Wiley & Sons
ISBN: 9781119015079
Release Date: 2014-08-08
Genre: Mathematics

Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts: - On the complexity of combinatorial optimization problems, presenting basics about worst-case and randomized complexity; - Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming; - Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.

Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization

Author: Levent Tunçel
Publisher: American Mathematical Soc.
ISBN: 9781470428112
Release Date: 2016-05-05

Since the early 1960s, polyhedral methods have played a central role in both the theory and practice of combinatorial optimization. Since the early 1990s, a new technique, semidefinite programming, has been increasingly applied to some combinatorial optimization problems. The semidefinite programming problem is the problem of optimizing a linear function of matrix variables, subject to finitely many linear inequalities and the positive semidefiniteness condition on some of the matrix variables. On certain problems, such as maximum cut, maximum satisfiability, maximum stable set and geometric representations of graphs, semidefinite programming techniques yield important new results. This monograph provides the necessary background to work with semidefinite optimization techniques, usually by drawing parallels to the development of polyhedral techniques and with a special focus on combinatorial optimization, graph theory and lift-and-project methods. It allows the reader to rigorously develop the necessary knowledge, tools and skills to work in the area that is at the intersection of combinatorial optimization and semidefinite optimization. A solid background in mathematics at the undergraduate level and some exposure to linear optimization are required. Some familiarity with computational complexity theory and the analysis of algorithms would be helpful. Readers with these prerequisites will appreciate the important open problems and exciting new directions as well as new connections to other areas in mathematical sciences that the book provides.

Integer Programming and Combinatorial Optimization

Author: Jon Lee
Publisher: Springer
ISBN: 9783319075570
Release Date: 2014-05-17
Genre: Computers

This book constitutes the refereed proceedings of the 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014, held in Bonn, Germany, in June 2014. The 34 full papers presented were carefully reviewed and selected from 143 submissions. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, computation, and applications in these areas. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.

Integer Programming and Combinatorial Optimization

Author: Oktay Günlük
Publisher: Springer Science & Business Media
ISBN: 9783642208065
Release Date: 2011-05-10
Genre: Computers

This book constitutes the proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011, held in New York, USA in June 2011. The 33 papers presented were carefully reviewed and selected from 110 submissions. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization with the aim to present recent developments in theory, computation, and applications. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.

Integer and Combinatorial Optimization

Author: Laurence A. Wolsey
Publisher: John Wiley & Sons
ISBN: 9781118627259
Release Date: 2014-08-28
Genre: Mathematics

Rave reviews for INTEGER AND COMBINATORIAL OPTIMIZATION "This book provides an excellent introduction and survey of traditional fields of combinatorial optimization . . . It is indeed one of the best and most complete texts on combinatorial optimization . . . available. [And] with more than 700 entries, [it] has quite an exhaustive reference list."-Optima "A unifying approach to optimization problems is to formulate them like linear programming problems, while restricting some or all of the variables to the integers. This book is an encyclopedic resource for such formulations, as well as for understanding the structure of and solving the resulting integer programming problems."-Computing Reviews "[This book] can serve as a basis for various graduate courses on discrete optimization as well as a reference book for researchers and practitioners."-Mathematical Reviews "This comprehensive and wide-ranging book will undoubtedly become a standard reference book for all those in the field of combinatorial optimization."-Bulletin of the London Mathematical Society "This text should be required reading for anybody who intends to do research in this area or even just to keep abreast of developments."-Times Higher Education Supplement, London Also of interest . . . INTEGER PROGRAMMING Laurence A. Wolsey Comprehensive and self-contained, this intermediate-level guide to integer programming provides readers with clear, up-to-date explanations on why some problems are difficult to solve, how techniques can be reformulated to give better results, and how mixed integer programming systems can be used more effectively. 1998 (0-471-28366-5) 260 pp.

The Linear Ordering Problem

Author: Rafael Martí
Publisher: Springer Science & Business Media
ISBN: 3642167292
Release Date: 2011-01-03
Genre: Computers

Faced with the challenge of solving the hard optimization problems that abound in the real world, existing methods often encounter great difficulties. Important applications in business, engineering or economics cannot be tackled by the techniques that have formed the predominant focus of academic research throughout the past three decades. Exact and heuristic approaches are dramatically changing our ability to solve problems of practical significance and are extending the frontier of problems that can be handled effectively. This monograph details state-of-the-art optimization methods, both exact and heuristic, for the LOP. The authors employ the LOP to illustrate contemporary optimization technologies as well as how to design successful implementations of exact and heuristic procedures. Therefore, they do not limit the scope of this book to the LOP, but on the contrary, provide the reader with the background and practical strategies in optimization to tackle different combinatorial problems.