Mathematical Programming

最新文章

• Tractable approximations to robust conic optimization problems AI翻译
  作者：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...
• Matrix sum-of-squares relaxations for robust semi-definite programs AI翻译
  作者：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 ...
• A new ILP-based refinement heuristic for Vehicle Routing Problems AI翻译
  作者：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...
• Maximum network flows with concave gains AI翻译
  作者：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 ...
• Primal-dual nonlinear rescaling method with dynamic scaling parameter update AI翻译
  作者：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.
• Robust optimal feedback for terminal linear-quadratic control problems under disturbances AI翻译
  作者：Kostyukova, O; Kostina, E
  作者单位：National Academy of Sciences of Belarus (NASB); Institute of Mathematics of the National Academy of Sciences of Belarus; Ruprecht Karls University Heidelberg
  摘要：We consider a linear dynamic system in the presence of an unknown but bounded perturbation and study how to control the system in order to get into a prescribed neighborhood of a zero at a given final moment. The quality of a control is estimated by the quadratic functional. We define optimal guaranteed program controls as controls that are allowed to be corrected at one intermediate time moment. We show that an infinite dimensional problem of constructing such controls is equivalent to a spec...
• Assessing solution quality in stochastic programs AI翻译
  作者：Bayraksan, Guezin; Morton, David P.
  作者单位：University of Arizona; University of Texas System; University of Texas Austin
  摘要：Determining whether a solution is of high quality (optimal or near optimal) is fundamental in optimization theory and algorithms. In this paper, we develop Monte Carlo sampling-based procedures for assessing solution quality in stochastic programs. Quality is defined via the optimality gap and our procedures' output is a confidence interval on this gap. We review a multiple-replications procedure that requires solution of, say, 30 optimization problems and then, we present a result that justif...
• Simple integer recourse models: convexity and convex approximations AI翻译
  作者：Klein Haneveld, Willem K.; Stougie, Leen; van der Vlerk, Maarten H.
  作者单位：University of Groningen; Eindhoven University of Technology; Centrum Wiskunde & Informatica (CWI)
  摘要：We consider the objective function of a simple recourse problem with fixed technology matrix and integer second-stage variables. Separability due to the simple recourse structure allows to study a one-dimensional version instead. Based on an explicit formula for the objective function, we derive a complete description of the class of probability density functions such that the objective function is convex. This result is also stated in terms of random variables. Next, we present a class of con...
• Hedging uncertainty: Approximation algorithms for stochastic optimization problems AI翻译
  作者：Ravi, R.; Sinha, Amitabh
  作者单位：Carnegie Mellon University; University of Michigan System; University of Michigan
  摘要：We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the graph-theoretic (shortest path, vertex cover, facility location) to set-theoretic (set cover, bin packing), and contain representatives with different approximation ratios. The approximation ratio of the stochastic variant of a typical problem is found to be of the same order of magnitude as its determini...
• A constraint generation algorithm for large scale linear programs using multiple-points separation AI翻译
  作者：Ben-Ameur, W; Neto, J
  作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom SudParis
  摘要：In order to solve linear programs with a large number of constraints, constraint generation techniques are often used. In these algorithms, a relaxation of the formulation containing only a subset of the constraints is first solved. Then a separation procedure is called which adds to the relaxation any inequality of the formulation that is violated by the current solution. The process is iterated until no violated inequality can be found. In this paper, we present a separation procedure that u...