Interior Point Methods. Applications to Structured Problems

Jordi Castro

Humanitarian Supply Chain Analytics

Marie-Eve Rancourt

The first lectures will introduce the basics of the primal-dual path-following interior point algorithm, which is the one implemented in state-of-the-art optimization solvers (usually under the name "barrier algorithm"). We will see both the theory (i.e., the polynomial time complexity of these algorithms for linear optimization) and the implementation details. In the last lectures we will see how this algorithm can be further specialized for the solution of large (even huge) structured optimization problems, focusing on some particular applications: support vector machines (a classification technique from the data science/machine learning field); network optimization in bipartite graphs; multistage stochastic optimization; facility location (a mixed integer problem).

This course seeks to model and solve complex decision-making problems in humanitarian supply chains (HSCs), emphasizing their unique characteristics and identifying related problem classes. We will delve deeply into humanitarian-specific network analysis and design problems, such as relief item prepositioning, food aid, shelter, and community-based water and healthcare services. Recognizing that each problem demands an ad hoc solution approach, we will cover the basics of OR-based methodologies such as stochastic programming, bilevel optimization, heuristics development and statistical modeling, and show how they can be tailored. Applied quantitative research hinges heavily on data collection and processing to delineate problems and parametrize mathematical formulations. We will illustrate the use of both unstructured information and data extracted from formal tools, such as geographic information systems, to devise well-defined problems. Real-life examples and solution validation techniques will be also discussed. The course will follow the principles of a bottom-up research design, from challenges encountered by humanitarian organizations on the field to solution propositions. Throughout, students will experience the complexities of conducting analytical research in the humanitarian field. The overarching objective will be to demonstrate how quantitative analysis can foster critical thinking and enhance supply chain optimization in a sector where stakeholders have various, and sometimes competing, objectives and unique constraints.