zbMATH — the first resource for mathematics

Combining constraint programming and linear programming on an example of bus driver scheduling. (English) Zbl 1001.90029
Summary: 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.

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
PDF BibTeX Cite
Full Text: DOI