New Multirectional Mean Value Inequality
We establish new and stronger inequality of Clarke-Ledyaev type by direct construction. Citation Preprint, 2017, Sofia University Article Download View New Multirectional Mean Value Inequality
The Robust Uncapacitated Lot Sizing Model with Uncertainty Range
We study robust versions of the uncapacitated lot sizing problem, where the demand is subject to uncertainty. The robust models are guided by three parameters, namely, the total scaled uncertainty budget, the minimum number of periods in which one would like the demand to be protected against uncertainty, and the minimum scaled protection level per … Read more
Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches
Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design … Read more
An approximation algorithm for the partial covering 0-1 integer program
The partial covering 0-1 integer program (PCIP) is a relaxed problem of the covering 0-1 integer program (CIP) such that some fixed number of constraints may not be satisfied. This type of relaxation is also discussed in the partial set multi-cover problem (PSMCP) and the partial set cover problem (PSCP). In this paper, we propose … Read more
Geometric descent method for convex composite minimization
In this paper, we extend the geometric descent method recently proposed by Bubeck, Lee and Singh to tackle nonsmooth and strongly convex composite problems. We prove that our proposed algorithm, dubbed geometric proximal gradient method (GeoPG), converges with a linear rate $(1-1/\sqrt{\kappa})$ and thus achieves the optimal rate among first-order methods, where $\kappa$ is the … Read more
The (minimum) rank of typical fooling-set matrices
A fooling-set matrix is a square matrix with nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. ’96 proved that the rank of such a matrix is at least $\sqrt n$, for a matrix of order $n$. We ask for the typical minimum rank of a … Read more
Fooling Sets and the Spanning Tree Polytope
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with n nodes. The best known lower bound is \Omega(n^2), the best known upper bound is O(n^3). In this note … Read more
Complexity Analysis of a Trust Funnel Algorithm for Equality Constrained Optimization
A method is proposed for solving equality constrained nonlinear optimization problems involving twice continuously differentiable functions. The method employs a trust funnel approach consisting of two phases: a first phase to locate an $\epsilon$-feasible point and a second phase to seek optimality while maintaining at least $\epsilon$-feasibility. A two-phase approach of this kind based on … Read more
The Selective Traveling Salesman Problem with Draught Limits
This paper introduces the Selective Traveling Salesman Problem with Draught Limits, an extension of Traveling Salesman Problem with Draught Limits, wherein the goal is to design maximal profit tour respecting draught limit constraints of the visited ports. We propose a mixed integer linear programming formulation for this problem. The proposed mixed integer program is used … Read more
An extension of Chubanov’s algorithm to symmetric cones
In this work we present an extension of Chubanov’s algorithm to the case of homogeneous feasibility problems over a symmetric cone K. As in Chubanov’s method for linear feasibility problems, the algorithm consists of a basic procedure and a step where the solutions are confined to the intersection of a half-space and K. Following an … Read more