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.


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.