Search

Given any algorithm for convex optimization that uses exact first-order information (i.e., function values and subgradients), we show how to use such an algorithm to solve the problem with access to inexact first-order information. This is done in a ``black-box'' manner without knowledge of the internal workings of the algorithm. This complements previous work that considers the performance of specific algorithms like (accelerated) gradient descent with inexact information. In particular, our results apply to a wider range of algorithms beyond variants of gradient descent, e.g., projection-free methods, cutting-plane methods, or any other first-order methods formulated in the future. Further, they also apply to algorithms that handle structured nonconvexities like mixed-integer decision variables., Comment: 15 pages, 1 figure

We consider the problem of maximizing the total reward in a transportation system with $M$ buses that serve a set of Origin-Destination (OD) pairs. Each bus operates on at most one line selected from a set of candidate lines, where operating a line incurs multiple resource costs. The goal is to efficiently assign the buses to the lines to serve integral portions of given OD demands while respecting bus capacity, resource limits, and demand constraints. This model significantly generalizes line planning models in prior works by integrating candidate line assignments to buses, broader OD demand specifications, and considering multiple resource constraints. We propose randomized approximation algorithms addressing various problem scenarios. When line costs are zero, we achieve the optimal approximation ratio of $1 - \frac{1}{e}$, assuming $P \neq NP$. For instances with small line costs, the algorithm attains an approximation ratio of $1 - \frac{1}{e} - \eta$. In the most general case, we obtain an approximation ratio of $\frac{1}{2} - \frac{1}{2e} - \eta$. Additionally, we develop an approach ensuring a ratio of $1 - \frac{1}{e} - \eta$ while limiting resource overuse to at most $\tau$ units, where $\eta$ and $\tau$ are arbitrarily small constants. To demonstrate real-world applicability, we modify one of our algorithms to improve practical performance while maintaining a level of theoretical guarantees, and validate it using numerical simulations on real-world data. Results show that our algorithm produces high-quality solutions efficiently, outperforming commercial solvers on challenging instances.

We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived as a corollary of a more fundamental ``transfer" result that shows how lower bounds on information complexity of continuous convex optimization under different oracles can be transferred to the mixed-integer setting in a black-box manner. Further, we (to the best of our knowledge) initiate the study of, and obtain the first set of results on, information complexity under oracles that only reveal \emph{partial} first-order information, e.g., where one can only make a binary query over the function value or subgradient at a given point. We give algorithms for (mixed-integer) convex optimization that work under these less informative oracles. We also give lower bounds showing that, for some of these oracles, every algorithm requires more iterations to achieve a target error compared to when complete first-order information is available. That is, these oracles are provably less informative than full first-order oracles for the purpose of optimization., Comment: 35 pages, 4 figures

When multi-dimensional instruments are used to identify and estimate causal effects, the monotonicity condition may not hold due to heterogeneity in the population. Under a partial monotonicity condition, which only requires the monotonicity to hold for each instrument separately holding all the other instruments fixed, the 2SLS estimand can still be a positively weighted average of LATEs. In this paper, we provide a simple nonparametric test for partial instrument monotonicity. We demonstrate the good finite sample properties of the test through Monte Carlo simulations. We then apply the test to monetary incentives and distance from results centers as instruments for the knowledge of HIV status.

This paper proposes a nonparametric test for $m$th-degree inverse stochastic dominance which is a powerful tool for ranking distribution functions according to social welfare. We construct the test based on empirical process theory. The test is shown to be asymptotically size controlled and consistent. The good finite sample properties of the test are illustrated via Monte Carlo simulations. We apply our test to the inequality growth in the United Kingdom from 1995 to 2010.

