18
$\begingroup$

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.

$\endgroup$
  • $\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$ – JakobS Aug 21 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 Duque Aug 21 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$ – Mehdi Aug 21 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 Contardo Aug 21 at 20:24
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Avoiding column-dependent rows to not complicate the pricing problem was also suggested in answers to this question. $\endgroup$ – Kevin Dalmeijer Aug 22 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.