Boolean Methods in Operations Research and Related Areas

ISBN-13: 9783642858253 / Angielski / Miękka / 2014 / 331 str.

P. L. Hammer; S. Rudeanu; R. Bellmann

Opis

In classical analysis, there is a vast difference between the class of problems that may be handled by means of the methods of calculus and the class of problems requiring combinatorial techniques. With the advent of the digital computer, the distinction begins to blur, and with the increasing emphasis on problems involving optimization over structures, tIlE' distinction vanishes. What is necessary for the analytic and computational treatment of significant questions arising in modern control theory, mathematical economics, scheduling theory, operations research, bioengineering, and so forth is a new and more flexible mathematical theory which subsumes both the cla8sical continuous and discrete t 19orithms. The work by HAMMER (IVANESCU) and RUDEANU on Boolean methods represents an important step in this dnectlOn, and it is thus a great pleasure to welcome it into print. It will certainly stimulate a great deal of additional research in both theory and application. RICHARD BELLMAN University of Southern California FOf(, WOl

Spis treści

I.- I. Boolean Algebra.- § 1. The Two-Element Boolean Algebra.- § 2. Boolean Functions.- § 3. Boolean Matrices and Determinants.- § 4. The General Concept of Boolean Algebra.- § 5. Boolean Algebras and Boolean Rings.- § 6. Pseudo-Boolean Functions.- II. Boolean Equations.- A. Equations in an Arbitrary Boolean Algebra.- § 1. The Single-Equation Form of a System of Boolean Equations and/or Inequalities.- § 2. The Boolean Equation m one Unknown (Consistency and Solutions).- § 3. Boolean Equations m n Unknowns: The Method of Successive Eliminations (Consistency and Solutions).- § 4. The Lowenheim Form of the General Solution.- B. Equations in the Two-Element Boolean Algeha.- § 5. The Method of Bifurcations.- § 6. Families of Solutions.- C. Addendum.- § 7. Other Researches Concerning Boolean Equations and their Generalizations.- III. Linear Pseudo-Boolean Equations and Inequalities.- § 1. Linear Pseudo-Boolean Equations.- § 2. Linear Pseudo-Boolean Inequalities.- § 3. Systems of Pseudo-Boolean Equations and/or Inequalities.- § 4. The Methods of R. Fortet and P. Camion.- IV. Nonlinear Pseudo-Boolean Equations and Inequalities.- § 1. The Characteristic Function m the Linear Case.- § 2. The Characteristic Function of a Nonlinear Equation or Inequality.- § 3. The Characteristic Function for Systems.- § 4. The Characteristic Function of Logical Conditions.- § 5. Irredundant Solutions of the Characteristic Equation.- § 6. The Pseudo-Boolean Form of the Characteristic Equation.- § 7. The Methods of R. Fortet and P. Camion.- V. Minimization of Linear Pseudo-Boolean Functions.- § 1. Using Partially Minimizing Points.- § 2. Accelerated Linear Pseudo-Boolean Programming.- § 3. The Method of P. Camion.- VI. Minimization of Nonlinear Pseudo-Boolean Functions.- A. Minima without Constraints.- § 1. The Basic Algorithm.- B. Minima with Constraints.- § 2. Lagrangean Multipliers.- § 3. Minimization Using Families of Solutions.- § 4. Minimization Using Parametric Forms of the Solutions.- § 5. Extension of the Basic Algorithm.- VII. Extensions of Pseudo-Boolean Programming.- § 1. Local Minima of Pseudo-Boolean Functions.- § 2. Applications to the Theory of Graphs.- § 3. Near-Minima of Pseudo-Boolean Functions.- § 4. Minimax Problems m Pseudo-Boolean Programming.- § 5. Fractional Pseudo-Boolean Programming.- II.- VIII. Integer Mathematical Programming.- § 1. All-Integer Mathematical Programming.- § 2. Mixed Integer-Continuous Mathematical Programming.- § 3. Linear and Quadratic Continuous Programming.- § 4. Discrete-Variable Problems.- IX. Connectedness and Path Problems in Graphs.- § 1. Basic Concepts m Graph Theory: Paths, Circuits, Connectedness.- § 2 Unitary Incidence-Matrices.- § 3. Incidence Matrices.- § 4. The Algebraic Closure of Graphs.- § 5. Decompositions of Graphs.- § 6. Latin Multiplication.- § 7. Hamiltoman Paths and Circuits.- § 8. Using Free Boolean Algebras.- § 9. Boolean Proofs of Graph-Theoretical Properties.- X. Stable Sets, Kernels, and Chromatic Decompositions of Graphs.- § 1. Definitions and Interpretations.- §2 Internally Stable Sets.- § 3. Externally Stable Sets.- § 4. Kernels of Graphs.- § 5. Chromatic Decompositions.- § 6. The Four Colouring Problem.- XI. Matchings of Bipartite Graphs.- § 1. Bipartite Graphs.- § 2. Assignment and Transportation Problems.- § 3. Systems of Representatives.- XII. Flows in Networks and Chains in Partially Ordered Sets.- § 1. Flows m Networks.- § 2. Minimal Decompositions of Partially Ordered Sets into Chains.- XIII. Various Applications.- § 1. A Sequencing Problem.- § 2. Time-Table Scheduling (by Ivo Rosenberg).- § 3. Applications to Coding Theory.- § 4. Miscellanies.- § 5. Plant Location.- § 6. Other Types of Applications.- XIV. Minimization Problems in Automata Theory.- § 1. Minimization of Normal Forms of Boolean Functions; Generalizations.- § 2. Minimization of the Number of States m Input-Restricted Machines (by Ivo Rosenberg).- § 3. The State Assignment of Sequential Circuits with High Reliability.- § 4. Program Segmentation.- Appendix: Generalized Pseudo-Boolean Programming, by Ivo Rosenberg.- Conclusions.- Supplementary Bibliographies.- A. Boolean Equations and Generalizations.- B. Books on Boolean Algebra and Switching Theory.- Author Index.