What is the optimality argument in a simultaneous column and row generation procedure? By column and row generation procedure I mean a procedure in which every time a column in generated, several constraints need to be added to the master program.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Not sure where the rows play a role here (do you mean additional cutting planes?) but I'd say if no column can be found during the pricing step. Whether the solution is then optimal for the original problem will depend on the circumstances of your problem and model. $\endgroup$– JakobSAug 21, 2019 at 14:09
-
$\begingroup$ @JakobS by rows I mean actual constraints that define the original problem. So this could be seen as a DW decomposition in which the number of constraints depend on the columns you bring from the sub. In other words, I don't have the entire list of constraints in the master since I don't know the columns I want to use, but once I get a column I know exactly all the constraints I need. $\endgroup$– Daniel DuqueAug 21, 2019 at 14:18
-
$\begingroup$ @DanielDuque I am going to ask a random question. What are you doing when these new rows make the Master infeasible? In other word, the only column generated by the sub-problem is making the Master infeasible. $\endgroup$– MehdiAug 21, 2019 at 17:55
-
3$\begingroup$ Hello Daniel, you may find an answer to your question in the following article link.springer.com/article/10.1007/s10107-012-0561-8. In this article, the authors face exactly the problem you 're describing and propose a way to include the dual contribution of the missing rows in the CG process $\endgroup$– Claudio ContardoAug 21, 2019 at 20:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
As you are probably aware of, the standard optimality condition for column generation is not valid if not all constraints are included in the master problem, as the dual information of the missing constraints needs to be taken into account in the computation of the reduced costs. Muter et al. (2013) consider this issue and show that if the formulation satisfies certain assumptions, it is possible to anticipate the optimal dual variables of the missing dual variables, such that the reduced costs can be computed correctly.
There are successful applications of this approach, see e.g. this paper or this paper. However, whether this approach is computationally feasible fully depends on your model. In some cases, the pricing problem itself becomes an integer program with exponentially many variables, so then it might be worthwhile to try and come up with a different formulation without column-dependent rows.
answered Aug 22, 2019 at 15:17
-
1$\begingroup$ Avoiding column-dependent rows to not complicate the pricing problem was also suggested in answers to this question. $\endgroup$ Aug 22, 2019 at 16:05