News & Events
The journal Interfaces
recently published the 8th Rothkopf rankings of University Contributions to the academic literature in applied operations research. Colorado School of Mines is first out of 45 U.S. universities in one measure of contributions (yield) and second in the other measure (visibility).
FALL 2011
SEMINAR SERIES
DIVISION OF ECONOMICS & BUSINESS
Date: Tuesday, October 11
Time: 4:00 - 5:15 pm
Place: EH 211 Classroom
Speaker: Josef Kallrath, Professor, University of Florida
Title: Modeling and Solving Real World Optimization Problems
Speaker: Josef Kallrath obtained his PhD in astrophysics from Bonn University (Germany) in 1989, after which he joined BASF's group Scientific Computing in Ludwigshafen, Germany. He is a professor at the University of Florida and solves real-world problems in industry using a broad spectrum of methods in scientific computing, from modeling physical systems to supporting decisions processes by mathematical optimization. He has written review articles on the subject, about 70 research papers in astronomy and applied mathematics, and several books on mixed integer optimization, as well as one on eclipsing binary stars.
Abstract:
This Lecture will transmit a sense of the requirements to solve real world decision or optimization problems using mathematical optimization methods. Among them are advanced modeling skills, familiarity with algebraic modeling languages and the ability to develop tailor-made methods. Many industrial or societal problems are so complicated that they need tailor-made methods. Therefore, we will put a focus on the important of modeling and the development of methods. I will explain and explore polylithic modeling and solution approaches in which mixed integer or non-convex nonlinear optimization problems are solved. Difficult problems need time to be analyzed and solved properly. Thus, modeling and solving real world optimization problems is not only an art regarding the mathematical techniques but also a very challenging mission in the triangle conflict of nowadays educational, scientific and industrial constraints and interests.
Place: EH 211 Classroom
Speaker: Josef Kallrath, Professor, University of Florida
Title: Modeling and Solving Real World Optimization Problems
Speaker: Josef Kallrath obtained his PhD in astrophysics from Bonn University (Germany) in 1989, after which he joined BASF's group Scientific Computing in Ludwigshafen, Germany. He is a professor at the University of Florida and solves real-world problems in industry using a broad spectrum of methods in scientific computing, from modeling physical systems to supporting decisions processes by mathematical optimization. He has written review articles on the subject, about 70 research papers in astronomy and applied mathematics, and several books on mixed integer optimization, as well as one on eclipsing binary stars.
Abstract:
This Lecture will transmit a sense of the requirements to solve real world decision or optimization problems using mathematical optimization methods. Among them are advanced modeling skills, familiarity with algebraic modeling languages and the ability to develop tailor-made methods. Many industrial or societal problems are so complicated that they need tailor-made methods. Therefore, we will put a focus on the important of modeling and the development of methods. I will explain and explore polylithic modeling and solution approaches in which mixed integer or non-convex nonlinear optimization problems are solved. Difficult problems need time to be analyzed and solved properly. Thus, modeling and solving real world optimization problems is not only an art regarding the mathematical techniques but also a very challenging mission in the triangle conflict of nowadays educational, scientific and industrial constraints and interests.
Sandwiches and drinks provided.
Date: Oct 28, 2011-
Time: 1:00 - 2:15 p.m
Place: EH 211
Speaker: Jens Schulz is a PhD student in Mathematics at the Technical University in Berlin, Germany
Topic: Conflict Analysis in Cumulative Scheduling
Abstract: A line of research to tackle scheduling problems as they arise in industry (Resource-Constrained Project Scheduling, open-pit mining,etc.) are decomposition approaches. Such approaches use a branch-and-bound scheme and a lot of constraint programming, integer programming and SAT techniques. The decomposed parts capture the logical structure independent of each other, such as precedence and resource constraints. During B&B search a lot of nodes can be pruned because infeasibilities are detected by propagation algorithms or because the dual bound (e.g. from the LP relaxation) is worse than the best known solution. Such situations can be analyzed (called conflict analysis) and no-goods can be learned. We provide experimental evidence that conflict analysis is one of the key ingredients to solve scheduling problems efficiently. This will be demonstrated on standard benchmark instances from PSPLib and RCPSP with discounted cash flows.The computational complexity of explanation algorithms that explain infeasibilities or bound changes of the resource constraints plays an important role. We present complexity results for computing minimum-size explanations for the propagation algorithms time-tabling, edge-finding, and energetic reasoning. We show that it is possible to compute in polynomial time minimum-size explanations for bound changes which result from energetic reasoning and edge-finding. In case of time-tabling, we prove that an important special case is already strongly NP-hard. We evaluate different heuristic approaches and exact approaches to explain bound changes derived by these algorithms.
Abstract: A line of research to tackle scheduling problems as they arise in industry (Resource-Constrained Project Scheduling, open-pit mining,etc.) are decomposition approaches. Such approaches use a branch-and-bound scheme and a lot of constraint programming, integer programming and SAT techniques. The decomposed parts capture the logical structure independent of each other, such as precedence and resource constraints. During B&B search a lot of nodes can be pruned because infeasibilities are detected by propagation algorithms or because the dual bound (e.g. from the LP relaxation) is worse than the best known solution. Such situations can be analyzed (called conflict analysis) and no-goods can be learned. We provide experimental evidence that conflict analysis is one of the key ingredients to solve scheduling problems efficiently. This will be demonstrated on standard benchmark instances from PSPLib and RCPSP with discounted cash flows.The computational complexity of explanation algorithms that explain infeasibilities or bound changes of the resource constraints plays an important role. We present complexity results for computing minimum-size explanations for the propagation algorithms time-tabling, edge-finding, and energetic reasoning. We show that it is possible to compute in polynomial time minimum-size explanations for bound changes which result from energetic reasoning and edge-finding. In case of time-tabling, we prove that an important special case is already strongly NP-hard. We evaluate different heuristic approaches and exact approaches to explain bound changes derived by these algorithms.