We study two-stage stochastic mixed integer programs (TSS-MIPs) with integer variables in the second stage. We show that under suitable conditions, the second stage MIPs can be convexified by adding parametric cuts a priori. As special cases, we extend the results of Miller and Wolsey (Math Program 98(1):73-88, 2003) to TSS-MIPs. Furthermore, we consider second … Read more
We present a branch-and-bound framework to solve the following problem: Given a graph G and an integer k, find a subgraph of G formed by removing no more than k edges that contains the most symmetry. We call symmetries on such a subgraph “almost symmetries” of G. We implement our branch-and-bound framework in PEBBL to … Read more
In this paper we consider a particular method of clustering for graphs, namely the modularity density maximization. We propose a hierarchical divisive heuristic which works by splitting recursively a cluster into two new clusters by maximizing the modularity density, and we derive four reformulations for the mathematical programming model used to obtain the optimal splitting. … Read more
In many real-world transportation systems, passengers are often required to make a number of interchanges between different modes of transport. As cities continue to grow, a greater number of these connections tend to occur within centrally located Transport Hubs. In order to encourage the uptake of public transport in major cities, it is important for … Read more
As shown in [9, 1], signals whose wavelet coefficients exhibit a rooted tree structure can be recovered — using specially-adapted compressed sensing algorithms — from just $n=\mathcal{O}(k)$ measurements, where $k$ is the sparsity of the signal. Motivated by these results, we introduce a simplified proportional-dimensional asymptotic framework which enables the quantitative evaluation of recovery guarantees … Read more
This paper describes an accelerated HPE-type method based on general Bregman distances for solving monotone saddle-point (SP) problems. The algorithm is a special instance of a non-Euclidean hybrid proximal extragradient framework introduced by Svaiter and Solodov [28] where the prox sub-inclusions are solved using an accelerated gradient method. It generalizes the accelerated HPE algorithm presented … Read more
The primal-dual Dikin-type affine scaling method was originally proposed for linear optimization and then extended to semidefinite optimization. Here, the method is generalized to symmetric conic optimization using the notion of Euclidean Jordan algebras. The method starts with an interior feasible but not necessarily centered primal-dual solution, and it features both centering and reducing the … Read more
Recently, Pena and Soheili presented a deterministic rescaling perceptron algorithm and proved that it solves a feasible perceptron problem in $O(m^2n^2\log(\rho^{-1}))$ perceptron update steps, where $\rho$ is the radius of the largest inscribed ball. The original stochastic rescaling perceptron algorithm of Dunagan and Vempala is based on systematic increase of $\rho$, while the proof of … Read more
In this paper we consider a broad class of distributionally robust optimization (DRO for short) problems where the probability of the underlying random variables depends on the decision variables and the ambiguity set is de ned through parametric moment conditions with generic cone constraints. Under some moderate conditions including Slater type conditions of cone constrained moment … Read more
The objective of this work is to study weak infeasibility in second order cone programming. For this purpose, we consider a relaxation sequence of feasibility problems that mostly preserve the feasibility status of the original problem. This is used to show that for a given weakly infeasible problem at most m directions are needed to … Read more