Research: Methodology


This page is devoted to projects developing general methodology. For a description of each project, click below.

Branch, cut, and price algorithms

We are developing a wide variety of methodology for solving large-scale discrete optimization problems using various LP-based branch and bound algorithms based on dynamic generation of variables and constraints. Our research includes development of advanced techniques for bounding, branching, and primal heuristics, as well as methodology for solving problems with multiple objectives, performing sensitivity analysis, and warm starting computations. Such techniques present interesting challenges for implementation. For information on related software development, click here.

Decomposition algorithms

Methods for generating bounds on the optimal value of a MILP are essential to the development of effective solution procedures. Traditionally, bounding methods based on decomposition, such as Dantzig-Wolfe decomposition and Lagrangian relaxation, have been treated as distinct from polyhedral methods that utilize dynamic cut generation for bound improvement. It is possible to view these methods from a common perspective and to integrate them in a way that capitalizes on the strengths of each approach. In this project, we are developing a general framework for such integrated methods, an important element of which is a new paradigm for generating valid inequalities that we call \emph{structured separation}. %Structured separation methods exploit the %known structure of a given solution to enable faster separation algorithms. Relaxed solutions that are integral (but infeasible) are a natural by-product of decomposition-based bounding methods. Such solutions have well-defined structure that allows them to be separated far more efficiently than unstructured ones. We are developing techniques that take advantage of this fact to aid in the generation of new valid inequalities.

Recent publications related to decomposition methods:

Recent presentations related to decomposition methods:

  • M. Galati and T.K.R., A Framework for Decomposition in Integer Programming, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R. and M. Galati, A Framework for Decomposition in Integer Programming, University of Newcastle, Newcastle, NSW, Australia, June 2009 (PDF).

Generalized branching methods

We have several projects focused generally on better methods for branching in solutions methods for mixed integer programs. In particular, we are considering methods for selecting effective general disjunctions in an automatic way. We are also considering a specific method known as bilevel branching focused on combinatorial problems for which single-variable branching is ineffective.

Recent publications related to branching methods:

  • A. Mahajan and T.K.R., On the Complexity of Selecting Branching Disjunctions in Integer Programming, to appear in the SIAM Journal on Optimization (2009) (Working paper version: PDF)
  • A. Mahajan and T.K.R., Experiments with Branching using General Disjunctions, The Proceedings of the Eleventh INFORMS Computing Society Meeting (2009), 101-118 (Working paper version: PDF)

Recent presentations related to branching methods:

Parallel tree search

We currently have a number of projects under development in this area, but our main effort is currently devoted to the CHiPPS project, in which we are developing methodology to improve the scalability of large-scale, data-intensive applications, such as branch, cut, and price. Our methods are based on the use compact data structures, asynchronous messsaging, advanced load balancing and sophisticated knowledge-sharing mechanisms that reduce parallel overhead.

Recent publications related to parallel tree search:

  • Y. Xu, T.K.R., L. Ladányi, and M.J. Saltzman, Computational Experience with a Software Framework for Parallel Integer Programming (Revised), to appear in the INFORMS Journal on Computing (2009) (Working paper version: PDF).
  • T.K.R., Parallel Branch and Cut, in Parallel Combinatorial Optimization, E. Talbi, ed. (2006) (Working paper version: PS PDF)
  • Y. Xu, T.K.R., L. Ladányi, and M.J. Saltzman, ALPS: A Framework for Implementing Parallel Search Algorithms, The Proceedings of the Ninth INFORMS Computing Society Conference (2005), 319 (Working paper version: PS PDF).
  • T.K.R., L. Ladányi, and M.J. Saltzman, A Library Hierarchy for Implementing Scalable Parallel Search Algorithms, The Journal of Supercomputing 28 (2004), 215. (Working paper version: PS PDF).
  • T.K.R., Parallel Branch and Cut for Capacitated Vehicle Routing, Parallel Computing, 29 (2003), 607 (Working paper version: PS PDF).

