2006

最新文章

• 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...
• Robust game theory AI翻译
  作者：Aghassi, M; Bertsimas, D
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
  摘要：We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our robust game'' model relaxes the assumptions of Harsanyi's Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call robust-optimization equilibrium,'' to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an inc...
• Polyhedra related to integer-convex polynomial systems AI翻译
  作者：Michaels, D; Weismantel, R
  作者单位：Otto von Guericke University
  摘要：This paper deals with the reformulation of a polynomial integer program. For deducing a linear integer relaxation of such a program a class of polyhedra that are associated with nonlinear functions is introduced. A characterization of the family of polynomials for which our approach leads to an equivalent linear integer program is given. Finally the family of so-called integer-convex polynomials is defined, and polyhedra related to such a polynomial are investigated.
• Valid inequalities based on simple mixed-integer sets AI翻译
  作者：Dash, S; Günlük, O
  作者单位：International Business Machines (IBM); IBM USA
  摘要：In this paper we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities two-step MIR inequalities as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice. The two-step MIR inequalities define facets of the master cyclic group polyhedron of Gomory (1969). In addition, they dominate the strong fractional cuts of Letchford and Lod...
• Solving a class of stochastic mixed-integer programs with branch and price AI翻译
  作者：Silva, Eduardo F.; Wood, R. Kevin
  作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
  摘要：We begin this paper by identifying a class of stochastic mixed-integer programs that have column-oriented formulations suitable for solution by a branch-and-price algorithm (B&P). We then survey a number of examples, and use a stochastic facility-location problem (SFLP) for a detailed demonstration of the relevant modeling and solution techniques. Computational results with a scenario representation of uncertain costs, demands and capacities show that B&P can be orders of magnitude faster than...
• On the gap between the quadratic integer programming problem and its semidefinite relaxation AI翻译
  作者：Malik, U; Jaimoukha, IM; Halikias, GD; Gungah, SK
  作者单位：Imperial College London; City St Georges, University of London
  摘要：Consider the semidefinite relaxation (SDR) of the quadratic integer program (QIP): gamma := max {x(T) Qx : x is an element of {-1, 1}(n)} <= min {trace(D) : D - Q greater than or similar to 0} =: (gamma) over bar where Q is a given symmetric matrix and D is diagonal. We consider the SDR gap (gamma) over bar gamma. We establish the uniqueness of the SDR solution and prove that gamma = (gamma) over bar if and only if gamma(r) := n(-1) max {x(T) VVT x : x is an element of {-1, 1}(n)} = 1 where V ...