Computational, Combinatorial, and Geometric Aspects of Linear Optimization

点击翻译按钮获取中文摘要

Rational decision-making through quantitative modelling and analysis is the guiding principle behind operations research, a field with several far-reaching applications across engineering, sciences, and industry. Finding optimal allocations of resources, scheduling tasks, and designing prototypes are a few of the areas operations research is concerned with. These problems can often be formulated, or approximated, as linear optimization problems, which involve maximizing or minimizing a linear function over a domain defined by a set of linear inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. The algorithmic issues are related to the combinatorial and geometric structure of the feasible region. In the last few years, there has been substantial progress in both the geometric analysis of linear programming algorithms and novel models for integer programming. The research proposal aims at consolidating and preserving the momentum in several research areas related to the computational, combinatorial, and geometric aspects of linear optimization with a focus on the analysis of worst-case constructions leading to computationally highly challenging instances. Developing new models to handle application driven questions forms another key focus of this research proposal. The anticipated outcome and significance include fostering cutting edge research and triggering novel approaches. Tightening of the bounds, deeper understanding of the interactions between the algorithmic performance and the structural properties of the input have the potential to stimulate novel approaches for solving linear optimization problems. The proposed methodology is based on a combination of novel constructions and worst-case examples and a tighter analysis of the current bounds and results such as a strengthening of the upper bound for the diameter of polytopes, a counterexample to the Hirsch conjecture, an exponential counterexample to the continuous analogue of the polynomial Hirsch conjecture, and continuous generalizations of the Klee-Minty construction. Supervision and training of highly qualified personnel is an essential part of my research proposal. As the head of the Advanced Optimization Laboratory (AdvOL), I will continue to seek top graduate students and further strengthen the reputation of AdvOL as one of the leading optimization research groups in Canada. I will nurture multifaceted, multidisciplinary training that produces highly marketable, qualified personnel for both industrial and academic positions. This will develop optimization models, algorithms, software and produce Highly Qualified Personnel to assist Canadian enterprises in strategic sectors of the economy, such as information technology, design, manufacturing, and transportation.