NDLI: Feasibility pump 2.0

Please wait, while we are loading the content...

Feasibility pump 2.0

Content Provider	Springer Nature Link
Author	Fischetti, Matteo Salvagnin, Domenico
Copyright Year	2009
Abstract	Finding a feasible solution of a given mixed-integer programming (MIP) model is a very important $${\mathcal{NP}}$$ -complete problem that can be extremely hard in practice. Feasibility Pump (FP) is a heuristic scheme for finding a feasible solution to general MIPs that can be viewed as a clever way to round a sequence of fractional solutions of the LP relaxation, until a feasible one is eventually found. In this paper we study the effect of replacing the original rounding function (which is fast and simple, but somehow blind) with more clever rounding heuristics. In particular, we investigate the use of a diving-like procedure based on rounding and constraint propagation—a basic tool in Constraint Programming. Extensive computational results on binary and general integer MIPs from the literature show that the new approach produces a substantial improvement of the FP success rate, without slowing-down the method and with a significantly better quality of the feasible solutions found.
Starting Page	201
Ending Page	222
Page Count	22
File Format	PDF
ISSN	18672949
Journal	Mathematical Programming Computation
Volume Number	1
Issue Number	2-3
e-ISSN	18672957
Language	English
Publisher	Springer-Verlag
Publisher Date	2009-09-17
Publisher Institution	Mathematical Optimization Society
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mixed-integer programming Primal heuristics Constraint programming Constraint propagation Mixed integer programming Combinatorial optimization Polyhedral combinatorics, branch-and-bound, branch-and-cut Approximation methods and heuristics Operations Research/Decision Theory Optimization
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Rounding-based heuristics for nonconvex MINLPs

Testing cut generators for mixed-integer linear programming

Computing compatible tours for the symmetric traveling salesman problem

The time dependent traveling salesman problem: polyhedra and algorithm

Local cuts for mixed-integer programming

Integer programming approaches for minimum stabbing problems

Branch-and-cut for complementarity-constrained optimization

A relax-and-cut framework for Gomory mixed-integer cuts

Solving network design problems via iterative aggregation

Feasibility pump 2.0

Similar Documents

Rounding-based heuristics for nonconvex MINLPs

Testing cut generators for mixed-integer linear programming

Computing compatible tours for the symmetric traveling salesman problem

The time dependent traveling salesman problem: polyhedra and algorithm

Local cuts for mixed-integer programming

Integer programming approaches for minimum stabbing problems

Branch-and-cut for complementarity-constrained optimization

A relax-and-cut framework for Gomory mixed-integer cuts

Solving network design problems via iterative aggregation

Feasibility pump 2.0