Integrallity in convex hull of a linear programming

Question 1

To add a bit to Martin answer above (I think this is too long for a comment):

There is a general procedure that I know of, called Chvátal-Gomorry procedure, which allow to ultimately describe the convex hull by adding Gomorry cuts. This is very interesting theoretically; however, there is a well-known example where this procedure takes n step (a parameter in the LP) for a problem with two variables and two constraints, i.e. the number of cuts added cannot be bounded by the size of the problem.
Totally unimodular matrix are common in problems arising in graph theory, but it is certainly not a "general" method: you can convince yourself just by the definition that the coefficient of the A matrix must be 0, 1 or -1 in a TU matrix, which is usually not the case in a ILP of course.

Of course, since solving an LP is polynomial and solving an ILP is NP-complete, one cannot expect that there is a general efficient method to do what you expect, since that would almost reduce ILP to LP!

But if you are studiying a problem in particular, especially if it has a simple structure, it could be one of the "special cases" where one of the two methods above are effective.

I can provide further references at the end of the week if you are interested.

Question 2

In the sense of a formulation, a linear program yields a polyhedron with (in general) fractional extreme points. If you want to solve exactly this problem, there is nothing to change /manipulate at the polyhedron.

If you have a (mixed) integer linear program (MIP), you may be interested in the description of the convex hull of its integer points. In general, this can be used for a fast solution process, since you can solve its linear relaxation without performing a branch and bound process afterwards.

This means, the linear relaxation of the MIP gives a polyhedron which contains this convex hull - and which itself needs not have integer extreme points. In many cases, you want to tighten this formulation towards the convex hull of the integer points, which is done by the usual solvers (e.g. by adding inequalities). The aim is always to obtain a formulation of said convex hull. However, finding this formulation is generally NP-hard (so there are no known general techniques to obtain it easily). Especially this means, that the size of such a formulation (i.e., the amount of inequalities) can be exponential.

The are algorithms to compute convex hulls of integer points (or from general polyhedrons), but they are not simple and not "fast". Software, which can help you there is probably Porta or Polymake.

There are properties describing when polyhedrons/formulations are integer. E.g. one of these goes by the name of total (dual) unimodularity. Formulating your problem in such a way or identifying this property is not easy and I am not aware of any structural approaches for doing so.

I hope this helps :)

Kind regards,

Martin