• Home
• About
• People
• News
• Events
• Research
• Areas
• Publications
• Themes
• Topics and Projects
• Courses
• Graduate Study
• Undergraduate Study
• Places
• Computing Systems
• Industrial Relations
• Alumni
• Contacts

Optimization - Hybrid Methods

Combinatorial optimization is the core task of algorithmic computer science. In theoretical computer science, the task of finding the element where a function takes it's maximum over a finite yet vast set of potential solutions has lead to fundamental complexity notions like NP-hardness and to the idea of approximation algorithms. On the other hand, research dealing with practical optimization problems has lead to paradigms like linear programming in operations research and constraint programming in the artificial intelligence community.

Today we realize that theory, artificial intelligence, and operations research are largely dealing with the same problems. While some methods have been developed in all communities in parallel, often they can actually complement each other as they exhibit different strengths and weaknesses. This project tries to channel understanding and knowledge between the different research areas, with the ultimate aim to produce theoretically and practically superior optimization algorithms and systems.

Project status: Active

Publications

Aron, I., Leventhal, D., and Sellmann, M. A Totally Unimodular Description of the Consistent Value Polytope for Binary CSPs. In Proceedings of the Third International Conference on Integration of AI and OR Techniques (CP-AI-OR) (2006), Springer Verlag, pp. 16-28. [ pdf ]

Kenyon, C., and Sellmann, M. Uncertainty/Time Trade-Offs for Linear and Integer Programming. In Proceedings of the Third International Conference on Integration of AI and OR Techniques (CP-AI-OR) (2006), Springer Verlag, pp. 126-138.

Sellmann, M. The Theory of Grammar Constraints. In Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP) (2006), Springer, pp. 530-544. [ pdf ]

Gellermann, T., Sellmann, M., and Wright, R. Shorter Path Constraints for the Resource Constrained Shortest Path Problem. In Proceedings of the Second International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization (CPAIOR) (2005), Springer, pp. 201-216. [ postscript | pdf ]

Sellmann, M. Approximated Consistency for the Automatic Recording Constraint. In Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP) (2005), Springer, pp. 822-826. [ postscript | pdf ]

Gomes, C., Sellmann, M., van Es, C., and van Es, H. The Challenge of Generating Spatially Balanced Scientific Experiment Designs. In Proceedings of the First International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR) (2004), Springer, pp. 387-394. [ postscript | pdf ]

Sellmann, M. The Practice of Approximated Consistency for Knapsack Constraints. In Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI) (2004), AAAI Press, pp. 179-184. [ postscript | pdf ]

Sellmann, M. Theoretical Foundations of CP-based Largrangian Relaxation. In Proceedings of the Tenth International Conference on the Principles and Practice of Constraint Programming (CP) (2004), Springer, pp. 634-647. [ postscript | pdf ]

Sellmann, M. Approximated Consistency for Knapsack Constraints. In Proceedings of the Ninth International Conference on the Principles and Practices of Contraint Programming (CP) (2003), Springer, pp. 679-693. [ postscript | pdf ]

Sellmann, M. Cost-Based Filtering for Shorter Path Constraints. In Proceedings of the Ninth International Conference on the Principles and Practices of Contraint Programming (CP) (2003), Springer, pp. 694-708. [ postscript | pdf ]

Sellmann, M., and Fahle, T. Constraint Programming Based Lagrangian Relaxation for the Automatic Recording Problem. Annals of Operations Research (AOR) 118 (2003), 17-33. [ postscript | pdf ]

Sellmann, M., Sensen, N., and Timajev, L. Multicommodity Flow Approximation Used for Exact Graph Partitioning. In Proceedings of the Eleventh Annual European Symposium on Algorithms (ESA) (2003), Springer, pp. 752-764. [ postscript | pdf ]

Fahle, T., and Sellmann, M. Cost-Based Filtering for the Constrained Knapsack Problem. Annals of Operations Research (AOR) 115 (2002), 73-93. [ postscript | pdf ]

Fahle, T., Junker, U., Karisch, S. E., Kohl, N., Sellmann, M., and Vaaben, B. Constraint Programming Based Column Generation for Crew Assignment. Journal of Heuristics (JOH), Kluwer Academic Publishers 8, 1 (2002), 59-81. [ postscript | pdf ]

Sellmann, M. An Arc-Consistency Algorithm for the Minimum Weight All Different Constraint. In Proceedings of the Eighth International Conference on the Principles and Practice of Constraint Programming (CP) (2002), Springer. [ postscript | pdf ]

Sellmann, M., Zervoudakis, K., Stamatopoulos, P., and Fahle, T. Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search. Annals of Operations Research (AOR) 115 (2002), 207-225. [ postscript | pdf ]

Sellmann, M., and Harvey, W. Heuristic Constraint Propagation. In Proceedings of the Eighth International Conference on the Principles and Practice of Constraint Programming (CP) (2002), Springer, pp. 738-743. [ postscript | pdf ]

Sellmann, M., Kliewer, G., and Koberstein, A. Lagrangian Cardinality Cuts and Variable Fixing for Capacitated Network Design. In Proceedings of the Tenth Annual European Symposium on Algorithms (ESA) (2002), Springer, pp. 845-858. [ postscript | pdf ]

Sellmann, M. Reduction Techniques in Constraint Programming and Combinatorial Optimization. PhD thesis, University of Paderborn, 2002.

Sellmann, M., and Fahle, T. Coupling Variable Fixing Algorithms for the Automatic Recording Problem. In Proceedings of the Ninth Annual European Symposium on Algorithms (ESA) (2001), Springer, pp. 134-145. [ postscript ]

Junker, U., Karisch, S. E., Kohl, N., Vaaben, B., Fahle, T., and Sellmann, M. A Framework for Constraint Programming Based Column Generation. In Proceedings of the Fifth International Conference on the Principles and Practice of Constraint Programming (CP) (1999), Springer, pp. 261-274. [ pdf ]