Search

The purpose of this paper is to take stock of what is known and to suggest some conceptual foundations for future progress in the areas of postoptimality analysis and parametric optimization techniques for integer programming. [ABSTRACT FROM AUTHOR]

The paper presents an analytical description of a state-dependent assignment policy, where different assignments of attributes to objects are employed under different states. Various considerations, other than optimizing an objective function, present themselves for such cases—for example, the existence of groups of assignees with certain levels of intragroup assignment uniformity, the stability of the policy over states, the presence of a revealed preference ordering of the assignments, and others. An approach towards a quantitative treatment of such features of a state-dependent assignment policy is discussed, and in particular a uniformity measure is defined and its properties are investigated. Potential uses of the model are suggested for urban emergency services, questionnaire analysis, task allocation, medical diagnosis, and dynamic computer program behavior. Three implementations for questionnaire analysis are reported. [ABSTRACT FROM AUTHOR]

A local search framework for the (undirected) Rural Postman Problem (RPP) is presented in this paper. The framework allows local search approaches that have been applied successfully to the well-known Travelling Salesman Problem also to be applied to the RPP. New heuristics for the RPP, based on this framework, are introduced and these are capable of solving significantly larger instances of the RPP than have been reported in the literature. Test results are presented for a number of benchmark RPP instances in a bid to compare efficiency and solution quality against known methods. [ABSTRACT FROM AUTHOR]

We study a discrete problem of scheduling activities of three types under the constraint that at most a single activity can be scheduled to any one period. Applications of such a model are the scheduling of maintenance service to machines and multi-item replenishment of stock. We assume that the cost associated with any given type of activity increases linearly with the number of periods since the last execution of this type. The problem is to specify at which periods to execute each of the activity types in order to minimize the long-run average cost per period. We analyze various forms of optimal solution which may occur, relating them to the combination of the three machine cost constants. Some cases remain unsolved by this method and for these we develop a heuristic whose worst case performance is no more than 3.33% from the optimal. [ABSTRACT FROM AUTHOR]

We consider constrained finite-time optimal control problems for discrete-time linear time-invariant systems with constraints on inputs and outputs based on linear and quadratic performance indices. The solution to such problems is a time-varying piecewise affine (PWA) statefeedback law and can be computed by means of multiparametric programming. By exploiting the properties of the value function and the piecewise affine optimal control law of the constrained finitetime optimal control (CFTOC), we propose two new algorithms that avoid storing the polyhedral regions. The new algorithms significantly reduce the on-line storage demands and computational complexity during evaluation of the PWA feedback control law resulting from the CFTOC. [ABSTRACT FROM AUTHOR]