×

zbMATH — the first resource for mathematics

A hybrid primal heuristic for finding feasible solutions to mixed integer programs. (English) Zbl 1380.90193
Summary: We present a new framework for finding feasible solutions to mixed integer programs (MIP). We use the feasibility pump heuristic coupled to a biased random-key genetic algorithm (BRKGA). The feasibility pump heuristic attempts to find a feasible solution to a MIP by first rounding a solution to the linear programming (LP) relaxation to an integer (but not necessarily feasible) solution and then projecting it to a feasible solution to the LP relaxation. The BRKGA is able to build a pool of projected and rounded but not necessarily feasible solutions and to combine them using information from previous projections. This information is also used to fix variables during the process to speed up the solution of the LP relaxations, and to reduce the problem size in enumeration phases. Experimental results show that this approach is able to find feasible solutions for instances where the original feasibility pump or a commercial mixed integer programming solver often fail.

MSC:
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
FEASPUMP; MIRPLib; SPOT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optimization, 4, 1, 77-86, (2007) · Zbl 1170.90443
[2] Andrade, C. E.; Miyazawa, F. K.; Resende, M. G.C., Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem, Proceedings of the 15th annual conference on genetic and evolutionary computation GECCO’13, 463-470, (2013), ACM New York, NY, USA
[3] Andrade, C. E.; Resende, M. G.C.; Karloff, H. J.; Miyazawa, F. K., Evolutionary algorithms for overlapping correlation clustering, Proceedings of the 16th conference on genetic and evolutionary computation GECCO’14, 405-412, (2014), ACM New York, NY, USA
[4] Andrade, C. E.; Resende, M. G.C.; Zhang, W.; Sinha, R. K.; Reichmann, K. C.; Doverspike, R. D.; Miyazawa, F. K., A biased random-key genetic algorithm for wireless backhaul network design, Applied Soft Computing, 33, 150-169, (2015)
[5] Andrade, C. E.; Toso, R. F.; Resende, M. G.C.; Miyazawa, F. K., Biased random-key genetic algorithms for the winner determination problem in combinatorial auctions, Evolutionary Computation, 23, 279-307, (2015)
[6] Baena, D.; Castro, J., Using the analytic center in the feasibility pump, Operations Research Letters, 39, 5, 310-317, (2011) · Zbl 1235.90098
[7] Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optimization, 4, 1, 63-76, (2007) · Zbl 1169.90415
[8] Berthold, T.; Hendel, G., Shift-and-propagate, Journal of Heuristics, 21, 1, 73-106, (2015) · Zbl 1360.90297
[9] Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated F-race: an overview, Experimental methods for the analysis of optimization algorithms, 311-336, (2010), Springer Berlin Heidelberg · Zbl 1204.68280
[10] Boland, N. L.; Eberhard, A. C.; Engineer, F. C.; Fischetti, M.; Savelsbergh, M. W.P.; Tsoukalas, A., Boosting the feasibility pump, Mathematical Programming Computation, 6, 3, 255-279, (2014) · Zbl 1323.65065
[11] Caserta, M.; Reiners, T., A pool-based pattern generation algorithm for logical analysis of data with automatic fine-tuning, European Journal of Operational Research, 248, 2, 593-606, (2016) · Zbl 1347.62107
[12] Ericsson, M.; Resende, M. G.C.; Pardalos, P. M., A genetic algorithm for the weight setting problem in OSPF routing, Journal of Combinatorial Optimization, 6, 3, 299-333, (2002) · Zbl 1068.90092
[13] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical Programming, 104, 1, 91-104, (2005) · Zbl 1077.90039
[14] Fischetti, M.; Salvagnin, D., Feasibility pump 2.0, Mathematical Programming Computation, 1, 2-3, 201-222, (2009) · Zbl 1180.90208
[15] Glover, F.; Laguna, M., General purpose heuristics for integer programming - part I, Journal of Heuristics, 2, 4, 343-358, (1997) · Zbl 0887.90123
[16] Glover, F.; Laguna, M., General purpose heuristics for integer programming - part II, Journal of Heuristics, 3, 2, 161-179, (1997) · Zbl 0898.90094
[17] Gonçalves, J. F.; de Almeida, J. R., A hybrid genetic algorithm for assembly line balancing, Journal of Heuristics, 8, 6, 629-642, (2002)
[18] Gonçalves, J. F.; Resende, M. G.C., Biased random-key genetic algorithms for combinatorial optimization, Journal of Heuristics, 17, 487-525, (2011)
[19] Gonçalves, J. F.; Resende, M. G.C., A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem, Journal of Combinatorial Optimization, 22, 2, 180-201, (2011)
[20] Hanafi, S.; Lazić, J.; Mladenović, N., Variable neighborhood pump heuristic for 0-1 mixed integer programming feasibility, Electronic Notes in Discrete Mathematics, 36, 759-766, (2010) · Zbl 1237.90161
[21] Hansen, P.; Mladenović, N.; Urošević, D., Variable neighborhood search and local branching, Computers & OR, 33, 10, 3034-3045, (2006) · Zbl 1086.90042
[22] Li, Y.; Ergun, O.; Nemhauser, G. L., A dual heuristic for mixed integer programming, Operations Research Letters, 43, 4, 411-417, (2015) · Zbl 1408.90200
[23] Papageorgiou, D. J.; Nemhauser, G. L.; Sokol, J.; Cheon, M.-S.; Keha, A. B., Mirplib - a library of maritime inventory routing problem instances: survey, core model, and benchmark results, European Journal of Operational Research, 235, 2, 350-366, (2014) · Zbl 1305.90072
[24] Santis, M. D.; Lucidi, S.; Rinaldi, F., Feasibility pump-like heuristics for mixed integer problems, Discrete Applied Mathematics, 165, 0, 152-167, (2014) · Zbl 06292070
[25] Stefanello, F.; Aggarwal, V.; Buriol, L. S.; Gonçalves, J. F.; Resende, M. G.C., A biased random-key genetic algorithm for placement of virtual machines across geo-separated data centers, Proceedings of the 2015 on genetic and evolutionary computation conference GECCO ’15, 919-926, (2015), ACM New York, NY, USA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.