Return to search
## The P-norm surrogate-constraint algorithm for polynomial zero-one programming.

by Wang Jun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 82-86). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.2 --- The polynomial zero-one programming problem --- p.2 / Chapter 1.3 --- Motivation --- p.3 / Chapter 1.4 --- Thesis outline --- p.4 / Chapter 2 --- Literature Survey --- p.6 / Chapter 2.1 --- Lawler and Bell's method --- p.7 / Chapter 2.2 --- The covering relaxation algorithm for polynomial zero-one pro- gramming --- p.8 / Chapter 2.3 --- The method of reducing polynomial integer problems to linear zero- one problems --- p.9 / Chapter 2.4 --- Pseudo-boolean programming --- p.11 / Chapter 2.5 --- The Balasian-based algorithm for polynomial zero-one programming --- p.12 / Chapter 2.6 --- The hybrid algorithm for polynomial zero-one programming --- p.12 / Chapter 3 --- The Balasian-based Algorithm --- p.14 / Chapter 3.1 --- The additive algorithm for linear zero-one programming --- p.15 / Chapter 3.2 --- Some notations and definitions referred to the Balasian-based al- gorithm --- p.17 / Chapter 3.3 --- Identification of all the feasible solutions to the master problem --- p.18 / Chapter 3.4 --- Consistency check of the feasible partial solutions --- p.19 / Chapter 4 --- The p-norm Surrogate Constraint Method --- p.21 / Chapter 4.1 --- Introduction --- p.21 / Chapter 4.2 --- Numerical example --- p.23 / Chapter 5 --- The P-norm Surrogate-constraint Algorithm --- p.26 / Chapter 5.1 --- Main ideas --- p.26 / Chapter 5.2 --- The standard form of the polynomial zero-one programming problem --- p.27 / Chapter 5.3 --- Definitions and notations --- p.29 / Chapter 5.3.1 --- Partial solution in x --- p.29 / Chapter 5.3.2 --- Free term --- p.29 / Chapter 5.3.3 --- Completion --- p.29 / Chapter 5.3.4 --- Feasible partial solution --- p.30 / Chapter 5.3.5 --- Consistent partial solution --- p.30 / Chapter 5.3.6 --- Partial solution in y --- p.30 / Chapter 5.3.7 --- Free variable --- p.31 / Chapter 5.3.8 --- Augmented solution in x --- p.31 / Chapter 5.4 --- Solution concepts --- p.33 / Chapter 5.4.1 --- Fathoming --- p.33 / Chapter 5.4.2 --- Backtracks --- p.41 / Chapter 5.4.3 --- Determination of the optimal solution in y --- p.42 / Chapter 5.5 --- Solution algorithm --- p.42 / Chapter 6 --- Numerical Examples --- p.46 / Chapter 6.1 --- Solution process by the new algorithm --- p.46 / Chapter 6.1.1 --- Example 5 --- p.46 / Chapter 6.1.2 --- Example 6 --- p.57 / Chapter 6.2 --- Solution process by the Balasian-based algorithm --- p.61 / Chapter 6.3 --- Comparison between the p-norm surrogate constraint algorithm and the Balasian-based algorithm --- p.71 / Chapter 7 --- Application to the Set Covering Problem --- p.74 / Chapter 7.1 --- The set covering problem --- p.74 / Chapter 7.2 --- Solving the set covering problem by using the new algorithm . .。 --- p.75 / Chapter 8 --- Conclusions and Future Work --- p.80 / Bibliography --- p.82

Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_322614 |

Date | January 1999 |

Contributors | Wang, Jun., Chinese University of Hong Kong Graduate School. Division of Systems Engineering and Engineering Management. |

Source Sets | The Chinese University of Hong Kong |

Language | English, Chinese |

Detected Language | English |

Type | Text, bibliography |

Format | print, ix, 86 leaves ; 30 cm. |

Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |

Page generated in 0.0013 seconds