New answers tagged column-generation
3
votes
Accepted
Termination criterion for the Phase 1 algorithm in column generation
The termination criterion is the same because the primal objective value is $0$ if and only if the dual objective value is $0$.
Your dual formulation is almost correct, but you are missing $a$ and $b$ ...
1
vote
Accepted
Partially modify LHS of a constraint set?
The most computationally expensive aspect of this algorithm is the reconstruction of the master problem when a column is added (or sometimes removed)
By "reconstruction", do you mean that ...
0
votes
Is there existing code for the set partitioning formulation of routing problems?
There is a Python interface for the VRPSolver that can be installed using the following code:
python -m pip install VRPSolverEasy
All the information is given in ...
1
vote
Is there existing code for the set partitioning formulation of routing problems?
Python is not an efficient language, and solving the resource constrained shortest path is the bottleneck of the branch-and-cut-and-price algorithms for routing problems. Therefore, you won't find a ...
Top 50 recent answers are included
Related Tags
column-generation × 67mixed-integer-programming × 17
linear-programming × 12
branch-and-price × 11
vehicle-routing × 10
dantzig-wolfe-decomposition × 9
combinatorial-optimization × 8
optimization × 7
duality × 7
python × 6
heuristics × 5
set-covering × 5
reduced-costs × 5
cplex × 4
reference-request × 4
simplex × 4
integer-programming × 3
algorithms × 3
branch-and-bound × 3
pyomo × 2
graphs × 2
traveling-salesman × 2
metaheuristics × 2
docplex × 2
c++ × 2