Logic-Based Decision Support (eBook)

Mixed Integer Model Formulation

R.G. Jeroslow (Autor)

eBook Download: PDF

1989 | 1. Auflage
221 Seiten
Elsevier Science (Verlag)
978-0-08-086780-9 (ISBN)

Infos

This monograph is based on a series of lectures given by the author at the first Advanced Research Institute on Discrete Applied Mathematics, held at Rutgers University. It emphasizes connections between the representational aspects of mixed integer programming and applied logic, as well as discussing logic-based approaches to decision support which help to create more `intelligent' systems.

Dividing naturally into two parts, the first four chapters are an overview of mixed-integer programming representability techniques. This is followed by five chapters on applied logic, expert systems, logic and databases, and complexity theory. It concludes with a summary of open research issues and an attempt to extrapolate trends in this rapidly developing area.

Inhalt

Front Cover 1
Logic-Based Decision Support: Mixed Integer Model Formulation 4
Copyright Page 5
Contents 11
Introduction 18
PART I: MIXED-INTEGER MODEL FORMULATION 20
Lecture 1. Disjunctive Representations 22
1.1 Introduction 22
1.2 Some definitions and a basic result 26
1.3 Some small examples 31
1.4 Related Work 38
1.5 Exercises 38
Lecture 2. Furthtr Illustrations 40
2.1 Some further examples 40
2.2 A simplification in the disjunctive representation for some multiple rhs instances 49
2.3 'Separate' vs . 'joint' formulations 54
2.4 Exercises 58
Lecture 3. Constructions which Parallel Set Operations 60
3.1 Definitions and basic constructions 60
3.2 The union construction 62
3.3 Some other constructions 64
3.4 Some technical properties of the basic constructions 65
3.5 Composite constructions and 'structure' in MIP 66
3.6 Two central technical results 69
3.7 Hereditary sharpness 72
Lecture 4. Topics in Representability 74
4.1 Reformulation via distributive laws 74
4.2 Convex union representability 79
4.3 Using combinatorial principles in representability 82
4.4 Some experimental results 86
PART II: LOGIC-BASED APPROACHES TO DECISION SUPPORT 94
Lecture 5. Propositional Logic and Mixed Integer Programming 96
5.1 Introduction 96
5.2 A "natural deduction" system for propositional logic 99
5.3 Propositional logic as done by integer programming 102
5.4 Clausal chaining: a subroutine 107
5.5 Some properties of frequently-used algorithms of expert systems 112
5.6 The Davis-Putnam Algorithm in Two Forms 116
5.7 Some recent developments (December 1987) 117
5.8 Exercises 119
Lecture 6. A Primer on Predicate Logic 120
6.1 Introduction 120
6.2 Predicate logic: basic concepts, notation 122
6.3 Applications for problem-solving 128
Lecture 7. Computational Complexity above NP: A Retrospective Overview 136
7.1 Introduction 136
7.2 The fundamental distinction: conceptions vs . their instances 138
7.3 Two fundamental results 139
7.4 What if we increase expressability "a little bit"? 142
7.5 The Polynomial Hierarchy, Probabilistic Models, and Games 145
Lecture 8. Theorem-Proving Techniques which Utilise Discrete Programming 154
8.1 Reduction of Predicate Logic to a Structured Propositional Logic 155
8.2 Preliminary discussion 157
8.3 The algorithm framework 159
8.4 Illustrations and comments 163
8.5 A generalization: predicate logic together with linear constraints 167
Lecture 9. Spatial Embeddings for Linear and Logic Structures 170
9.1 Definition of an Embedding 170
9.2 Illustrations of embeddings 175
9.3 Results for predicate logic embeddings 176
9.4 Logic an pre-processing routines for MIP: an example via the DP/DPL algorithm 179
Lecture 10. Tasks Ahead 182
10.1 Three "top-down" Views of Mathematical Programming 182
10.2 Some research challenges related to these lectures 192
10.3 Some other research programs in the AI/OR Interface 193
10.4 Some programs and courses in the AI/OR Interface 194
10.5 Guessing Ahead 196
Illustrative Examples 200
Solutions to Examples 208
Bibliography 220

Produkt-Details

• Erscheint lt. Verlag: 1.2.1989
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Technik
• ISBN-10: 0-08-086780-4 / 0080867804
• ISBN-13: 978-0-08-086780-9 / 9780080867809