Necessary and sufficient conditions for the existence of a combinatorial algorithm for a given problem. Last semester, I took a combinatorial optimization course where the reference book was Combinatorial Optimization by William J. Cook et al. It was very interesting for me to see the relationship between some great algorithms (like disjktra's shortest path algorithm, edmonds' maximum matching algorithm ...) and LP duality. 

My question is about a general framework on constructing combinatorial algorithms based on LP duality. 

For a given problem what are the necessary and sufficient conditions for the existence of such algorithms. I think duality gap should be the first necessary condition and to have a totally unimodal matrix could be sufficient.

Maybe the answer is written in that book and I should read it again carefully.
Some people in combinatorial optimization use the word "combinatorial algorithm" to mean "algorithm without using ellipsoid method (or interior-point methods)."  For example, Schrijver's Fulkerson-prize-winning paper has a title "A combinatorial algorithm minimizing submodular functions in strongly polynomial time."  The co-winners (Iwata, Fleischer, and Fujishige) also have "A combinatorial strongly polynomial algorithm for minimizing submodular function."

As far as I see the field of combinatorial optimization, people there actually try to give an answer to the posed question, and still struggle.  Cunningham's survey "Matching, matroids, and extensions" (Mathematical Programming B91 (2002) 515-542) is a bit old by now, but you can see how generalizations of Edmonds' blossom algorithm and concepts on matroid lead to combinatorial polynomial-time algorithms for other problems.  Please note that the field has been advanced since the survey, and good sources are probably some papers from IPCO (Integer Programming and Combinatorial Optimization).

I would like to point out that an big open problem is to find a combinatorial algorithm for the maximum independent set problem for perfect graphs running in strongly polynomial time.