Rounding Integer Linear Programming Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replace - " (2009)" to " (2009)") |
No edit summary |
||
| Line 1: | Line 1: | ||
A [[Rounding Integer Linear Programming Algorithm]] is an [[Integer Linear Programming Algorithm]] that replaces the [[Integrality Constraint|integrality constraints]] with a [[Unit Interval|unit interval constraint]], solves the resulting [[Linear Programming Task|linear programming problem]], and then [[Rounding Function|rounds]] the [[LP Output|solution]] to an [[ILP Solution|integral solution]]. | A [[Rounding Integer Linear Programming Algorithm]] is an [[Integer Linear Programming Algorithm]] that replaces the [[Integrality Constraint|integrality constraints]] with a [[Unit Interval|unit interval constraint]], solves the resulting [[Linear Programming Task|linear programming problem]], and then [[Rounding Function|rounds]] the [[LP Output|solution]] to an [[ILP Solution|integral solution]]. | ||
* <B><U>See</U>:</B> [[Rounding]], [[Linear Program Relaxation]], [[Randomized Rounding Procedure]]. | |||
* <B><U>See</U>:</B> [[Rounding | |||
---- | ---- | ||
---- | ---- | ||
Revision as of 16:37, 9 September 2013
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.
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 & 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 & 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.