A model for adaptive rescheduling of flights in emergencies (MARFE)
- Authors: Filar, Jerzy , Manyem, Prabhu , Panton, David , White, Kevin
- Date: 2007
- Type: Text , Journal article
- Relation: Journal of Industrial and Management Optimization Vol. 3, no. 2 (May 2007), p. 335-356
- Full Text:
- Reviewed:
- Description: Disruptions to commercial airline schedules are frequent and can inflict significant costs. In this paper we continue a line of research initiated by Vranas, Bertsimas and Odoni [15, 16], that aims to develop techniques facilitating rapid return to normal operations whenever disruptions occur. Ground Holding is a technique that has been successfully employed to combat disruptions at North American airports. However, this alone is insufficient to cope with the problem. We develop an adaptive optimization model that allows the implementation of other tactics, such as flight cancellations, airborne holding and diversions. While the approach is generic, our model incorporates features of Sydney airport in Australia, such as a night curfew from 11:00pm to 6:00am. For an actual day when there was a significant capacity drop, we demonstrate that our model clearly outperforms the actions that were initiated by the air traffic controllers at Sydney.
- Description: C1
- Description: 2003004883
Constrained spanning, Steiner trees and the triangle inequality
- Authors: Manyem, Prabhu
- Date: 2009
- Type: Text , Book chapter
- Relation: Optimization : Structure and applications Chapter 19 p. 355-367
- Full Text: false
- Description: 2003007888
Online LIB problems : Heuristics for bin covering and lower bounds for bin packing
- Authors: Finlay, L. , Manyem, Prabhu
- Date: 2005
- Type: Text , Journal article
- Relation: Rairo-Operations Research Vol. 39, no. 3 (Jul-Sep 2005), p. 163-183
- Full Text:
- Reviewed:
- Description: We consider the NP Hard problems of online Bin Covering and Packing while requiring that larger (or longer, in the one dimensional case) items be placed at the bottom of the bins, below smaller (or shorter) items - we call such a version, the LIB version of problems. Bin sizes can be uniform or variable. We look at computational studies for both the Best Fit and Harmonic Fit algorithms for uniform sized bin covering. The Best Fit heuristic for this version of the problem is introduced here. The approximation ratios obtained were well within the theoretical upper bounds. For variable sized bin covering, a more thorough analysis revealed definite trends in the maximum and average approximation ratios. Finally, we prove that for online LIB bin packing with uniform size bins, no heuristic can guarantee an approximation ratio better than 1.76 under the online model considered.
- Description: C1
- Description: 2003001388
Performance estimations of first fit algorithm for online bin packing with variable bin sizes and LIB constraints
- Authors: Manyem, Prabhu , Lin, J. Y. , Sheu, Ruey-Lin
- Date: 2005
- Type: Text , Conference paper
- Relation: Paper presented at the Sixteenth Australasian Workshop on Combinatorial Algorithms, Ballarat, Victoria : 18th - 21st September, 2005
- Full Text:
- Reviewed:
- Description: We consider the NP Hard problem of online Bin Packing while requiring that larger (or longer) items be placed below smaller (or shorter) items --- we call such a version the {LIB} version of problems. Bin sizes can be uniform or variable. We provide analytical upper bounds as well as experimental results on the asymptotic approximation ratio for the first fit algorithm.
- Description: 2003001387
Polynomial-time maximisation classes : Syntactic hierarchy
- Authors: Manyem, Prabhu
- Date: 2006
- Type: Text , Conference paper
- Relation: Paper presented at AWOCA 2006, 17th Australasian Workshop on Combinatorial Algorithms, Uluru, Australia : 13th July, 2006
- Full Text:
- Reviewed:
- Description: In Descriptive Complexity, there is a vast amount of literature on decision problems, and their classes such as textbf{P, NP, L and NL}. ~ However, research on the descriptive complexity of optimisation problems has been limited. In a previous paper [Man], we characterised the optimisation versions of textbf{P} via expressions in second order logic, using universal Horn formulae with successor relations. In this paper, we study the syntactic hierarchy within the class of polynomially bound maximisation problems. We extend the result in the previous paper by showing that the class of polynomially-bound bf{NP} (not just bf{P}) maximisation problems can be expressed in second-order logic using Horn formulae with successor relations. Finally, we provide an application --- we show that the Bin Packing problem with online LIB constraints can be approximated to within a $Theta(log n)$ bound, by providing a syntactic characterisation for this problem.
- Description: E1
- Description: 2003001917
Proceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)
- Authors: Ryan, Joe , Manyem, Prabhu , Sugeng, Kiki Ariyanti , Miller, Mirka
- Date: 2005
- Type: Text , Conference proceedings
- Full Text: false
Syntactic characterizations of polynomial time optimization classes
- Authors: Manyem, Prabhu
- Date: 2008
- Type: Journal article
- Relation: Chicago Journal of Theoretical Computer Science Vol. 2008, no. (2008), p.
- Full Text:
- Reviewed:
- Description: The characterization of important complexity classes by logical descriptions has been an important and prolific area of Descriptive complexity. However, the central focus of the research has been the study of classes like P, NP, L and NL, corresponding to decision problems (e.g. the characterization of NP by Fagin [Fag74] and of P by Gradel [E. 91]). In contrast, optimization problems have received much less attention. Optimization problems corresponding to the NP class have been characterized in terms of logic expressions by Papadimitriou and Yannakakis, Panconesi and Ranjan, Kolaitis and Thakur, Khanna et al, and by Zimand. In this paper, we attempt to characterize the optimization versions of P via expressions in second order logic, many of them using universal Horn formulae with successor relations. These results nicely complement those of Kolaitis and Thakur [KT94] for polynomially bounded NP-optimization problems. The polynomially bounded versions of maximization and minimization problems are treated first, and then the maximization problems in the not necessarily polynomially bounded class.
- Description: 2003006662