Optimization Online


Using the analytic center in the feasibility pump

Daniel Baena(daniel.baena***at***upc.edu)
Jordi Castro(jordi.castro***at***upc.edu)

Abstract: The feasibility pump (FP) [5,7] has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for finding better quality solutions. Briefly, FP alternates between two sequences of points: one of feasible so- lutions for the relaxed problem (but not integer), and another of integer points (but not feasible for the relaxed problem). Hopefully, the procedure may eventually converge to a feasible and integer solution. Integer points are obtained from the feasible ones by some rounding procedure. This short paper extends FP, such that the integer point is obtained by rounding a point on the (feasible) segment between the computed feasible point and the analytic center for the relaxed linear problem. Since points in the segment are closer (may be even interior) to the convex hull of integer solutions, it may be expected that the rounded point has more chances to become feasible, thus reducing the number of FP iterations. When the selected point to be rounded is the feasible solution of the relaxation (i.e., one of the two end points of the segment), this analytic center FP variant behaves as the standard FP. Computational results show that this variant may be effcient in some MILP instances.

Keywords: Analytic Center, Interior-point Methods, Mixed-integer Linear Programming, Feasibility Problem, Primal Heuristics

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: D. Baena, J. Castro, Using the analytic center in the feasibility pump, Research Report DR 2010/03, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2010.

Download: [PDF]

Entry Submitted: 11/05/2010
Entry Accepted: 11/05/2010
Entry Last Modified: 11/05/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society