I am not aware of any algorithm for counting the number of integral vertices or the proportion of integral vertices of convex polyhedra. I suspect that both of these problems are #P-complete (which is even worse than NP-complete). See here for a definition of #P:

http://en.wikipedia.org/wiki/Sharp-P

Having said that, there is software, such as PORTA or cdd, that can enumerate the vertices of convex polyhedra, but they only work for up to around 25 variables. There are also papers, by people like Alexander Barvinok and Jean-Bernard Lasserre, on methods for counting the number of integral points *within* a convex polyhedron.

Thank you Adam Letchford. I will check de papers. Unfortunatelly, my problem has more than 25 variables.

Regarding those methods by Barvinok, there is some free software called Latte available that implements that method, thanks to Jesus de Loera and others at UC Davis: https://www.math.ucdavis.edu/~mkoeppe/latte/

Furthermore, CPLEX has a solution pool feature for MILPs that you can configure to keep branching until it has found all possible feasible solutions. While using this limits CPLEX's ability to prune nodes (i.e nodes can only be pruned when infeasible) as compared to when branching to find one optimal solution, you still get the benefits of primal MIP preprocessing and cuts to speed up the search. While I wouldn't expect fast results on a huge model, you might get results in a reasonable amount of time for models with a few hundred variables. In addition, if you found that Latte could efficiently give you the number of integer solutions to search for, you could tell CPLEX to stop its search as soon as it found that number of solutions.

Hi Adam Letchford and Ed Klotz. The methods designed by Barvinok provide ways to count the number of integral lattices *inside* a polytope. I was wondering if it would be useful for me since I want to count the number of integral vertex (not inside the polytope). Could you help me on this. Thank you in advance.

I'm sorry, but I am not aware of any algorithm to do this, that works for more than about 25 variables. (Unless your polytope has a high degree of symmetry. In that case, perhaps you could do a clever enumeration that avoids considering vertices that are isomorphic to ones already considered.)

Francisco, I don't have an immediate answer either. Off the top of my head, I can think of two approaches to try, but I haven't thought through either.

1. Perhaps you could apply Barvinok's (or some other lattice counting) algorithm twice. First just do it for your polytope go get the count of integer solutions inside. Then, expand the polytope so that the current vertex points are in the interior rather than the boundary. Run Barvinok's algorithm again, and the difference between this result and the previous result gives you the count you want. However, this relies on being able to come up with a way to expand the polytope that doesn't add other integer solutions that are outside of your original polytope. Furthermore, it must also be practical in terms of finite precision; if the perturbation involves really small amounts, it might work in theory, but not in practice. I'm not sure how promising this approach is, but I'm throwing it out just in case. I'm somewhat concerned that the problem of expanding the polytope in the way I have described as just as hard as the counting problem you want to solve.

2. You could use CPLEX's solution pool feature to enumerate all integer feasible solutions, then take each solution and test if it lies on the boundary. The test for the boundary condition involves solving an LP: if x is your solution, you want to check if there exist a y and z such that x = 1/2/ y + 1/2z, with Ay = b and Az = b. If so, x does not lie on the boundary. But, running CPLEX's solution pool to enumerate all solutions could take quite a while. While I expect it would work well for many (but not all) variables with more than 25 variables, I don't expect it to scale very well to models with thousands or hundreds of thousands of variables. But, if your polytopes are modest in size, and you are familiar with calling CPLEX from any of its programming APIs, you could probably get something up and running pretty quickly and see how it works. And who knows; perhaps going through that exercise would make you recognize some way to spend up this process. On the other hand, the notion of finding all integer feasible solutions so you can extract the ones on the boundary doesn't seem particularly efficient; if there was some boundary condition that was easy to formulate to add to the model, that would be more promising.

You could randomly sample vertices and estimate the ratio of integer vertices to non integer vertices. This could be done by means of Markov Chain Monte Carlo. Is there any special reason for you to know exactly how many integer vertices are there?

Hi Anselmo. Randomly choosing vertices seems a good approach. Basically I could design the objective function of the linear optimization problem to random directions. With a high number of samples, I would get an estimate (statistical) of the ratio of integer vertices over the total number of vertices. I would like to know this estimate in order to know how often the linear integer optimization that I am studying can be solved by linear (continuous) optimization problems that are much efficient in terms of computer computations. In the cases that I do not get an integer solution, I would use a rounding strategy of the fractional solution (still to be searched).

This is a possible approach, though computationally intensive, as you would be solving a linear program to optimality only to generate a single sample vertex. Instead, you could find an initial vertex, and then randomly choose the next direction, i.e., the next variable to enter the basis. In this way, you would sample a new vertex in each pivoting operation. Obviously the samples are correlated, as you would be randomly walking on the vertices. In order to mitigate the effect of the correlation, you could take as a valid sample the vertex generated in every k pivoting operations.

The paper "On integer points in polyhedra" by 

W. Cook, M. Hartmann, R. Kannan, C. McDiarmid

gives a bound on the number of vertices of the integer hull of a polyhedron. Some improvements have been made since.

See the survey

Zolotykh N. Yu. On the number of vertices in integer linear programming problems. eprint arXiv:math/0611356 [math.CO], 2006.

for more information.

In Hartman's thesis,

M. Hartmann. Cutting planes and the complexity of the integer hull. Technical Report 819, School of Operations Research and Industrial Engineering, Cornell University, 1989.

he gave an algorithm for computing the integer hull and its vertices which runs in polynomial time in fixed dimension.

A procedure similar to this appears to be implemented in

Algorithmic Aspects in Information and Management

Lecture Notes in Computer Science Volume 5564, 2009, pp 85-99

Integer Polyhedra for Program Analysis

Philip J. Charles, Jacob M. Howe, Andy King

I did not find any open source code, but the paper mentions several other packages that have similar implementations, such as the barvinok package for lattice point counting.