<p>I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU).  However, even though constraint matrix is small (14x20), extensive generation of random coefficients for objective function did not allow me to find the problem formulation for which optimal solution value changes if I add integrality constraints.</p>

<p>I believe that the reason might be that I also have some constraints on the objective function coefficients - I know that some coefficients are 0'os, and some coefficients are equal.</p>

<p>Given that, I wanted to know if it is possible to prove that given my specific subset of objective functions the objective will always be integral, and what should be the way to do that.</p>

<p>Provided that my hypothesis is true, I also wanted to ask if it is easy to find an integer solution, given the solution of an LP, if I know that the objective function value will be the same. (Some kind of movement on the hyperplane of active constraints?)</p>

<p>Any relevant literature links are appreciated.</p>

<p>Thank you!</p>

CC BY-SA 3.0
2015-12-11T06:02:19.517Z
If you only have $n=20$ variables and $m=14$ constraints, you can probably just enumerate all basic feasible solutions and check that they are integral.
Austin Buchanan
CC BY-SA 3.0
2015-12-13T17:53:23.500Z
Following Austin's comment: use a tool like  the Parma Polyhedral Library to enumerate all the vertices of your feasible region. A 14 x 20 problem is possibly in the  realm of sizes that PPL can handle: but vertex enumeration is a hard problem and in your case, you can get as many as  $$\binom{20}{14}$$ vertices in your result. Verify that all vertices are integral. Note that if an LP has an optimal solution then an optimal solution can be found as a vertex of it's feasible region.
Sriram S
CC BY-SA 3.0
2015-12-13T17:56:33.773Z
Also, when you know that your objective has certain structure, it is possible to eliminate vertices that can never be optimal for an objective function of your form. For example, with each vertex, I can easily characterize all the objective functions for which the vertex will be an optimal solution. What you have to check that this set of objectives has a nonempty intersection with the ones you care about. I hope this makes sense. Otherwise, I can expand on this as well.
Sriram S
CC BY-SA 3.0
2015-12-14T11:14:24.180Z
Thank you for your replies. Unfortunately, 20x14 is the smallest instance of a problem for which I found that the matrix is not totally unimodular and yet the objective values of IP and LP are equal. In practice, however, I will have much bigger matrices. 


@SriramS , can you please expand? Your second comment applies only after enumerating the vertices, is that correct? And to find such a set of objectives for a given vertex, I have to find all the hyperplanes which gave me this vertex, and my set of objectives would be a linear combination of their normals?
maksay
<optimization><linear-programming><integer-programming>
How to prove integrality of LP with not totally unimodular matrix
maksay
# How to prove integrality of LP with not totally unimodular matrix

(Asked by: username_0 on 2015-12-09)

I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU). However, even though constraint matrix is small (14x20), extensive generation of random coefficients for objective function did not allow me to find the problem formulation for which optimal solution value changes if I add integrality constraints.

I believe that the reason might be that I also have some constraints on the objective function coefficients - I know that some coefficients are 0'os, and some coefficients are equal.

Given that, I wanted to know if it is possible to prove that given my specific subset of objective functions the objective will always be integral, and what should be the way to do that.

Provided that my hypothesis is true, I also wanted to ask if it is easy to find an integer solution, given the solution of an LP, if I know that the objective function value will be the same. (Some kind of movement on the hyperplane of active constraints?)

Any relevant literature links are appreciated.

Thank you!

**Tags:** optimization, linear-programming, integer-programming

> **Comments:**
> **username_1**: If you only have $n=20$ variables and $m=14$ constraints, you can probably just enumerate all basic feasible solutions and check that they are integral.  
> **username_2**: Following Austin's comment: use a tool like  the Parma Polyhedral Library to enumerate all the vertices of your feasible region. A 14 x 20 problem is possibly in the  realm of sizes that PPL can handle: but vertex enumeration is a hard problem and in your case, you can get as many as  $$\binom{20}{14}$$ vertices in your result. Verify that all vertices are integral. Note that if an LP has an optimal solution then an optimal solution can be found as a vertex of it's feasible region.  
> **username_2**: Also, when you know that your objective has certain structure, it is possible to eliminate vertices that can never be optimal for an objective function of your form. For example, with each vertex, I can easily characterize all the objective functions for which the vertex will be an optimal solution. What you have to check that this set of objectives has a nonempty intersection with the ones you care about. I hope this makes sense. Otherwise, I can expand on this as well.  
> **username_0**: Thank you for your replies. Unfortunately, 20x14 is the smallest instance of a problem for which I found that the matrix is not totally unimodular and yet the objective values of IP and LP are equal. In practice, however, I will have much bigger matrices.    @SriramS , can you please expand? Your second comment applies only after enumerating the vertices, is that correct? And to find such a set of objectives for a given vertex, I have to find all the hyperplanes which gave me this vertex, and my set of objectives would be a linear combination of their normals?  

---

## 0 answers

