Logic and Integer Programming / Edition 1

Logic and Integer Programming / Edition 1

by H. Paul Williams
ISBN-10:
0387922792
ISBN-13:
9780387922799
Pub. Date:
04/21/2009
Publisher:
Springer US

Hardcover

Current price is , Original price is $89.95. You
Select a Purchase Option (2009)
  • purchase options
    $60.64 $89.95 Save 33% Current price is $60.64, Original price is $89.95. You Save 33%.
  • purchase options

Overview

Logic and Integer Programming / Edition 1

Paul Williams, a leading authority on modeling in integer programming, has written a concise, readable introduction to the science and art of using modeling in logic for integer programming. Written for graduate and postgraduate students, as well as academics and practitioners, the book is divided into four chapters that all avoid the typical format of definitions, theorems and proofs and instead introduce concepts and results within the text through examples. References are given at the end of each chapter to the more mathematical papers and texts on the subject, and exercises are included to reinforce and expand on the material in the chapter. Methods of solving with both logic and IP are given and their connections are described. Applications in diverse fields are discussed, and Williams shows how IP models can be expressed as satisfiability problems and solved as such.

Product Details

ISBN-13: 9780387922799
Publisher: Springer US
Publication date: 04/21/2009
Series: International Series in Operations Research & Management Science , #130
Edition description: 2009
Pages: 200
Product dimensions: 6.30(w) x 9.30(h) x 0.50(d)

About the Author

H.P.(Paul) Williams is Professor of Operational Research at the London School of Economics. He has a degree in Mathematics from Cambridge University and a PhD in Mathematical Logic from Leicester University (having studied under the late Professor R.L.Goodstein). His research work has been primarily in Linear and Integer Programming. This proposed book combines his knowledge in all these areas.

He worked for IBM on developing software for and helping clients model and solve problems in Linear and Integer Programming. This work was continued in a number of academic posts. He has held chairs at Edinburgh and Southampton Universities and published many papers in these areas (listed on his web site). He is particularly well known for his book Model Building in Mathematical Programming (Wiley) first published in 1978 and now in a fourth edition. It has been translated into a number of other languages.

Table of Contents

1 An Introduction to Logic 1

1.1 The Purpose of Logic: Philosophical: Computational 1

1.2 Logical Inference and Consistency 2

1.3 The Propositional Calculus 3

1.3.1 Connectives and Truth Tables 3

1.3.2 Equivalent Statements 5

1.3.3 Disjunctive and Conjunctive Normal Forms 6

1.3.4 Complete Sets of Connectives 10

1.3.5 The Calculus of Indications 11

1.3.6 Venn Diagrams 13

1.4 The Predicate Calculus 14

1.4.1 The Use of Quantifiers 15

1.4.2 Prenex Normal Form 16

1.5 Decidable Fragments of Mathematics 18

1.5.1 The Theory of Dense Linear Order 18

1.5.2 Arithmetic Without Multiplication 20

1.6 References and Further Work 22

1.7 Exercises 22

2 Integer Programming 25

2.1 Linear Programming 25

2.1.1 The Dual of an LP Model 28

2.1.2 A Geometrical Representation of a Linear Programme 30

2.2 Integer Programming 35

2.2.1 The Branch-and-Bound Algorithm 38

2.2.2 The Convex Hull of an IP 43

2.3 The Use of 0-1 Variables 49

2.3.1 Expressing General Integer Variables as 0-1 Variables 49

2.3.2 Yes/No Decisions 50

2.3.3 The Facility Location Problem 50

2.3.4 Logical Decisions 51

2.3.5 Products of 0-1 Variables 53

2.3.6 Set-Covering, Packing and Partitioning Problems 53

2.3.7 Non-linear Problems 55

2.3.8 The Knapsack Problem 58

2.3.9 The Travelling Salesman Problem 58

2.3.10 Other Problems 60

2.4 Computational Complexity 60

2.4.1 Problem Classes and Instances 60

2.4.2 Computer Architectures and Data Structures 61

2.4.3 Polynomial and Exponential Algorithms 62

2.4.4 Non-deterministic Algorithms and Polynomial Reducibility 64

2.4.5 Feasibility Versus Optimisation Problems 65

2.4.6 Other Complexity Concepts 66

2.5References and Further Work 66

2.6 Exercises 68

3 Modelling in Logic for Integer Programming 71

3.1 Logic Connectives and IP Constraints 71

3.2 Disjunctive Programming 75

3.2.1 A Geometrical Representation 75

3.2.2 Mixed IP Representability 78

3.3 Alternative Representations and Tightness of Constraints 84

3.3.1 Disjunctive Versus Conjunctive Normal Form 86

3.3.2 The Dual of a Disjunctive Programme 89

3.4 Convexification of an IP Model 91

3.4.1 Splitting Variables 92

3.5 Modelling Languages Based On Logic 96

3.5.1 Algebraic Languages 96

3.5.2 The 'Greater Than or Equal' Predicate 98

3.6 References and Further Work 102

3.7 Exercises 102

4 The Satisfiability Problem and Its Extensions 105

4.1 Resolution and Absorption 106

4.2 The Davis-Putnam-Loveland (DPL) Procedure 109

4.3 Representation as an Integer Programme 109

4.4 The Relationship Between Resolution and Cutting Planes 111

4.5 The Maximum Satisfiability Problem 113

4.6 Simplest Equivalent Logical Statement 116

4.7 Horn Clauses: Simple Satisfiability Problems 119

4.8 Constraint Logic Programming 123

4.8.1 Modelling in CLP 124

4.8.2 Solving CLP Models 126

4.8.3 Hybrid CLP and IP systems 127

4.9 Solving Integer Programmes as Satisfiability Problems 129

4.10 Applications 134

4.10.1 Electrical Circuit Design Using Switches 134

4.10.2 Logical Net Design Using Gates 135

4.10.3 The Logical Analysis of Data (LAD) 137

4.10.4 Chemical-processing networks 139

4.10.5 Other Applications 140

4.11 References and Further Work 141

4.12 Exercises 142

References 145

Index 151

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews