Contributed Session Mon.1.H 2013

Monday, 10:30 - 12:00 h, Room: H 2013

Cluster 11: Integer & mixed-integer programming [...]

Column generation and decomposition


Chair: Richard Lusby



Monday, 10:30 - 10:55 h, Room: H 2013, Talk 1

Ozgur Ozpeynirci
Allocation of proposals to reviewers to facilitate effective ranking: A branch and price approach


One of the key problems for the funding agencies is to determine the proposals that are worth funding. A recent evaluation approach uses the ordinal ranking of the proposals. The approach allocates the proposals to the reviewers and each reviewer provides pairwise comparison of the assigned proposals. The approach uses a set covering IP model to assign the proposals so as to receive the maximum pairwise comparison information considering the capabilities and the preferences of the reviewers. In this study, we develop two new mathematical models for this approach. The size of the first model is polynomial in the number of the proposals. We propose a branch and price algorithm in the second model. We conduct a computational experiment to compare the performances of three models on a set of randomly generated instances.



Monday, 11:00 - 11:25 h, Room: H 2013, Talk 2

Richard Lusby
A column generation approach for solving the patient admission scheduling problem

Coauthors: Jesper Larsen, Troels Martin Range


The Patient Admission Scheduling Problem (PASP) is the problem of assigning patients to hospital rooms in such a way that the preferences of the patients as well as the effectiveness of the medical treatment are maximized. We present a Dantzig-Wolfe decomposition of PASP into a set partitioning master problem and a set of room scheduling problems for the pricing problems; here each column of the master corresponds to a feasible room schedule over the planning horizon. We describe an implementation of the dynamic constraint aggregation methodology proposed by Elhallaoui et al. (2005) to overcome the degeneracy of the master problem and show how this improves the performance of the column generation significantly. The method is tested on benchmark instances described by Demeester et al. (2008) where we derive tighter lower bounds than those previously reported for several of the instances. The computation time for identifying these lower bounds is, in most cases, significantly less than those presented by Ceshia and Schaerf (2011). A discussion on several branching strategies to integerize the lower bound solution is also provided.


  USA Payday Loans Online. Since its introduction in the market buying Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.