• Speaker: Dr Yanqun Liu, School of Mathematical and Geospatial Sciences, RMIT University
  • Title: A Tighten-and-Branch ILP Algorithm Framework under Generalized Formulation
  • Location: Room V206, Mathematics Building (Callaghan Campus) The University of Newcastle
  • Access Grid Venue: TBC
  • Time and Date: 3:30 pm, Fri, 30th Mar 2012
  • Persons outside the School of Mathematical and Physical Sciences should RSVP to agr@newcastle.edu.au.
  • 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".

  • [Permanent link]