-
作者：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...
-
作者：Perakis, G; Sood, A
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：We study a multi-period oligopolistic market for a single perishable product with fixed inventory. Our goal is to address the competitive aspect of the problem together with demand uncertainty using ideas from robust optimization and variational inequalities. The demand function for each seller has some associated uncertainty and we assume that the sellers would like to adopt a policy that is robust to adverse uncertain circumstances. We believe this is the first paper that uses robust optimiz...
-
作者：Cameron, K; Hell, P
作者单位：Wilfrid Laurier University; Simon Fraser University
摘要：Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocompa...
-
作者：Bertsimas, Dimitris; Natarajan, Karthik; Teo, Chung-Piaw
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); National University of Singapore; National University of Singapore
摘要：An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the netw...
-
作者：Jibetean, D; de Klerk, E
作者单位：Eindhoven University of Technology; Tilburg University
摘要：We consider the problem of global minimization of rational functions on R-n (unconstrained case), and on an open, connected, semi-algebraic subset of R-n, or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [6]. This extends the analogous results by Nesterov [13] for global minimization of univa...
-
作者：Yamashita, Hideaki; Ishizuka, Yo; Suzuki, Shigemichi
作者单位：Tokyo Metropolitan University; Sophia University; Chiba Institute of Technology
摘要：We analyze alternating traffic crossing a narrow one-lane bridge on a two-lane road. Once a car begins to cross the bridge in one direction, arriving cars from the other direction must wait, forming a queue, until all the arrivals in the first direction finish crossing the bridge. Such a situation can often be observed when road-maintenance work is being carried out. Cars are assumed to arrive at the queues according to independent Poisson processes and to cross the bridge in a constant time. ...
-
作者：Atamtuerk, Alper
作者单位：University of California System; University of California Berkeley
摘要：We introduce strong formulations for robust mixed 0-1 programming with uncertain objective coefficients. We focus on a polytopic uncertainty set described by a ``budget constraint'' for allowed uncertainty in the objective coefficients. We show that for a robust 0-1 problem, there is an alpha-tight linear programming formulation with size polynomial in the size of an alpha-tight linear programming formulation for the nominal 0-1 problem. We give extensions to robust mixed 0-1 programming and p...
-
作者：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; ...
-
作者：Chen, X; Qi, HD
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Southampton
摘要：We introduce a Cartesian P-property for linear transformations between the space of symmetric matrices and present its applications to the semidefinite linear complementarity problem (SDLCP). With this Cartesian P-property, we show that the SDLCP has GUS-property (i.e., globally unique solvability), and the solution map of the SDLCP is locally Lipschitzian with respect to input data. Our Cartesian P-property strengthens the corresponding P-properties of Gowda and Song [15] and allows us to ext...
-
作者：Dash, S; Günlük, O
作者单位：International Business Machines (IBM); IBM USA
摘要：We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in Dash and Gunluk (2003). We first analyze and extend the shooting experiment described in Gomory, Johnson and Evans. We...
