期刊名称：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 ∈ ZZn |
A = A§} in order to tackle the feasibility problem for the set X+ =
X∩n
+. Here the goal isnot to find an improved polyhedral relaxation
of conv(X+), but rather to reformulate in such a way that the new
variablesin troduced provide good branching directions, and in certain
circumstances permit one to deduce rapidly that the instance is infeasible.
For the case that A hasone row a we analyze the reformulations
in more detail. In particular, we determine the integer width of the
extended formulationsin the direction of the last coordinate, and derive
a lower bound on the Frobeniusn umber 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.
关键词：fertility, war, bargaining power, collapse, natural resources.
