برمجة الأعداد الصحيحة
تعريف برمجة الأعداد الصحيحة :هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. في كثير من الحالات هذا المصطلح يُعبِر عن البرمجة الخطية الصحيحة، التي فيها دالة الهدف والقيود تكون خطية.
البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة.
حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود
البرمجة الخطية الصحيحة في الشكل المُتعارف عليه يُعبر عنها كالتالي:
والبرمجة الخطية الصحيحة بالشكل القياسي يُعبر عنها كالتالي :
بحيث أن المُدخلات ال C , B عبارة عن متجهات وال A عباره عن مصفوفة تحتوي على قيم صحيحة 
لاحظ أنه مشابه للبرمجة الخطية . البرمجة الخطية الصحيحة التي ليست في الشكل القياسي يمكن تحويلها إلى الشكل القياسي 
عن طريق حذف شرط عدم التساوي بإضافة متغير إضافي للمعادلة واستبدال المتغيرات الغير مُقيدة بالإشارة بالفرق بين متغيرين مقيدين بالإشارة .
الشكل التالي يوضح المسألة التالية :
النقاط الصحيحة للحل هي الموضحة باللون الأحمر في الشكل المقابل بينما الخط المتقطع الأحمر يُعبِر عن شكلهم المُحدب ، الذي هو عبارة عن مجسم صغير يحتوي على كل هذه النقاط .
الخطوط الزرقاء مع المحاور تُعبِر عن مجسم للبرمجة الخطية البسيطة المُعطى بشروط عدم التساوي .
الهدف من الأمثَلَه هو تحريك الخط الأسود المُنقَّط أعلى مايمكن بشرط أن يضل ملامس للمُجسم . نقاط الحل الأمثل لهذه المسألة هي (1,2) و (2, 2) حيث أن قيمة دالة الهدف في النقطتين السابقتين هي القيمة 2. 
الحل الوحيد الأمثل التي تصل فيه الدلة إلى حالة الإستقرار وتكون برمجة خطية غير مقيده هو (1.8, 2.8) حيث أن قيمة دالة الهدف في النقطة السابقة هي القيمة 2.8 
لاحظ أنه إذا قرَّبنا قيمة دالة الهدف (2.8) إلى أقرب عدد صحيح (3) من الشكل نلاحظ أنه خارج منطقة الحل .
البرمجة الخطية الصحيحة المختلطة : عباره عن مسألة تحتوي على متغيرات بعضها مُقيده بأن تكون صحيحة والبعض الآخر مسموح لها بأن تكون غير صحيحة .
البرمجة الخطية صفر- واحد هي المسألة التي تتضمن متغيرات مُقيدة بأن تكون صفر أو واحد . لاحظ أن المتغيرات الصحيحة المحدودة يمكن أن يُعبَر عنها كخليط من المتغيرات الرقمية ، على سبيل المثال ، مُعطى متغير صحيح formula_4 ، المتغير يمكن أن يُعبَر عنه بإستخدام formula_5 المتغيرات الرقيمة
العديد من المسائل يمكن صياغتها بشكل برمجة خطية صحيحة 
بما أن حلول البرمجة الخطية الصحيحة يمكن التأكد منها بإستخدام كثيرة الحدود الموجودة في مسألة كثيرة حدود غير قطعية كاملة والمسألة الغير حتمية متعددة الحدود يمكن أن تُختَزل بواسطة دالة كثيرة حدود إلى البرمجة الخطية الصحيحة ، إذا البرمجة الخطية الصحيحة هي مسأله غير حتمية متعددة الحدود .
هناك سببان رئيسيان لإستخدام المتغيرات الصحيحه عند تصميم المسائل كبرمجة خطيه
هذه الإعتبارات بتظر بشكل مستمر في الحياة العملية وبالتالي البرمجة الخطية الصحيحه يمكن أن تستخدم في عدة تطبيقات بعضها سنتطرق للحديث عنها بشكل مختصر كما يلي :
البرمجة الخطية المختلطه لها العديد من التطبيقات في الإنتاج الصناعي . أحد الأمثله المهمة وهو تخطيط الإنتاج الزراعي الذي يشمل تحديد العائد الإنتاجي للعديد من المحاصيل المشتركة في المصادر ، على سبيل المثال ، ( الأرض والعمل والأسمده … إلخ ). دالة الهدف هنا هي زيادة الإنتاج الكُلي بشرط عدم زيادة المصادر المتوفره . في بعض الحالات يمكن أن يُعبر عنها كمسألة برمجة خطيه ، لكن المتغيرات لابد أن تكون أعداد صحيحه.
هذه المسائل تقدم خدمه في جدولة خطوط النقل، على سبيل المثال ، هذه المسألة تُستخدم في مترو الأنفاق لتحديد مسارات مختلفه في أوقات محدده يتم التعامل معها من قِبَل السائقين. المتغيرات التي تؤثر على القرار تُعبر ما إذا كان السائق سوف يسلك هذا الطريق أو لا .
الطريقة البسيطة لحل مسائل البرمجة الخطية الصحيحة هي خذف القيد الذي فيه x عباره عن رقم صحيح، الحل المكافئ للبرمجة الخطية الصحيحة (يُسمى البرمجة الخطية الصحيحة الغير مقيدة ) وبعد ذالك يتم تقريب مدخلات الحلول لهذه المسألة . لكن ليس من الضروري أن تكون هذه هي الحلول الأمثل ، ولايمكن أن تكون حتى ضمن نطاق الحل، ممكن أنها لا تحقق بعض القيود.
بينما في الصيغة العامة الحل لمسألة البرمجة الخطية الغير مُقيدة لاتضمن بأن تكون مُثلى، لو البرمجة الخطية الصحيحة بالشكل التالي :
formula_7
بحيث ان formula_8 where formula_9 and formula_10
حيث أن ال A, B, C أعداد صحيحة وال A أُحادية النمط، بعد ذالك كل الحلول الأساسية الممكنة تكون أعداد صحيحة. بناء على ذالك ، الحل الناتج من طريقة التبسيط (برمجة) نضمن بأن يكون عدد صحيح. لتوضيح أن كل الحلول الأساسية الممكنة تكون أعداد صحيحة نفرض أن ال x هو حل أساسي عشوائي ضمن نطاق الحل
وبما أن ال formula_11 يكون في نطاق الحل ونحن نعرف أن ال formula_11 نفرض ان formula_13. Let formula_14هي عبارة عن العناصر المكافئة للأعمدة الأساسية التي تُعبر عن الحلول الأساسية formula_11 . بتعريف الأساسيات ، هناك بعض المصفوفات الجزئية المربعة B من A مع أعمدة خطية مستقلة مثال ذالكformula_16 of
formula_17 من هنا أعمدة ال B تكون مستقلة خطية وال B مربعة ، ال B لديها معكوس ، وبالتالي حسب الفرض ال B أحادية النمط ،وبالتالي المحددة 
formula_18 وأيضا بما أن B لديها معكوس ولذالك formula_19 بتعرف ال formula_20 لاحظ أن formula_21 يرمز لمقلوب  ال B وتكون أعداد صحيحة بسبب
أن ال B أعداد صحيحة . ولذالك 
كل الحلول الأساسية الممكنة أعداد صحيحة .
وبالتالي إذا المصفوفه A التابعة للبرمجة الخطية تكون أحادية النمط ، بدلا عن استخدام خوارزميات البرمجة الخطية الصحيحة ، الطريقة البسيطة يمكن أن تستخدم لحل البرمجة الخطية الغير مُقيدة والحل يكون عباره عن أعداد صحيحة .
عندما المصفوفة A لاتكون أحادية النمط ، هناك تغيٌر في الخوارزميات التي تُستخدم في حل البرمجة الخطية الصحيحة بشكل دقيق .
أحد أصناف الخوارزميات طرق تقاطع المستويات  التي تعمل على حل البرمجة الخطية الغير مقيده ومن ثم إضافة القيود الخطية التي تقود الحل بإتجاه الأعداد الصحيحة بدون إستثناء أي من نقاط الحل الصحيحة الممكنة.
صنف اخر من الخوارزميات يكون متغير من الفرع والحد يضم الصنفين السابقين . خوارزميات الفرع والحد تمتلك عددا من المميزات أكثر من الخوارزميات التي تستخدم فقط المستويا المتقاطعة. واحدة من ميزات هذه الخوارزميات أنها تعطينا على الأقل حل واحد صحيح بطريقة سريعة في نطاق الحل وليس من الضروري أن يكون حل أمثَل.
علاوة على ذالك حلول البرمجة الخطية الغير مقيدة يمكن أن تُستخدم لتقييم أسواء حالة تٌحدد بعد الحل الناتج عن الحل الأمثل. أخيرا، طُرق الفرع والحد يمكن أن تُستخدم لكي تعطينا العديد من الحلول المُثلى
Lenstra in 1983 يوضح أنه عندما يكون عدد المتغيرات ثابت ، فإن البرمجة الصحيحة يمكن أن تُحل بإستخدام كثيرة الحدود.
بما أن البرمجة الخطية الصحيحة هي مسألة كثيرة حدود غير قطعية كاملة، فإن الكثير من المسائل تكون مُعقدة وبالتالي طُرق الحدس المهني لابد أن تُستخدم بديلا عنها، على سبيل المثال البحث المقارب يمكن أن يُستخدم للبحث عن حلول للبرمجة الخطية الصحيحة ، لإستخدام البحث المقارب لحل البرمجة الخطية الصحيحة ، فإن الخطوات يمكن أن تُعرف بزيادة أو نقصان المتغيرات الصحيحه المقيده في نطاق الحل، بينما نحافظ على كل المتغيرات المتبقيه ثابته .
الذاكرة القصيرة يمكن أن تحتوي على الحلول المُجربة سابقا بينما الذاكرة المتوسطة يمكن أن تحتوي على قيم للمتغيرات الصحيحة المقيَدة الناتجة من قيم دالة الهدف.
أخيرا الذاكرة طويلة المدى يمكن أن توجه البحث بإتجاه القيم الصحيحة التي لم تُجرب مسبقا.
هناك طُرق أخرى للحدس المهني من الممكن أن تُطبق على البرمجة الخطية الصحيحة :
هناك أيضا مجموعة متنوعة من مسائل الحدس المهني الأخرى، على سبيل المثال، مسألة البائع المتجول يُستخدم لحل مسألة سفريات مندوب المبيعات. لاحظ أن عيوب طرق الحدس المهني لو فشلت في إيجاد الحل فإنه لايمكن أن نحدد ما إذا كان السبب أن الحل الناتج لايكون ضمن نطاق الحل أو أن الخوارزميات البسيطة غيرة قادرة على إيجاد أحد الحلول. علاوة على ذلك فإنه من المستحيل أن تُحدد قرب الحل الناتج من الحل الأمثل بإستخدام هذه الطرق.