1
$\begingroup$

I was wondering what the typical approaches are for generating an initial solution for the first column in a COlumn Generation approach and which usually work best and are easiest to implement (Gurobi). So far, I have either fixed the initial columns to values that generate the worst possible objective function value (in my case this would be $motivation_{its}=0~\forall i,t,s$ in my example) or I have solved the compact model for e.g. 20 seconds and then taken the optimal values up to this point in time from the starting point.

$\endgroup$

2 Answers 2

1
$\begingroup$

Another idea when you have multiple subproblems is to solve each one (perhaps with a time limit) using the part of the original objective that corresponds to the variables in each subproblem, rather than minimizing the reduced cost. For your example, that would just be a constant zero objective, so the resulting columns would be arbitrary.

$\endgroup$
0
$\begingroup$

Other approaches might be more efficient for specific problems, but for a good method that's easy to implement consider Farkas' Pricing (see Lubbecke's Column generation section 2.1.1. for a light overview of the method). It's quite simple to implement, you just need to solve a slightly different pricing problem. The objective cost is 0, and you use Farkas' Duals (supported by Gurobi here) instead of the normal ones. It has the added benefit of being able to fix local infeasibilities introduced by branching decisions.

It's the method I've been using in my work and I've been happy with it.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. Any idea on how to incorporate it in my case (or.stackexchange.com/questions/11581/…), since i already use the cost coefficient of 0? $\endgroup$ Commented yesterday
  • $\begingroup$ @nflgreaternba I'm fairly certain it wouldn't alter anything, but you can look into the literature for details. $\endgroup$ Commented yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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