期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2007
卷号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：We study different extended formulations for the set X = {x ∈ Ζn | Ax = Ax0}
in order to tackle the feasibility problem for the set X+ = X ∩ Ζn
+. Here the goal
is not to find an improved polyhedral relaxation of conv(X+), but rather to
reformulate in such a way that the new variables introduced provide good
branching directions, and in certain circumstances permit one to deduce rapidly
that the instance is infeasible. For the case that A has one row a we analyze the
reformulations in more detail. In particular, we determine the integer width of
the extended formulations in the direction of the last coordinate, and derive a
lower bound on the Frobenius number of a. We also suggest how a
decomposition of the vector a can be obtained that will provide a useful
extended formulation. Our theoretical results are accompanied by a small
computational study.
