线性规划的松弛
Sign in to savelinear program that arises by removing the integrality constraints in an integer program
In the Vinony graph
Vinony's link graph records 33 inbound references to 线性规划的松弛, and connects out to linear programming, approximation algorithm and International Standard Book Number.
It sits within the topics Combinatorial optimization, Linear programming and Polyhedral combinatorics.
Vinony links it to 6 Wikipedia language editions.
Wikidata facts
- Subclass of
- problem
Show 1 more fact
- maintained by WikiProject
- WikiProject Mathematics
Sources (3)
via Wikidata · CC0
Article · 中文
在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。
Abstract from DBpedia / Wikipedia · CC BY-SA
Connections
linear programming
Entity
approximation algorithm
Entity
International Standard Book Number
Entity
set
Entity
digital object identifier
Entity
union
Entity
travelling salesperson problem
Entity
George Bernard Dantzig
Entity
László Lovász
Entity
greedy algorithm
Entity
graph coloring
Entity
convex hull
Entity
time complexity
Entity
NP-hard
Entity
randomized algorithm
Entity
CiteSeerX
Entity
harmonic number
Entity
integer programming
Entity
optimization problem
Entity
combinatorial optimization
Entity