论文标题
延长配方的电路
Circuits in Extended Formulations
论文作者
论文摘要
电路和扩展配方是线性编程理论中的经典概念。多面体的电路是可行点之间的基本差向量，并包括所有边缘方向。我们研究了多面体$ p $的电路与$ p $的扩展配方的电路之间的连接，即对polyhendron $ q $的描述，该$ q $线性地投射到$ p $上。 众所周知，$ p $的边缘方向是$ q $的边缘方向的图像。我们表明，在进行预测下的这种“继承”并未扩展到一组电路。我们提供的反例提供了较小数量的刻面，顶点和极端射线，包括聚集的相关多型，并表明继承的电路数量和不可值的电路数量在尺寸中可能呈指数级。 我们进一步证明，除非映射是映射的，否则对于任何固定的线性投影映射，都存在反例。最后，我们表征了那些Polyhedra $ p $，其电路是从所有Polyhedra $ Q $继承到$ p $的所有Polyhedra $ Q $。相反，我们证明，每个多面体$ q $满足温和假设的预测方式都可以使图像Polyhedron $ p $具有$ Q $的电路中没有预先映射的电路。我们的证明是建立在标准结构（例如均质化和脱节编程）上的。
Circuits and extended formulations are classical concepts in linear programming theory. The circuits of a polyhedron are the elementary difference vectors between feasible points and include all edge directions. We study the connection between the circuits of a polyhedron $P$ and those of an extended formulation of $P$, i.e., a description of a polyhedron $Q$ that linearly projects onto $P$. It is well known that the edge directions of $P$ are images of edge directions of $Q$. We show that this `inheritance' under taking projections does not extend to the set of circuits. We provide counterexamples with a provably minimal number of facets, vertices, and extreme rays, including relevant polytopes from clustering, and show that the difference in the number of circuits that are inherited and those that are not can be exponentially large in the dimension. We further prove that counterexamples exist for any fixed linear projection map, unless the map is injective. Finally, we characterize those polyhedra $P$ whose circuits are inherited from all polyhedra $Q$ that linearly project onto $P$. Conversely, we prove that every polyhedron $Q$ satisfying mild assumptions can be projected in such a way that the image polyhedron $P$ has a circuit with no preimage among the circuits of $Q$. Our proofs build on standard constructions such as homogenization and disjunctive programming.
