Rounding Integer Linear Programming Algorithm: Difference between revisions
Jump to navigation
Jump to search
m (Text replace - " (2009)" to " (2009)") |
m (Text replacement - "ions]] " to "ion]]s ") |
||
| (24 intermediate revisions by 3 users not shown) | |||
| 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> | * <B>Example(s):</B> | ||
* <B | ** 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]]. | |||
---- | ---- | ||
---- | ---- | ||
===2010=== | == References == | ||
=== 2010 === | |||
* http://en.wikipedia.org/wiki/Linear_programming_relaxation | * http://en.wikipedia.org/wiki/Linear_programming_relaxation | ||
** In mathematics, the '''linear programming relaxation | ** In mathematics, the '''linear programming relaxation</B> of a [[0-1 Integer Program|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 (Mathematics)|interval]] [0,1]. | ||
** | ** … The resulting relaxation is a [[Linear Program|linear program]], hence the name. This [[Relaxation Technique (Mathematics)|relaxation technique]] transforms an [[NP-hard]] optimization problem (integer programming) into a related problem that is solvable in [[Polynomial Time|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=== | === 2009 === | ||
* ([[ | * ([[2009_CollectiveAnnotationofWikipedia|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]]). [http://dx.doi.org/10.1145/1557019.1557073 doi:10.1145/1557019.1557073]. | ||
** We investigate practical solutions based on local hill-climbing, <B>[[Rounding Integer Linear Programming Algorithm|rounding integer linear programs]]</B>, and pre-clustering entities followed by local optimization within clusters. ... We propose practical and effective heuristics based on [[local hill-climbing]] and [[Linear Program Relaxation|linear program relaxations]]. | ** [[We]] investigate practical solutions based on local hill-climbing, <B>[[Rounding Integer Linear Programming Algorithm|rounding integer linear programs]]</B>, and pre-clustering entities followed by local optimization within clusters. ... [[We]] propose practical and effective heuristics based on [[local hill-climbing]] and [[Linear Program Relaxation|linear program relaxations]]. | ||
===1990=== | === 1990 === | ||
* ([[1990_ApproximationAlgsForSchedUnrelParMachines|Lenstra | * ([[1990_ApproximationAlgsForSchedUnrelParMachines|Lenstra et al., 1990]]) ⇒ Jan Karel Lenstra, David B. Shmoys, and [[Éva Tardos]]. ([[1990]]). “Approximation Algorithms for Scheduling Unrelated Parallel Machines.” In: [[Mathematical Programming Journal|Mathematical Programming]], 46(1). [http://dx.doi.org/10.1007/BF01585745 doi:10.1007/BF01585745] | ||
** One of the most natural [[Integer Linear Program Algorithm|strategies]] to obtain good [[ILP Output| | ** One of the most natural [[Integer Linear Program Algorithm|strategies]] to obtain good [[ILP Output|solution]]s to an [[Integer Linear Programming Task|integer linear program]] is to drop the [[Integrality Constraint|integrality constraints]], solve the resulting [[Integer Linear Programming Task|linear programming problem]], and then [[ILP Solution Rounding Task|round the solution]] to an [[Integral Task Output|integral solution]]. | ||
---- | ---- | ||
Latest revision as of 07:32, 22 August 2024
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.