Research: Methodology

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

Branch, Cut, and Price Algorithms

We are developing advanced 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.

Recent publications related to branch, cut, and price methods:

  • T.K.R., Parallel Branch and Cut, in Parallel Combinatorial Optimization, E. Talbi, ed. (2006) (Working paper version: PS PDF)
  • J.T. Linderoth and T.K.R., Noncommercial Software for Mixed-Integer Linear Programming, to appear in Integer Programming: Theory and Practice, John Karlof, ed. (2005) (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).
  • T.K.R., SYMPHONY Version 5.0 User’s Manual, Lehigh University Industrial and Systems Engineering Technical Report 04T-009 (2004) (PS PDF).
  • T.K.R., L. Ladányi, and M.J. Saltzman, Parallel Branch, Cut, and Price for Large-scale Discrete Optimization, Mathematical Programming 98 (2003), 253 (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).
  • L. Ladányi, T.K.R., and L.E. Trotter Jr., Branch, Cut, and Price: Sequential and Parallel, in Computational Combinatorial Optimization, D. Naddef and M. Juenger, eds., Springer, Berlin (2001), 223 (PS PDF).

Recent presentations related to branch, cut, and price methods:

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:

Multicriteria Integer Programming Algorithms

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:

Warm Starting and Sensitivity Analysis 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 warm starting and sensitivity analysis:

  • 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, to appear in a special issue of the International Journal of Operations Research on Integer Programming (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 warm starting and sensitivity analysis:

Parallel Algorithms

We currently have a number of projects under development in this area, but our main effort is currently devoted to the ALPS 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 parallelism:

  • 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., L. Ladányi, and M.J. Saltzman, Parallel Branch, Cut, and Price for Large-scale Discrete Optimization, Mathematical Programming 98 (2003), 253 (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).
  • L. Ladányi, T.K.R., and L.E. Trotter Jr., Branch, Cut, and Price: Sequential and Parallel, in Computational Combinatorial Optimization, D. Naddef and M. Juenger, eds., Springer, Berlin (2001), 223 (PS PDF).

Recent presentations related to parallelism:

Trackback