3
$\begingroup$

I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution to initialize the CG-heuristic. Subsequently, in each of the CG-iterations,

  1. The restricted master problem (RMP) is solved for the LP-solution and the optimal dual vector.
  2. These dual variables along with information of existing flight-connections are used to construct partial pricing subproblems as the full-scale network is intractable. From this, I only generate the columns/variables with negative reduced cost.

My questions are related to Step 1. From the RMP, it is required to generate a:

  • primal-solution (optimal primal vector with continuous variables $\in [0,1]$ corresponding to each column/pairing in the input set), and
  • a dual-solution (optimal dual vector with non-negative dual variables corresponding to each input constraint/flight).

In every CG-iteration, the input to the RMP consists of ~0.5 million columns/pairings and ~4500 constraints/flights. To solve the RMP, first, I formulate the primal using the above-sized input, and solve it using the Simplex algorithm to get the primal-optimal solution (having ~50k non-zero variables). Using this primal-solution, i.e, only non-zero variables as the search space, I formulate the dual of the problem and solve it. Questions:

  1. To solve the primal, which simplex method is the best method for such problems (currently, I use Gurobi and in that, I have empirically found the barrier method to the most effective in comparison to the primal simplex & dual simplex)? Is there a scientific survey on how the simplex method evolved and what are the associated advantages/disadvantages of the evolved methods?
  2. Is it advisable to formulate dual in the above-mentioned way, i.e., only using the optimal columns/pairings from the primal (~50k), or shall it be formulated using the whole input set of columns (~0.5 million) (I did it to reduce the solutioning-time of the dual)? Is it correct to assume that the optimal dual-solution of the former version of the dual will be the same as that of the latter version?
  3. Is there scientific evidence suggesting that solving the dual in CG using the interior-point methods can lead to better convergence than the simplex methods?
  4. For stabilization of CG, how to decide among the different interior-point methods available? (I have empirically found that the SciPy's interior-point method leads to better convergence than the Gurobi's barrier method for this optimization problem)
  5. Is it possible to extract/derive the dual-solution from the primal-solution w/o solving the dual of the RMP or vice-versa, eliminating the need to solve both primal & dual in each CG-iteration?
Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ I cannot answer all of your questions but I know that, when you solve the primal LP, the dual solution (with 4500 dual variables for each primal constraint) is directly available. In C# library of Gurobi it is something like //LP_duals = model.Get(GRB.DoubleAttr.Pi, model.GetConstrs()); $\endgroup$
    – Evren Guney
    May 7, 2020 at 8:50
  • 1
    $\begingroup$ Thanks. I did not come across this earlier. I will explore it and see if this would help me in achieving better/faster convergence. $\endgroup$
    – Divyam Aggarwal
    May 7, 2020 at 9:55
  • 1
    $\begingroup$ When you compute the reduced costs based on the master dual solution, remember to account for the upper bounds on the master variables. The simplest approach is probably to omit the upper bounds, which will naturally be satisfied anyway. $\endgroup$
    – RobPratt
    May 7, 2020 at 13:08
  • $\begingroup$ Thanks, @RobPratt for the insights. $\endgroup$
    – Divyam Aggarwal
    May 8, 2020 at 13:21
  • 1
    $\begingroup$ @mehdi I further read about 'Pi' attribute and found that Gurobi provides dual optimal solution along with a primal-solve. I still haven't figured out the above problem. I think there is a mismatch between the dual-model I am formulating and the one Gurobi has given answer for. Let me ask about the correctness of dual of my problem formulation in a separate thread/question. $\endgroup$
    – Divyam Aggarwal
    May 11, 2020 at 13:58

0

Reset to default

Your Answer

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