Motivated by a transit line planning problem in transportation systems, we investigate the following capacitated assignment problem under a budget constraint. Our model involves $L$ bins and $P$ items. Each bin $l$ has a utilization cost $c_l$ and an $n_l$-dimensional capacity vector. Each item $p$ has an $n_l$-dimensional binary weight vector $r_{lp}$, where the $1$s in $r_{lp}$ (if any) appear in consecutive positions, and its assignment to bin $l$ yields a reward $v_{lp}$. The objective is to maximize total rewards through an assignment that satisfies three constraints: (i) the total weights of assigned items do not violate any bin's capacity; (ii) each item is assigned to at most one open bin; and (iii) the overall utilization costs remain within a total budget $B$. We propose the first randomized rounding algorithm with a constant approximation ratio for this problem. We then apply our framework to the motivating transit line planning problem, presenting corresponding models and conducting numerical experiments using real-world data. Our results demonstrate significant improvements over previous approaches in addressing this critical transportation challenge., Comment: The preliminary version, titled 'Approximation Algorithms for Capacitated Assignment with Budget Constraints and Applications in Transportation Systems,' was accepted at COCOON 2022. The extended version, now titled 'Approximation Algorithm for Generalized Budgeted Assignment Problems and Applications in Transportation Systems,' was accepted by Discrete Applied Mathematics

Inspired by branch-and-bound and cutting plane proofs in mixed-integer optimization and proof complexity, we develop a general approach via Hoffman's Helly systems. This helps to distill the main ideas behind optimality and infeasibility certificates in optimization. The first part of the paper formalizes the notion of a certificate and its size in this general setting. The second part of the paper establishes lower and upper bounds on the sizes of these certificates in various different settings. We show that some important techniques existing in the literature are purely combinatorial in nature and do not depend on any underlying geometric notions.

We show that one can enumerate the vertices of the convex hull of integer points in polytopes whose constraint matrices have bounded and nonzero subdeterminants, in time polynomial in the dimension and encoding size of the polytope. This extends a previous result by Artmann et al. who showed that integer linear optimization in such polytopes can be done in polynomial time.

We study the complexity of cutting planes and branching schemes from a theoretical point of view. We give some rigorous underpinnings to the empirically observed phenomenon that combining cutting planes and branching into a branch-and-cut framework can be orders of magnitude more efficient than employing these tools on their own. In particular, we give general conditions under which a cutting plane strategy and a branching scheme give a provably exponential advantage in efficiency when combined into branch-and-cut. The efficiency of these algorithms is evaluated using two concrete measures: number of iterations and sparsity of constraints used in the intermediate linear/convex programs. To the best of our knowledge, our results are the first mathematically rigorous demonstration of the superiority of branch-and-cut over pure cutting planes and pure branch-and-bound.

We define a new cutting plane closure for pure integer programs called the two-halfspace closure. It is a natural generalization of the well-known Chv\'atal-Gomory closure. We prove that the two-halfspace closure is polyhedral. We also study the corresponding $2$-halfpsace rank of any valid inequality and show that it is at most the split rank of the inequality. Moreover, while the split rank can be strictly larger than the two-halfspace rank, the split rank is at most twice the two-halfspace rank. A key step of our analysis shows that the split closure of a rational polyhedron can be obtained by considering the split closures of all $k$-dimensional (rational) projections of the polyhedron, for any fixed $k\geq 2$. This result may be of independent interest.

We provide a polynomial time cutting plane algorithm based on split cuts to solve integer programs in the plane. We also prove that the split closure of a polyhedron in the plane has polynomial size.

We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP does at least as well as BB, with variable disjunctions. We sharpen this by giving instances of the stable set problem where we can provably establish that CP does exponentially better than BB. We further show that if one moves away from 0/1 sets, this advantage of CP over BB disappears; there are examples where BB finishes in O(1) time, but CP takes infinitely long to prove optimality, and exponentially long to get to arbitrarily close to the optimal value (for variable disjunctions). We next show that if the dimension is considered a fixed constant, then the situation reverses and BB does at least as well as CP (up to a polynomial blow up), no matter which family of disjunctions is used. This is also complemented by examples where this gap is exponential (in the size of the input data).