Bound on the number of constraints to be generated (lazy constraints)

Question

I am working on a very large optimisation problem. All variables are continuous, the objective is linear and the constraints convex, but I have many such constraints (on the order of $2^n$ — actually, one constraint per possible solution to a given combinatorial problem with $n$ variables). Due to the large number of constraints, I generate them lazily, one by one, as they are required (in case you're wondering, the separation problem involves solving a nonconvex MIQP, but I can approximate it).

I am trying to have any kind of bound on the number of lazy constraints to be generated. Do you have any idea of what techniques could be applied? I am not necessarily interested by an algorithm that could be computing this number (without actually solving the problem and seeing that there are no more lazy constraints to add). However, I would also be keen on getting any insight in the distance to the optimal value when adding $k$ lazy constraints (always found by the separation procedure as maximising the infeasibility).

There should be results like this, as it could be a way to tell whether a robust optimisation program or a TSP instance is hard to solve (i.e. requires an exponential number of lazy constraints, be they retrieved from the uncertainty set or subtour elimination). The only thing I could find was an application of robust optimisation in network routing (Optimal Oblivious Routing in Polynomial Time), but the article did not really provide the required details to fully understand what they are doing:

First, the polynomial bound on the number of iterations follows using the standard bounds on the size of the initial ellipsoid and the smallest “volume” of the feasible set.

Answer 1

The number of lazy constraints that have to be used, depends on the algorithm that is used. I will discuss two algorithms:

1. The cutting-plane method: solve the problem to optimality for a subset of constraints. If any lazy constraints are violated, add some of the violated constraints and solve again. Stop when the solution satisfies all lazy constraints.
2. The ellipsoid method: the optimal solution is contained in an ellipsoid. In each step of the algorithm, the volume of the ellipsoid is decreased until the optimum is found with sufficient precision. See Wikipedia for details.

In practice, the cutting-plane method is often effective for solving problems. However, I am not aware of a bound on the number of lazy constraints that have to be added. For specific problems, such a bound may exists, but I agree with Marco Lübbecke that you can likely construct examples where all lazy constraints are added.

The ellipsoid method is often not useful in practice due to its numerical instability, among other things. However, it is used in theory because of its good worst-case complexity. For example, linear programs can be solved in polynomial time with the ellipsoid method. Under technical assumptions, convex programs can also be solved in polynomial time. In papers, this fact is used to make arguments like:

We model problem X as a convex program. As convex programs can be solved in polynomial time with the ellipsoid method, problem X can be solved in polynomial time. In our implementation, however, we will make use of the cutting-plane method.

Hence, if the technical conditions are satisfied, it follows that only a polynomial number of lazy constraints are used if the ellipsoid method is used. It is probably not possible to translate this result to the cutting-plane method.

As a final remark: even if you only have to add a polynomial number of lazy constraints, the ellipsoid method may still take exponential time if finding a violated lazy constraint takes exponential time.

Answer 2

Unless you use the ellipsoid method, it is very difficult to find a bound on the number of constraints that need to be generated. A recent review paper on cutting planes mentions only a single paper that develops a polynomial cutting plane algorithm, namely Chandrasekaran, Végh and Vempala (2016), who propose a tailored cutting plane approach for the minimum-cost perfect matching problem and prove it converges in polynomial time. Both the algorithm and the proof are rather involved and cannot easily be extended to other problems. Hence, I am afraid there is not much more you can do than wait until your separation oracle indicates the solution is feasible.