Recent presentations related to parallel tree search:

  • T.K.R., Y. Xu, L. Ladanyi, and M.Saltzman, Implementing Custom Applications with CHiPPS, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R., Y. Xu, L. Ladanyi, and M.Saltzman, Computational Experience with Parallel Integer Programming using the CHiPPS Framework, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R., Y. Xu, L. Ladanyi, and M.Saltzman, Doing it in Parallel (DIP) with the COIN-OR High Performance Parallel Search Framework (CHiPPS), University of Newcastle, Newcastle, NSW, Australia, May 2009 (PDF).
  • T.K.R., M. Guzelsoy, J.T. Linderoth, M.J. Saltzman, and M. Wiecek, Using Cyberinfrastructure Tools to Solve Biobjective Integer Programs, INFORMS Annual Conference, Pittsburgh, PA, November 2006 (PDF).

Dual methods for mixed integer linear programming

In this research, we are trying to extend to the realm of mixed-integer programming the ability to warm start LP-based branch and bound algorithms and the ability to perform sensitivity analysis. These capabilities have long been available with solvers for linear programs, but are largely missing from MILP solvers. The ability to warm start MILP computations will greatly improve the efficiency of methods for which a series of slightly modified MILPs must be solved. These methods include those for analyzing multicriteria MILPs, stochastic integer programs, and infeasible MILPs, and for performing sensitivity analysis. The aforementioned methods are all generally related to robust optimization and are important to practical mixed-integer programming.

Recent publications related to dual methods:

  • M. Guzelsoy and T.K.R., The Value Function of a Mixed-Integer Linear Program with a Single Constraint, COR@L Laboratory Technical Report (2006) (Available by request).
  • M. Guzelsoy and T.K.R., Duality for Mixed-Integer Linear Programs, The International Journal of Operations Research 4 (2007), 118-137 (Working paper version: PS PDF).
  • T.K.R. and M. Guzelsoy, Duality and Warm Starting in Integer Programming, Proceedings of the 2006 NSF Design, Service, and Manufacturing Grantees and Research Conference (PS PDF).
  • T.K.R. and M. Guzelsoy, The SYMPHONY Callable Library for Mixed Integer Programming, The Proceedings of the Ninth INFORMS Computing Society Conference (2005), 61 (Working paper version: PS PDF).

Recent presentations related to dual methods:

  • M. Guzelsoy, T.K.R. On the Value Function of a Mixed Integer Linear Program, INFORMS Annual Conference, San Diego, October 2009 (PDF).
  • T.K.R. and M. Guzelsoy, Duality in Mixed Integer Linear Programming, University of Newcastle, Newcastle, NSW, Australia, May 2009 (PDF).
  • T.K.R. and M. Guzelsoy, On the Value Function of a General Mixed Integer Linear Program, Victoria University of Wellington, New Zealand, January 2009.
  • M. Guzelsoy and T.K.R., Warm Starting for Mixed Integer Linear Programming, INFORMS Annual Meeting, Washington, D.C., October, 2008.

Bilevel integer programming

We are developing methods for solving general mixed integer bilevel programs by exploiting the structure of the lower-level value function. We plan to release a software package for this called MibS. We also have several related projects involving the theory of bilevel programming.

Recent publications related to bilevel programming:

Recent presentations related to bilevel programming:

Multicriteria integer programming

MILPs with multiple, competing objectives occur naturally in practice and are typically very difficult to analyze. We are developing efficient methods both for generating the complete set of Pareto outcomes and for generating a “representative sample” for such multi-objective MILPs.

Recent publications related to multicriteria integer programming:

  • T.K.R., M.J. Saltzman, and M.M. Wiecek, An Improved Algorithm for Biobjective Integer Programming, Annals of Operations Research 147 (2006), 43 (Working paper version: PS PDF).
  • T.K.R. and M. Guzelsoy,
    The SYMPHONY Callable Library for Mixed Integer Programming, The Proceedings of the Ninth INFORMS Computing Society Conference (2005), 61 (Working paper version: PS PDF).

Recent presentations related to multicriteria integer programming:

If you find something here useful, buy me a beer!

Trackback