Research

Dr. Richard ’s research focuses on the design and application of methods for the global solution of mixed-integer linear and nonlinear optimization problems (often abbreviated as MILP and MINLP, respectively). MILP and MINLP are branches of optimization that consider problems in which some of the variables are required to be integer-valued. In MILP, objective and constraints are linear. In MINLP, objective and constraints are allowed to be nonlinear functions, often nonconvex ones. These problems are typically very hard to solve to provable optimality. However, because they can be used to model various systems with the view of making them more efficient, they are omni-present in Engineering and Management. In particular, they have found successful applications in field as diverse as forestry, mining and finance. From a practical point of view, theoretical advances in this field are significant as they help increase the range of problems that can be readily solved. In turn such advances may help O.R. practitioners, across all fields, to solve, in a reasonable amount of time, practical problems that are currently intractable. As a result, they can lead to improvements in the efficiency of many systems. Dr. Richard is interested in both the theoretical and practical sides of MINLP.

• Methods for MINLPs:

MINLPs find applications in virtually all fields of engineering as discrete variables can be used to represent design decisions about a system and nonlinearities naturally arise from the physical nature of the underlying systems. The solution of these problems is typically very difficult. Dr. Richard is interested in developing solution techniques for these problems, with an emphasis on methods that produce (provably) globally optimal solutions. One particular way of achieving this goal is to design schemes to construct strong convex relaxations of MINLPs that can be incorporated in a divide-and-conquer framework. Dr. Richard is particularly interested in how lifting and disjunctive programming techniques can be used to generate such convex relaxations in the space of original variables. Specifically, Dr. Richard and is co-authors extended lifting to the nonlinear setting and showed how disjunctive formulations can be projected in closed-form when sets satisfy some orthogonally disjunctive properties. They also provided a general framework to explain most existing closed-form expressions for convex envelopes using submodularity results, and devised convex relaxations and convexification procedures for problems with certain multilinear terms, complementarity constraints, cardinality constraints, and permutation invariance.

• Cutting Planes Algorithms for MILPs:

Although MILPs form an apparently simple extension of Linear Optimization Problems (LPs), they are typically very hard to solve. Currently, the most successful algorithms for solving these problems are those based on branch-and-cut. A crucial element of branch-and-cut algorithms is the derivation of strong linear relaxations of the MILP at hand. This is typically achieved through the addition of linear inequalities, called cutting planes. Dr. Richard ’s research interests are in the development of cutting planes for MILPs, especially those that do not require the knowledge of the particular structure of the problem at hand. Such a research angle allows the derivation of general tools that can be easily incorporated in commercial solvers and therefore can be easily added to the toolbox of OR practitioners. Specifically, Dr. Richard has designed new lifting techniques for MILPs that are more encompassing than traditional methods because they consider continuous variables and/or multiple problem constraints. Dr. Richard 's work was also instrumental in reviving the study of group theoretic approaches to the generation of families of cutting planes for MILPs.

• Practical Applications of MI(N)LPs:

Dr. Richard has developed MI(N)LPs models and solution techniques for various practical applications, which are summarized next.

• Data analysis and prescriptive analytics: Many problems of finding structures in data or to analyze it involve solving optimization models. Oftentimes, these models are solved using convex optimization techniques, whereas the models themselves are intrinsically nonconvex. Dr. Richard is interested in taking a global optimization perspective to the solution of these problems. For instance, Dr. Richard and his co-authors recently investigated sparse principal component analysis, for which they introduced novel results that produced the strongest convex relaxations known to date. Further, modern machine learning models can be used to model constraints and objective of optimization models for which functional forms are not known and accessible only through data. Dr. Richard and his co-authors are currently investigated how to best formulate these nonconvex optimization models.

• Radiation therapy: In early work, Dr. Richard participated in the development of new MIP techniques for fluence map optimization problems arising in cancer radiation therapy. In particular, this work focused on the modeling of (nonconvex) dose-volume constraints that are used to guarantee that a certain fraction of organs are risk are spared from too intense radiation. In current work with the Department of Radiation Oncology at UMN, Dr. Richard and his co-authors are investigating optimization models arising from radiation therapy, including those that are enabled from new technologies.

• Railroads: In early work, Dr. Richard worked on the use of optimization techniques for railcars assignment problems at Union Pacific. One of his main achievement included the development of a model for the assignment of empty freight cars that was implemented by the company and has provided significant costs savings. Dr. Richard also worked on unit train scheduling problems for coal and rock trains and on the design of algorithms that could be used in practice for the solution of these problems. His work in this area was funded by Union Pacific and CSX.

• Infrastructure: In past work, Dr. Richard investigated the use of optimization techniques for water infrastructure design against intentional attacks and for homeland security risk reduction problems. He also worked recently on data-driven problems related to fire station location and sizing.

Coming soon!

• “Collaborative Research: Novel Relaxations for Cardinality-constrained Optimization Problems with Applications in Network Interdiction and Data Analysis.”

  • Sponsor: National Science Foundation.

  • Role: PI (co-PI M. Tawarmalani)

  • Dates: 08/17-07/22.

  • Award Amount: $351,017.00 (Richard's part of proposal only).

• “Collaborative Research: Novel Tighter Relaxations for Complementarity Constraints with Applications to Nonlinear and Bilevel Programming.”

1. • Sponsor: National Science Foundation.

   • Role: PI (co-PI M. Tawarmalani)

   • Dates: 08/12-07/16.

   • Award Amount: $213,816.00 (Richard's part of proposal only).

• “New Modeling and Solution Paradigms for Transportation Problems with Applications to Railroads.”

  • Sponsor: National Science Foundation.

  • Role: PI.

  • Dates: 05/12-05/17.

  • Award Amount: $233,134.00.

• Incorporating Stochasticity in an Improved Optimization-Based Decision Support System for Coal/Bulk Monthly Reservations Planning.”

  • Sponsor: CSX Transportation.

  • Role: PI (100%).

  • Dates: 02/12-12/12.

  • Award Amount: $48,000.

• “Optimization-based Decision Support System for Coal/Bulk Monthly Reservations Planning.”

  • Sponsor: CSX Transportation.

  • Role: PI (100%).

  • Dates: 02/11-01/12.

  • Award Amount: $37,000.

• “Collaborative Research: Generating Stronger Cuts for Nonlinear Programs Via Orthogonal Disjunctions and Lifting Techniques.”

  • Sponsor: National Science Foundation.

  • Role: PI (co-PI. M. Tawarmalani)

  • Dates: 07/09-06/12.

  • Award Amount: $202,689 (Richard''s part of the proposal only).

• “Cutting Planes Techniques in Nonlinear Programming.”

  • Sponsor: Purdue Research Foundation.

  • Role: PI.

  • Dates: 06/07-05/08.

  • Award Amount: $14,627.

• “Vulnerability Assessment and Mitigation for Water Infrastructure Systems Against Intentional Physical Attacks.”

  • Sponsor: Purdue Research Foundation.

  • Role: PI (50%) (co-PI, M. Lawley)

  • Dates: 09/04-08/06.

  • Award Amount: $14,979.

• “Improving the Assignment of Empty Cars in the UPRR Network.”

  • Sponsor: Union Pacific RailRoad.

  • Role: PI (100%).

  • Dates: 01/04-12/04.

  • Award Amount: $52,396.70.

• “CAREER: Improving the Optimization and Re-Optimization of Mixed Integer Programs through the Study of Continuous Variables.”

  • Sponsor: National Science Foundation.

  • Role: PI.

  • Dates: 01/04-12/08.

  • Award Amount: $400,000.

Coming soon!