问个和整数线性规划有关的问题

先打预防针。这是工作中碰到的问题，不是什么ACM题，所以没有严格的时间空间这类限制。要蹭分的出门左转，这里不是乃应该回帖的地方。


线性规划可以理解为R^n空间上若干个半平面围成的一个解。解空间是个凸多面体这也是众所周知的。整数线性规划的解就是这个凸多面体内的整点。
在同一个空间R^n上，假设有多个整数线性规划问题，它们的解空间分别是S1,S2,...,Sk。每一个Si都可以表示为某个凸多面体内的整点集合。
现在定义S = S1 + S2 + ... + Sk = {v1+v2+...+vk | vi \in Si}，即S集合里每个向量可以写成S1~Sk里每个集合取1个向量的和。
由定义，S显然也是一个R^n上整点构成的集合。

现在的问题是：
1. 是否存在一个凸多面体，使得S恰好是这个凸多面体内的整点集？换句话说，就是S是否是某个线性规划问题的整数解集？
2. 如果前一个问题的回答是肯定的，那是否存在一个合理的算法能够算出这个凸多面体，i.e.把这个线性规划问题给描述出来？

求解这个线性规划目前不在问题的范围之内，但是如果需要的话俺会在回帖里追加的。

---------
以下是一个例子。
假设S1={(0,0),(0,1)}, S2={(0,0),(1,0)}，那S={(0,0),(0,1),(1,0),(1,1)}。这个可以用0<=x<=1,0<=y<=1的线性规划去描述。

这帖在版块里似乎神隐了。bump一下。

ライラちゃん、乃这问题忒深邃了⋯⋯估计CSDN里木有人能回答出啊～～

第一问，感觉如果整数解是有限个，应该存在这样的多面体，而且应该是凸的（不清楚不凸的话是否就没有单纯型法了？）。证明我就不会了。

第二问没太明白，是说已知整点集，反过来推出一个线性规划么？