Rounding Integer Linear Programming Algorithm

Example(s):
- a Local Hill-Climbing Rounding Integer Linear Programming Algorithm (Kulkarni et al., 2009).
See: Rounding, Linear Program Relaxation, Randomized Rounding Procedure.

References

http://en.wikipedia.org/wiki/Linear_programming_relaxation
- In mathematics, the linear programming relaxation of a 0-1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval [0,1].
- … The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.

(Kulkarni et al., 2009) ⇒ Sayali Kulkarni, Amit Singh, Ganesh Ramakrishnan, Soumen Chakrabarti. (2009). “Collective Annotation of Wikipedia Entities in Web Text.” In: Proceedings of ACM SIGKDD Conference (KDD-2009). doi:10.1145/1557019.1557073.
- We investigate practical solutions based on local hill-climbing, rounding integer linear programs, and pre-clustering entities followed by local optimization within clusters. ... We propose practical and effective heuristics based on local hill-climbing and linear program relaxations.

(Lenstra et al., 1990) ⇒ Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. (1990). “Approximation Algorithms for Scheduling Unrelated Parallel Machines.” In: Mathematical Programming, 46(1). doi:10.1007/BF01585745
- One of the most natural strategies to obtain good solutions to an integer linear program is to drop the integrality constraints, solve the resulting linear programming problem, and then round the solution to an integral solution.