Open Collections

Ordered optimal solutions and applications

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2009-03-17

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.

http://hdl.handle.net/2429/6161

Business Administration - Management Science

University of British Columbia

UBCV

DSpace