  


Using the analytic center in the feasibility pump
Daniel Baena(daniel.baenaupc.edu) Abstract: The feasibility pump (FP) [5,7] has proved to be a successful heuristic for ﬁnding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for ﬁnding better quality solutions. Brieﬂy, 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, Interiorpoint Methods, Mixedinteger 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  