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

• 

  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

サインインしてコメントを残してください。