Simultaneous Row and Column Generation

Column generation is a well-known technique for solving linear programs that involve a huge number of variables. More specifically, it is an iterative process in which a master problem and a pricing problem are solved in each step. The master problem is the original linear program with a reduced set of columns. In the pricing problem, one tries to identify profitable columns that are not yet present and add these to the master problem. If it turns out that all variables have positive (in case of a minimization problem) reduced costs, the linear program is solved to optimality and the iterative process can be stopped.

In practical problems, it frequently occurs that not only the set of variables is huge, but also the set of constraints. In such cases, it is commonly observed that the variables appear in groups and that a set of constraints is present for every such group. The columns and rows associated to these groups can then be generated simultaneously. When determining whether a group of variables is profitable, the dual multipliers corresponding to the omitted constraints should be anticipated. The traditional reduced cost criterion of column generation does not take this into account.

In this technical talk, we demonstrate a technique that simultanesouly generates groups of columns and their corresponding rows. We derive an optimality criterion for the master problem that is similar to the reduced cost criterion in column generation. We illustrate this approach by an example from literature [1, 2]. We describe the corresponding pricing problem and derive the optimality criterion for this problem both intuitively and formally. Then, we apply this technique to an application in health care that we are currently working on [3].

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.

References

1. Avella, D'Auria, and Salerno, "A LP-based heuristic for a time-constrained routing problem," (2006) EJOR 173:120-124
2. Muter, Birbil, Bülbül, and Sahin, "A note on 'A LP-based heuristic for a time-constrained routing problem,'" (2012) EJOR 221:306-307
3. Glorie, Dollevoet, van Oostrum, and Wagelmans, "Sterile Net Optimization," (2013) Working paper

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars