Combining constraint programming and linear programming on an example of bus driver scheduling.

*(English)*Zbl 1001.90029Summary: This paper provides details of a successful application where the column generation algorithm was used to combine constraint programming and linear programming. In the past, constraint programming and linear programming were considered to be two competing technologies that solved similar types of problems. Both these technologies had their strengths and weaknesses. This paper shows that the two technologies can be combined together to extract the strengths of both these technologies. Details of a real-world application to optimize bus driver duties is given here. This system was developed by ILOG for a major software house in Japan using ILOG-Solver and ILOG-CPLEX, constraint programming and linear programming C/C++ libraries.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C08 | Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) |

90C90 | Applications of mathematical programming |

90C46 | Optimality conditions and duality in mathematical programming |