We formulate a risk-averse multi-stage stochastic program using conditional value at risk as the risk measure. The underlying random process is assumed to be stage-wise independent, and a stochastic dual dynamic programming (SDDP) algorithm is applied. We discuss the poor performance of the standard upper bound estimator in the risk-averse setting and propose a new … Read more
We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a “simple” … Read more
This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance … Read more
In this paper we introduce the s-monotone index selection rules for the well-known crisscross method for solving the linear complementarity problem (LCP). Most LCP solution methods require a priori information about the properties of the input matrix. One of the most general matrix properties often required for finiteness of the pivot algorithms (or polynomial complexity … Read more
Several variations of index selection rules for simplex type algorithms for linear programming, like the Last-In-First-Out or the Most-Often-Selected-Variable are rules not only theoretically finite, but also provide significant flexibility in choosing a pivot element. Based on an implementation of the primal simplex and the monotonic build-up (MBU) simplex method, the practical benefit of the … Read more
This paper studies an extended trust region subproblem (eTRS)in which the trust region intersects the unit ball with m linear inequality constraints. When m=0, m=1, or m=2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial … Read more
Power grid vulnerability is a major concern of modern society, and its protection problem is often formulated as a tri-level defender-attacker-defender model. However, this tri-level problem is compu- tationally challenging. In this paper, we design and implement a Column-and-Constraint Generation algorithm to derive its optimal solutions. Numerical results on an IEEE system show that: (i) … Read more
Users are often faced with the problem of finding complementary items that together achieve a single common goal (e.g., a starter kit for a novice astronomer, a collection of question/answers related to low-carb nutrition, a set of places to visit on holidays). In this paper, we argue that for some application scenarios returning item bundles … Read more
We show that there are 0-1 and unbounded knapsack polytopes with super-polynomial extension complexity. More specifically, for each n in N we exhibit 0-1 and unbounded knapsack polyhedra in dimension n with extension complexity \Omega(2^\sqrt{n}). Article Download View A NOTE ON THE EXTENSION COMPLEXITY OF THE KNAPSACK POLYTOPE
We address the following generalization $P$ of the Lowner-John’s ellipsoid problem. Given a (non necessarily convex) compact set $K\subset R^n$ and an even integer $d, find an homogeneous polynomial $g$ of degree $d$ such that $K\subset G:=\{x:g(x)\leq1\}$ and $G$ has minimum volume among all such sets. We show that $P$ is a convex optimization problem … Read more