Interdiction for the direct current optimal power flow problem is commonly modeled in two stages, where an attacker disables components in the first stage and an operator makes remedial adjustments in the second stage. The resulting bilevel mathematical program is often solved via transformation into a single-level mixed-integer program using duality. A drawback of this … Read more
The Multi-objective Integer Minimum Cost Flow Problem (MOIMCF) asks for the efficient integer flows of a capacitated network whose arcs carry vectors of conflicting costs. We present an exact algorithm that computes a minimal complete set of efficient flows, based on a characterization of efficiency by circulations in the residual network. The feasible set is … Read more
We introduce a framework that transforms discrete optimization into continuous optimization over parameterized probability distributions. The framework reveals a common distributional structure behind several methods that have largely developed independently, including continuous reformulations for multilinear binary optimization, Markov decision processes and reinforcement learning, the cross-entropy method, mean-field variational optimization, and the quantum approximate optimization algorithm. … Read more
Diffusion in networks is often modeled as a local neighbor-based process: a node becomes active as a result of influence exerted by its active neighbors. However, in many technological and communication settings, adoption is driven not only by local influence, but by access to sufficiently large active connected regions. This paper studies such component-based diffusion … Read more
This paper investigates a presolving method for handling symmetries in mixed-integer programs, based on inequalities computed from so-called Schreier-Sims tables. We show that an iterative application of this method together with merging variables produces an instance for which the symmetry group is trivial. We then prove that the problem structure can be preserved for certain … Read more
Let the elements of a matroid be labeled in an abelian group, and let \(F\) be a finite set of forbidden basis-label sums. We give an alternative proof of the sharp unweighted proximity bound established by Lizhong Chen: for every representable matroid, every basis is within \(|F|\) exchanges of an \(F\)-avoiding basis whenever one exists. … Read more
Classical stochastic approximation methods rely on estimators of the first moment (mean) of a random regression function. We study methods that employ estimators of both the first and the second moments, which include modern deep-learning optimizers such as Adam and Muon as special cases. We derive second-moment stochastic approximation methods through the lens of optimal … Read more
This paper proposes a simple facet enumeration algorithm for convex polytopes. The complexity of the algorithm is analyzed. The algorithm is implemented in Matlab. Some polytopes with known H-representations and V-representations are used as test examples. The preliminary numerical test shows the effectiveness and efficiency of the proposed algorithm. Due to the duality between the … Read more
For more than 20 years, single-leader multi-follower (SLMF) problems have been treated as a more difficult class of problems in comparison to bilevel optimization. In this work we challenge this common belief, studying whether SLMF problems can be reformulated as equivalent bilevel optimization problems. We consider both optimistic and pessimistic formulations. For the optimistic case … Read more
We propose robust and distributionally robust formulations of the risk budgeting problem under the mean absolute deviation (MAD) risk measure. The proposed models address uncertainty in asset returns and their distribution while allocating portfolio risk according to prescribed risk budgets. We first develop a robust model in which historical return observations are perturbed within a … Read more