Back to search

University of British Columbia

Ordered optimal solutions and applications

Abstract

dc:description

The Monotone Response and Selection (MRS) Theorems in lattice programming provide a sufficient condition under which the optimal solutions of a parametric optimization problem are monotone in the parameter. The MRS Theorems have many applications. In particular, they explain the monotonicity of minimum cuts in parametric maximum flow problems in certain networks. However, in some parametric optimization problems, monotonicity does not hold. Rather, a totally ordered selection of optimal solutions exists. In Chapter 2, I present some conditions under which there exists a selection of optimal solutions that are totally ordered, but not necessarily monotone. Based on this result, I present necessary and sufficient conditions for some natural classes of parametric maximum flow problems to ensure the existence of a totally ordered selection of minimum cuts. In Chapter 3, I extend the original selection problem studied by Rhys (1970) and Balinski (1970). I introduce the notion of tasks and assume that, facilities are capable of performing multi-tasks. A job then, instead of requiring a fixed set of facilities, requires a set of tasks, which can be performed by different facilities. The objective is to maximize the net return. Although this extended model is NP-hard, by introducing some natural restrictions in the extended selection problem, I obtain two variants thereof, which can be solved as minimum cut problems. A forest-harvest and road-construction scheduling problem can be formulated as one of the two variants and solved as a minimum cut problem. Recently, new legislations have been introduced which require that a logging company cannot harvest a block of forest if an adjacent block has been harvested within the past 20 years. In order to harvest a block of forest, a road must be ready leading from a saw mill to the block. Roads must be constructed from a tree structured network of potential links. Due to the long planning horizon, forest-harvesting and road-construction must be scheduled together in order to maximize the present value of net income. In Chapter 4, I present a tabu search heuristic to generate schedules which compare favorably with previous studies.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Business Administration - Management Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1996

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Li

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/6161

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Liu, Li. Ordered optimal solutions and applications. doctoral thesis, University of British Columbia, 1996. http://hdl.handle.net/2429/6161