Hello,
I am developing a column generation algorithm for a bus scheduling problem. In this problem I have a fixed set of buses that need to operate, and a fixed number of clients that the buses must serve. In my algorithm I generate a colum for the routing and scheduling of a single bus, that serves a subset of the clients. In the master problem I make sure all buses are operating and all clients are served.
The algorithm seems to find the optimal solution, which corresponds with my solution in my original MIP, but oddly enough it doesn't converge. The reduced cost reaches a maximum when the optimal solution is found but never reaches 0 or becomes positive. Hence I have to stop the algorithm manually.
Does anybody have any suggestions or have an idea what might cause this ?
Thanks in Advance.
Could it just be a matter of numerical precision? E.g. the routine for the pricing subproblem might think that a column has reduced cost -0.0001, when actually it is zero.
Adam N. Letchford thank you for your answer but I doubt this is a precision error, the redcuced cost stays at around -211 when it finds the optimal solution. I also confirmed I am including all the duals in the reduced cost calculation.
It sounds like you might be stopping the column generation process early. Normally, you would expect the optimal solution to the master LP to be fractional, and the corresponding lower bound to be slightly smaller than the cost of the integer optimum. In other words, you often need to embed the column generation process within a branch-and-price algorithm.
Adam N. Letchford the relaxed Master Problem actually returns an integer solution, which corresponds with the optimal solution. This, while the reduced cost is still negative. While I would expect the column generation process to return a postitve cost and terminate, but it keeps going suggesting more columns that don't even improve the realxed master problem. I just don't understand why the reduce cost is still negative eventho it found the optimal integer solution.
The optimal integer solution is not the same, in general, as the optimal solution to the LP relaxation. So, if you wish to *prove* that your optimal solution is indeed optimal, you will have to use a full branch-and-price algorithm. In particular, you will need to keep adding columns of negative reduced cost, and re-optimising the LP, until the algorithm converges. The cost of the resulting (probably fractional) LP solution will be a valid lower bound on the cost of the integer optimum.
Hi Adam (Letchford),
appreciating your help, here I am again. As you probably meanwhile assume, I am rewriting my latest paper falsely focused on the Asymmetric Traveling Salesman Path Problem ATSPP but (thanks your advice) now focused on the ASTSPP:
“Open and Closed Tours’ Efficient Determination in General Directed Graphs - Asymmetric Steiner Traveling Salesman Path Problem ASTSPP”
I’m sure that I should carefully study your papers
- The steiner travelling salesman problem with correlated costs.
- Compact formulations of the steiner traveling salesman problem and related problems.
May I ask you to send me a copy for consideration in my paper?
I thank you very much!
Peter (Richter) [email protected]
- Badges
- Science topic