Integer Solutions of Linear Programming Problems

回答済み

Sudheer Reddy

2024年03月25日 10:54

• 
• 
• 

Identifying cases where the solution to an LP problem happens to be integer-valued without explicitly formulating it as an Integer Linear Programming (ILP) problem.

I understand that in some LP problems, the optimal solution coincidentally falls on integer coordinates due to the structure of the problem or the relationships among the constraints.

I'm interested in whether there are any indicators or rules of thumb that could help me identify such cases ?

 

0

• 正式なコメント

  

  Simranjit Kaur

  • Gurobi Staff

  2026年11月13日 01:27

  This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
• 

  Elisabeth Rodríguez Heck

  • Gurobi Staff

  2024年03月25日 11:15

  Hi Sudheer,

  This is a very interesting topic. 

  A powerful property related to this is Total Unimodularity. See for example the resources:

  • https://theory.stanford.edu/~jvondrak/MATH233B-2017/lec3.pdf
  • https://www.ise.ncsu.edu/fuzzy-neural/wp-content/uploads/sites/9/2018/04/Lecture6.pdf -> also contains some examples of problems satisfying this property

  As described in the first link, 

  Totally unimodular matrices are very well behaved, because they always define polytopes with
  integer vertices, as long as the right-hand side is integer-valued.

  A related property is Total Dual Integrality (see https://math.mit.edu/~goemans/18438F09/lec7.pdf).

  Best regards,

  Elisabeth

  1

投稿コメントは受け付けていません。