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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Austin Buchanan Dec 11 '15 at 6:02
  • $\begingroup$ 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. $\endgroup$ – Sriram S Dec 13 '15 at 17:53
  • $\begingroup$ 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. $\endgroup$ – Sriram S Dec 13 '15 at 17:56
  • $\begingroup$ 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? $\endgroup$ – maksay Dec 14 '15 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.