A Tighten-and-Branch ILP Algorithm Framework under Generalized Formulation

Host Institution:

RMIT University

Title of Seminar:

A Tighten-and-Branch ILP Algorithm Framework under Generalized Formulation

Speaker's Name:

Dr Yanqun Liu

Speaker's Institution:

RMIT University, School of Mathematical and Geospatial Science

Time and Date:

Friday 30 March 2012, 3:30pm (AEDT)

Seminar Abstract:

In this talk, we present a numerical method for a class of generalized inequality constrained integer linear programming (GILP) problems that includes the usual mixed-integer linear programming (MILP) problems as special cases. Instead of restricting certain variables to integer values as in MILP, we require in these GILP problems that some of the constraint functions take integer values. We present a tighten-and-branch method that has a number of advantages over the usual branch-and-cut algorithms. This includes the ability of keeping the number of constraints unchanged for all subproblems throughout the solution process and the capability of eliminating equality constraints. In addition, the method provides an algorithm framework that allows the existing cutting-plane techniques to be incorporated into the tightening process. As a demonstration, we will solve a well-known ‘hard ILP problem’.

Seminar Convenor:

This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR IT support: