-
作者：Sherali, HD; Smith, JC
作者单位：Virginia Polytechnic Institute & State University; University of Arizona
摘要：The traditional vertex packing problem defined on an undirected graph identifies the largest weighted independent set of nodes, that is, a set of nodes whose induced subgraph contains no edges. In this paper, we examine a generalized vertex packing problem (GVP-k) in which k violations to the independent set restriction are permitted, whereby k edges may exist within the subgraph induced by the chosen set of nodes. A particular context in which such problems arise is in the national airspace p...
-
作者：Wolsey, LA
作者单位：Universite Catholique Louvain
摘要：We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also sh...
-
作者：Cornuéjols, G; Lemaréchal, C
作者单位：Carnegie Mellon University; Aix-Marseille Universite; Inria
摘要：We treat with tools from convex analysis the general problem of cutting planes, separating a point from a (closed convex) set P. Crucial for this is the computation of extreme points in the so-called reverse polar set, introduced by E. Balas in 1979. In the polyhedral case, this enables the computation of cuts that define facets of P. We exhibit three (equivalent) optimization problems to compute such extreme points; one of them corresponds to selecting a specific normalization to generate cut...
-
作者：Yin, HX; Ling, C; Qi, LQ
作者单位：Chinese Academy of Sciences; University of Chinese Academy of Sciences, CAS; Zhejiang University of Finance & Economics; Hong Kong Polytechnic University
摘要：In the paper, we prove the Holder continuous property of the Jacobian of the function generated from the dual of the power spectrum estimation problem. It follows that the convergence of the Newton method for the problem is at least of order 1 + 2/2m, where m is the order of the trigonometric bases. This result theoretically confirms the numerical observation by Potter (1990) and Cole and Goodrich (1993).
-
作者：Guérin, J; Marcotte, P; Savard, G
作者单位：Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Universite de Montreal; Universite de Montreal; Polytechnique Montreal
摘要：Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case.
-
作者：Dyer, M; Stougie, L
作者单位：University of Leeds; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
摘要：Stochastic programming is the subfield of mathematical programming that considers optimization in the presence of uncertainty. During the last four decades a vast quantity of literature on the subject has appeared. Developments in the theory of computational complexity allow us to establish the theoretical complexity of a variety of stochastic programming problems studied in this literature. Under the assumption that the stochastic parameters are independently distributed, we show that two-sta...
-
作者：Ahmed, S
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criterion. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk objective, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various mean-risk objective functions in addressing risk in stochastic programming models. We prove that the classical mean-variance criteri...
-
作者：Dai, YH; Fletcher, R
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; University of Dundee
摘要：There are many applications related to singly linearly constrained quadratic programs subjected to upper and lower bounds. In this paper, a new algorithm based on secant approximation is provided for the case in which the Hessian matrix is diagonal and positive definite. To deal with the general case where the Hessian is not diagonal, a new efficient projected gradient algorithm is proposed. The basic features of the projected gradient algorithm are: 1) a new formula is used for the stepsize; ...
-
作者：Fukasawa, R; Longo, H; Lysgaard, J; de Aragao, MP; Reis, M; Uchoa, E; Werneck, RF
作者单位：Universidade Federal Fluminense; Universidade Federal de Goias; Aarhus University; Pontificia Universidade Catolica do Rio de Janeiro; Princeton University
摘要：The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints th...
-
作者：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...
