Skip to content

ISE Seminar

Dr. Natasha Boland

Professor, Georgia Institute of Technology

Exploiting Decomposable Structure to Design Better Algorithms for Solving Integer Programs

Abstract: Optimization problems in which some or all of the variables are constrained to take integer values are of broad applicability in a wide range of fields, ranging from medicine and healthcare to banking and finance to environmental management and conservation. Over recent decades, exact algorithms for their solution have become faster and more efficient, culminating in a variety of commercial software platforms and public domain codes that provide exceptional capability for solving practical problems to optimality. However, this seems to have only increased the appetite of practitioners to solve ever-larger problems, which challenge the state-of-the-art. In this talk, we bring together two apparently disparate observations: (i) many practical problems have decomposable structure and (ii) despite the enormous strides in solution algorithms, one key element common to all of them, namely, the branching rule, has remained largely untouched since it was first presented in the 1960’s. Yet the branching rule defines how the search space is divided in the ``divide-and-conquer’’ paradigm that forms the basis of all exact algorithms; it is central to the algorithm. Here, we will describe a new idea for exploiting decomposable structure in problems to derive alternative, powerful, new branching rules. These rules are demonstrated to speed up commercial solvers by orders of magnitude, on two classes of problems having different characteristics. The potential to generalize these ideas will also be discussed.

Friday, October 12 at 2:30pm to 3:30pm

John D. Tickle Engineering Building, 410
851 Neyland Dr, Knoxville, TN 37996

Event Type

Lectures & Presentations

Topic

Engineering

Audience

Current Students, Faculty & Staff

Website

https://ise.utk.edu/graduate/graduate...

Department

Industrial and Systems Engineering

Contact Name

Mingzhou Jin

Contact Email

jin@utk.edu

Contact Phone

865-974-3333

Subscribe
Google Calendar iCal Outlook

Recent Activity