To access the full text documents, please follow this link:

Using the analytic center in the feasibility pump
Baena Mirabete, Daniel; Castro Pérez, Jordi
Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa; Universitat Politècnica de Catalunya. GNOM - Grup d´Optimització Numèrica i Modelització
The feasibility pump (FP) [5, 7] has proved to be a successful heuristic for finding feasible solutions if 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 solutions 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 efficient in some MILP instances.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Programació matemàtica
Programming (Mathematics)
Programació (Matemàtica)
Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming
Attribution-NonCommercial-NoDerivs 3.0 Spain
Article - Draft

Show full item record

Related documents

Other documents of the same author

Rosas Díaz, Dulce María; Castro Pérez, Jordi; Montero Mercadé, Lídia
Castro Pérez, Jordi; González Alastrué, José Antonio