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,
- The restricted master problem (RMP) is solved for the LP-solution and the optimal dual vector.
- 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:
- 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?
- 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?
- 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?
- 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)
- 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?