Rounding Integer Linear Programming Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replacement - "** ..." to "** …") |
m (Text replacement - ". ----" to ". ----") |
||
| Line 3: | Line 3: | ||
** a [[Local Hill-Climbing Rounding Integer Linear Programming Algorithm]] ([[2009_CollectiveAnnotationofWikipedia|Kulkarni et al., 2009]]). | ** a [[Local Hill-Climbing Rounding Integer Linear Programming Algorithm]] ([[2009_CollectiveAnnotationofWikipedia|Kulkarni et al., 2009]]). | ||
* <B>See:</B> [[Rounding]], [[Linear Program Relaxation]], [[Randomized Rounding Procedure]]. | * <B>See:</B> [[Rounding]], [[Linear Program Relaxation]], [[Randomized Rounding Procedure]]. | ||
---- | ---- | ||
---- | ---- | ||
Revision as of 20:40, 23 September 2021
A Rounding Integer Linear Programming Algorithm is an Integer Linear Programming Algorithm that replaces the integrality constraints with a unit interval constraint, solves the resulting linear programming problem, and then rounds the solution to an integral solution.
- Example(s):
- See: Rounding, Linear Program Relaxation, Randomized Rounding Procedure.
References
2010
- 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.
2009
- (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.
1990
- (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.