General question: What software can solve convex programs defined by a separation oracle?
The objective function is concave, and the feasible set is a polytope. By a separation oracle I mean that I would program a function that, on input a point, would return whether or not that point is in the feasible set and, if the point is not, also produce an inequality separating the given point from the feasible set. I'd love to be able to feed this function into something like cvxopt or mosek and maximize a concave function.
More specifically, the polytope I'm interested in is the convex hull of the indicators of basis of a matroid. We assume that we have an efficient independence oracle for the matroid, meaning that we obtain a separation oracle for the polytope via the techniques in Testing Membership in Matroid Polyhedra by Cunningham.
I would be interested in the following special case:
Specific Question: What software / algorithms are practically useful for maximizing a concave function over the spanning tree polytope?
Edit: It appears that the correct word to use for OR is "cutting plane," rather than "separation oracle." These notes overview some cutting plane methods.
Background: I am interested in implementing the algorithm in this paper.
I am aware that the ellipsoid method can be in theory used for this, but as I understand it that algorithm is not practically useful. I know that the number of spanning trees can be calculated efficiently without this; I'm just curious about the effectiveness of this particular algorithm, and would like to compare it to this case where the correct answer can be calculated.
Update: We reached out to Nima Anari, and he suggested using something like Frank-Wolfe since the specific polytopes I was interested in had efficient linear optimization oracles. There is a little bit of funny business guaranteeing convergence, since the curvature of the entropy function blows up near parts of the boundary, but initializing with a "random" point in the interior worked well in practice. The code is here: https://github.com/LorenzoNajt/EntropyCounting/blob/master/README.md