1

こんにちは、n次元の境界の線形不等式を持つ多面体があります。

  1. この多面体の整数点の数を見つける方法 (正確または近似)。
  2. この多面体の整数点の座標を見つける方法。
4

2 に答える 2

0

あなたにいくつかの検索用語を与えるために：あなたが説明するのは、整数プログラムに対する実行可能な解の列挙です。

前回このようなものが必要になったとき、すぐに使用できるソリューションが見つからなかったため、「<a href="http://martin.von-gagern.net/projects/idp/」という独自の実装を作成しました。 「 rel="nofollow">バンド」。これは分岐アルゴリズムに基づいており、COIN-ORの線形計画法エンジンを使用して、対応する線形 (非整数) プログラムに実行可能な解があるかどうかを判断します。用途に合わせてご自由にお使いください。

格子点の数を単純に決定することに関しては、それを計算するための式があったと思いますが、詳細は覚えていません。私が覚えている限り、その式は実際に解を列挙するのに役に立ちませんでした。

最近の出版物を見ると、 LattEを見たいと思うかもしれません。

于 2012-07-29T07:46:19.890 に答える
0

(凸包の中で) 与えられた多面体の整数点を計算できるソフトウェアはportaです。

ただし、この問題に関連するすべてのソフトウェアは列挙に基づいているため、大きなモデルでは失敗します。

よろしくお願いします

于 2012-07-31T14:48:07.557 に答える