العثور على نقاط عدد صحيح في بوليهيدرون

Question

مرحبا لدينا polyhedron مع عدم المساواة الخطية بحدودها في أبعاد N.

1. كيفية العثور على عدد عدد العناصر الصحيحة في هذا polyhedron (بالضبط أو تقريبا).
2. كيفية العثور على إحداثيات النقاط عدد صحيح في هذا polyhedron.

Answer 1

لتعطيك بعض مصطلحات البحث: ما تصفه هو تعداد من الحلول ممكن إلى برنامج صحيح.

آخر مرة كنت بحاجة إلى شيء من هذا القبيل، لم أتمكن من العثور على حل جاهز للاستخدام، لذلك كتبت تنفيذا الخاص بي يسمى " bande ". يعتمد على خوارزمية متفرعة، باستخدام محرك البرمجة الخطي من Coin-or لتحديد ما إذا كان المقابلة البرنامج الخطي (غير صحيح) لديه أي حلول مجدية. لا تتردد في استخدام ذلك يناسب حاجتك.

كما هو الحال ببساطة تحديد نقاط من نقاط شعرية: أعتقد أن هناك بعض الصيغة لحساب ذلك، لكنني لا أتذكر أي تفاصيل. بقدر ما أتذكر أن هذه الصيغة لم تكن فائدة في تعداد الحلول فعليا.

تبحث في المنشورات الأخيرة تقترح أنك قد ترغب في الحصول على انظر إلى Latte .

Answer 2

برنامج Beeing قادرة على حساب النقاط المعتمدة من مادة متعدد الوطن المعطاة (من بين بدن محدب) هو بورتا .

ومع ذلك، فإن جميع البرامج المتعلقة بهذه المشكلة هذه بشأن التعدادات، بحيث تفشل في نماذج أكبر.

مع أطيب التحيات