ACKNOWLEDGEMENTS

First, I would like to express my sincere gratitude to my two advisors, Dr. Faiz Al-Khayyal

and Dr. Shabbir Ahmed for their guidance and encouragements throughout the entire

course of my research. Without their excellent insights and invaluable suggestions, I could

not be able to complete this thesis.

I am grateful to Dr. Earl Barnes, Dr. Alex Shapiro and Dr. Matthew Realf for serving

as members of my committee and their valuable comments and suggestions.

Finally, I am deeply thankful to my parents, Bong-Nam Cheon and Sung-Hang Lee for

their support and encouragement. I owe special thanks to my wife, Jin-Ah Lim, and my

princess and prince, Esther and Ethan. Their support, patience, and love enabled me to

complete this thesis.

TABLE OF CONTENTS

DEDICATION iii

ACKNOWLEDGEMENTS iv

LIST OF TABLES . vii

LIST OF FIGURES viii

SUMMARY ix

CHAPTER I INTRODUCTION .

CHAPTER II MONOTONIC PROGRAMMING: STRUCTURE AND AL-

GORITHMS .

2.1 Introduction .

2.2 Characteristics of Monotonic Programs

2.3 Polyblock Algorithm

2.3.1 An illustrative example . 10

2.3.2 Enhancement 11

2.3.3 Convergence analysis 21

2.4 Branch-and-Bound Algorithm . 23

2.4.1 Selection and branching 23

2.4.2 Domain reduction 25

2.4.3 Bounding and optimality cuts . 28

2.4.4 Fathoming 30

2.4.5 Convergence analysis 30

2.5 Simplicial branching 33

CHAPTER III COMPUTATIONAL RESULTS FOR SEPARABLE POLY-

NOMIAL PROGRAMMING PROBLEMS . 36

3.1 Separable polynomial programming 36

3.1.1 Problem transformation 37

3.1.2 Convex relaxations . 38

3.2 Computational Experiments 42

3.2.1 Test problems 42

3.2.2 Bounding by variable fixing 45

3.2.3 Computational Results . 46

CHAPTER IV PROBABILISTICALLY CONSTRAINED LINEAR PRO-

GRAMS . 53

4.1 Introduction . 53

4.2 Problem reformulation and structural properties . 55

4.3 A Branch-Reduce-Cut algorithm 60

4.3.1 Selection and branching 63

4.3.2 Domain reduction 64

4.3.3 Feasibility and optimality cuts . 65

4.3.4 Upper bounding and searching for feasible solutions . 66

4.3.5 Fathoming 67

4.4 Convergence analysis 68

4.4.1 Discrete distribution 68

4.4.2 Continuous distribution 70

4.5 Computational results . 71

CHAPTER V CONCLUSION . 74

APPENDIX A — COMPUTATIONAL RESULTS . 77

REFERENCES . 92

VITA 95