-
作者：Sherali, Hanif D.; Zhu, Xiaomei
作者单位：Virginia Polytechnic Institute & State University
摘要：In this paper, we propose a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having mixed-integer first- and second-stage variables. A modified Benders' decomposition method is developed, where the Benders' subproblems define lower bounding second-stage value functions of the first-stage variables that are derived by constructing a certain partial convex hull representation of the two-stage solution space. This partial convex hull is sequentially ...
-
作者：Van der Laan, G.; Talman, D. A. J. J.; Yang, Z.
作者单位：Vrije Universiteit Amsterdam; Tinbergen Institute; Vrije Universiteit Amsterdam; Tilburg University; Tilburg University; Yokohama National University
摘要：In this paper we present two theorems on the existence of a discrete zero point of a function from the n-dimensional integer lattice Z(n) to the n-dimensional Euclidean space R-n. The theorems differ in their boundary conditions. For both theorems we give a proof using a combinatorial lemma and present a constructive proof based on a simplicial algorithm that finds a discrete zero point within a finite number of steps.
-
作者：d'Aspremont, A; El Ghaoui, L
作者单位：Princeton University; University of California System; University of California Berkeley
摘要：We consider the problem of computing upper and lower bounds on the price of an European basket call option, given prices on other similar options. Although this problem is hard to solve exactly in the general case, we show that in some instances the upper and lower bounds can be computed via simple closed-form expressions, or linear programs. We also introduce an efficient linear programming relaxation of the general problem based on an integral transform interpretation of the call price funct...
-
作者：Arora, S; Karakostas, G
作者单位：Princeton University; McMaster University
摘要：For any epsilon > 0 we give a (2 + epsilon)-approximation algorithm for the problem of finding a minimum tree spanning any k vertices in a graph (k-MST), improving a 3-approximation algorithm by Garg [10]. As in [10] the algorithm extends to a (2 + epsilon)-approximation algorithm for the minimum tour that visits any k vertices, provided the edge costs satisfy the triangle inequality.
-
作者：Nie, JW; Demmel, J; Sturmfels, B
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：A method is proposed for finding the global minimum of a multivariate polynomial via sum of squares (SOS) relaxation over its gradient variety. That variety consists of all points where the gradient is zero and it need not be finite. A polynomial which is nonnegative on its gradient variety is shown to be SOS modulo its gradient ideal, provided the gradient ideal is radical or the polynomial is strictly positive on the real gradient variety. This opens up the possibility of solving previously ...
-
作者：Bertsimas, D; Sim, M
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); National University of Singapore
摘要：In earlier proposals, the robust counterpart of conic optimization problems exhibits a lateral increase in complexity, i.e., robust linear programming problems (LPs) become second order cone problems (SOCPs), robust SOCPs become semidefinite programming problems (SDPs), and robust SDPs become NP-hard. We propose a relaxed robust counterpart for general conic optimization problems that (a) preserves the computational tractability of the nominal problem; specifically the robust conic optimizatio...
-
作者：Scherer, CW; Hol, CWJ
作者单位：Delft University of Technology
摘要：We consider robust semi-definite programs which depend polynomially or rationally on some uncertain parameter that is only known to be contained in a set with a polynomial matrix inequality description. On the basis of matrix sum-of-squares decompositions, we suggest a systematic procedure to construct a family of linear matrix inequality relaxations for computing upper bounds on the optimal value of the corresponding robust counterpart. With a novel matrix-version of Putinar's sum-of-squares ...
-
作者：De Franceschi, R; Fischetti, M; Toth, P
作者单位：University of Padua; University of Bologna
摘要：In this paper we address the Distance-Constrained Capacitated Vehicle Routing Problem (DCVRP), where k minimum-cost routes through a central depot have to be constructed so as to cover all customers while satisfying, for each route, both a capacity and a total-distance-travelled limit. Our starting point is the following refinement procedure proposed in 1981 by Sarvanov and Doroshko for the pure Travelling Salesman Problem (TSP): given a starting tour, (a) remove all the nodes in even position...
-
作者：Shigeno, M
作者单位：University of Tsukuba
摘要：This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem ...
-
作者：Griva, I; Polyak, RA
作者单位：George Mason University; George Mason University; George Mason University
摘要：In this paper we developed a general primal-dual nonlinear rescaling method with dynamic scaling parameter update (PDNRD) for convex optimization. We proved the global convergence, established 1.5-Q-superlinear rate of convergence under the standard second order optimality conditions. The PDNRD was numerically implemented and tested on a number of nonlinear problems from COPS and CUTE sets. We present numerical results, which strongly corroborate the theory.
