Integer Solutions of Linear Programming Problems

Answered

Sudheer Reddy

March 25, 2024 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

• Official comment

  

  Simranjit Kaur

  • Gurobi Staff

  November 13, 2026 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

  March 25, 2024 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

Post is closed for comments.