Content deleted Content added
No edit summary |
Al-Quaknaa (talk | contribs) |
||
| (10 intermediate revisions by 10 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject Mathematics|priority=High}}
}}
The suggestion that refers to the German page refers to the German page for Linear Programming, not Integer. I would recommend removing this banner.
[[User:StitchProgramming|StitchProgramming]] ([[User talk:StitchProgramming|talk]]) 14:02, 8 July 2011 (UTC)
:The German page is on [[integer linear programming]], which in the English Wikipedia redirects to [[Linear_program#Integer_unknowns]]. One possibility would be to expand this article with integer linear programming; others would be to expand [[Linear_program#Integer_unknowns]] or create a separate article on integer linear programming. But then perhaps this article should be merged with [[Discrete optimization]]? [[User:Isheden|Isheden]] ([[User talk:Isheden|talk]]) 14:40, 8 July 2011 (UTC)
How is this the only information about this huge field of study? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/128.8.110.78|128.8.110.78]] ([[User talk:128.8.110.78|talk]]) 00:37, 13 May 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
:I agree. Of all the Wikipedia articles about computer science related topics that I have seen, the quality of this article compared to my expectation for the quality of this article is extremely low. [[User:Bender2k14|Bender2k14]] ([[User talk:Bender2k14|talk]]) 02:53, 29 August 2010 (UTC)
It would be nice to point out that Ax <= b means each element of Ax is less than or equal to the corresponding element in b, Ax(i) ≤ b(i)
[[User:Nduchon|Nduchon]] ([[User talk:Nduchon|talk]]) 16:00, 12 December 2014 (UTC)
Why not introduce "Binary Program" (0-1 integer program) on this page or may be create a separate dedicated page for "Binary Program"?Amit 05:18, 29 March 2017 (UTC) <!-- Template:Unsigned --><small class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Qx2020|Qx2020]] ([[User talk:Qx2020#top|talk]] • [[Special:Contributions/Qx2020|contribs]]) </small> <!--Autosigned by SineBot-->
The article says ILP is NP-Complete, but only decision problems can be NP-complete, as far as I'm aware. I have no references to back this up.
== LP relaxation ==
The term "LP relaxation" is used in the Example section, but it is not explained until the "Algorithm" section further down the article. A reader (like myself) unfamiliar with the concept would benefit from an explanation of "LP relaxation" (and link to its page) in the first instance it is used. Perhaps the content could be reorganized or rewritten? [[User:Zor Quatre|Zor Quatre]] ([[User talk:Zor Quatre|talk]]) 23:14, 23 August 2023 (UTC)
== No dependence on input numbers in fixed dimension? ==
The article includes the following sentence: "Doignon's theorem asserts that an integer program is feasible whenever every subset of ''2^n'' constraints is feasible; a method combining this result with algorithms for LP-type problems can be used to solve integer programs in time that is linear in ''m'' and fixed-parameter tractable (FPT) in ''n'', but possibly doubly exponential in ''n'', '''with no dependence on ''V''.'''" (emphasis in the end mine)
I'm skeptical of this, and I couldn't find exactly this statement in the cited reference. If I'm wrong, the reference should contain a pointer to a specific statement. Why I think the claim does not hold: computing the gcd can be encoded as an ILP in 2 variables, and computing the gcd in any reasonable model takes non-constant number of operations (https://dl.acm.org/doi/abs/10.1145/103516.103522). So, what is meant here? [[User:Al-Quaknaa|Martin Koutecký]] ([[User talk:Al-Quaknaa|talk]]) 12:24, 27 April 2025 (UTC)
| |||