The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Article Download View The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization
Month: September 2023
Affine FR : an effective facial reduction algorithm for semidefinite relaxations of combinatorial problems
\(\) We develop a new method called \emph{affine FR} for recovering Slater’s condition for semidefinite programming (SDP) relaxations of combinatorial optimization (CO) problems. Affine FR is a user-friendly method, as it is fully automatic and only requires a description of the problem. We provide a rigorous analysis of differences between affine FR and the existing … Read more
Using orthogonally structured positive bases for constructing positive k-spanning sets with cosine measure guarantees
\(\) Positive spanning sets span a given vector space by nonnegative linear combinations of their elements. These have attracted significant attention in recent years, owing to their extensive use in derivative-free optimization. In this setting, the quality of a positive spanning set is assessed through its cosine measure, a geometric quantity that expresses how well … Read more
A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming
One of the chief attractions of stochastic mixed-integer second-order cone programming is its diverse applications, especially in engineering (Alzalg and Alioui, {\em IEEE Access}, 10:3522-3547, 2022). The linear and nonlinear versions of this class of optimization problems are still unsolved yet. In this paper, we develop a hybrid optimization algorithm coupling branch-and-bound and primal-dual interior-point … Read more
A Bilevel Optimization Approach for a Class of Combinatorial Problems with Disruptions and Probing
\(\) We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision-maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which … Read more
A generalized asymmetric forward-backward-adjoint algorithm for convex-concave saddle-point problem
The convex-concave minimax problem, known as the saddle-point problem, has been extensively studied from various aspects including the algorithm design, convergence condition and complexity. In this paper, we propose a generalized asymmetric forward-backward-adjoint (G-AFBA) algorithm to solve such a problem by utilizing both the proximal techniques and the interactive information of primal-dual updates. Except enjoying … Read more
Limited memory gradient methods for unconstrained optimization
The limited memory steepest descent method (Fletcher, 2012) for unconstrained optimization problems stores a few past gradients to compute multiple stepsizes at once. We review this method and propose new variants. For strictly convex quadratic objective functions, we study the numerical behavior of different techniques to compute new stepsizes. In particular, we introduce a method … Read more
Adaptive Consensus: A network pruning approach for decentralized optimization
We consider network-based decentralized optimization problems, where each node in the network possesses a local function and the objective is to collectively attain a consensus solution that minimizes the sum of all the local functions. A major challenge in decentralized optimization is the reliance on communication which remains a considerable bottleneck in many applications. To … Read more
Optimal Multi-Agent Pickup and Delivery Using Branch-and-Cut-and-Price
Given a set of agents and a set of pickup-delivery requests located on a two-dimensional map, the Multi-Agent Pickup and Delivery problem assigns the requests to the agents such that every agent moves from its start location to the locations of its assigned requests and finally to its end location without colliding into any other … Read more
Robust Optimization Under Controllable Uncertainty
Applications for optimization with uncertain data in practice often feature a possibility to reduce the uncertainty at a given query cost, e.g., by conducting measurements, surveys, or paying a third party in advance to limit the deviations. To model this type of applications we introduce the concept of optimization problems under controllable uncertainty (OCU). For … Read more