On cutting planes for cardinality-constrained linear programs
On cutting planes for cardinality-constrained linear programs
复制标题
关于基数约束线性规划的割平面
DOI：
10.1007/s10107-018-1306-0
复制
发表时间：
2018
影响因子：
2.7
通讯作者：
Richard, Jean-Philippe P.
中科院分区：
文献类型：
--
作者：
Kim, Jinhak;Tawarmalani, Mohit;Richard, Jean-Philippe P.
我们推导出基数约束线性规划的割平面。这些不等式可以用来分离问题的LP松弛的任何基本可行解，假设该解违反基数要求。为了得到它们，我们首先放松给定的单纯形表到一个析取集，表示在空间的非基本变量。我们建立了这个集合的闭凸船体的有效不等式的系数服从可以直接从单纯形表计算的比率。我们证明了运输问题可以用来分离这些不等式。然后，我们给出了一个建设性的程序，以产生违反小面定义不等式的闭凸船体的析取集使用的一个变种Prim的算法。
We derive cutting planes for cardinality-constrained linear programs. These inequalities can be used to separate any basic feasible solution of an LP relaxation of the problem, assuming that this solution violates the cardinality requirement. To derive them, we first relax the given simplex tableau into a disjunctive set, expressed in the space of nonbasic variables. We establish that coefficients of valid inequalities for the closed convex hull of this set obey ratios that can be computed directly from the simplex tableau. We show that a transportation problem can be used to separate these inequalities. We then give a constructive procedure to generate violated facet-defining inequalities for the closed convex hull of the disjunctive set using a variant of Prim’s algorithm.
登录
查看更多内容
影响因子：
1.1
作者：
R. Gomory
通讯作者：
R. Gomory
关于 p 中位数多胞形
影响因子：
2.7
作者：
P. Avella;A. Sassano
通讯作者：
A. Sassano
具有不相交基数约束的 0-1 背包问题的多面体研究：通过顺序提升定义面不等式
DOI：
10.1016/j.disopt.2010.09.005
发表时间：
2011
期刊：
Discret. Optim.
影响因子：
--
作者：
Bo Zeng;Jean
通讯作者：
Jean
影响因子：
--
作者：
PRIM, RC
通讯作者：
PRIM, RC
技术说明 - 补充编程中剪切的使用
DOI：
10.1287/opre.21.1.353
发表时间：
1973
期刊：
Oper. Res.
影响因子：
--
作者：
T. Ibaraki
通讯作者：
T. Ibaraki