-
作者：Zheng, Xiaojin; Sun, Xiaoling; Li, Duan; Xia, Yong
作者单位：Fudan University; Chinese University of Hong Kong; Beihang University
摘要：We investigate in this paper the Lagrangian duality properties of linear equality constrained binary quadratic programming. We derive an underestimation of the duality gap between the primal problem and its Lagrangian dual or SDP relaxation, using the distance from the set of binary integer points to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. Alternative Lagrangian dual schemes via the exact penalty and the...
-
作者：Bertsimas, Dimitris; Iancu, Dan A.; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：In this paper, we prove the optimality of disturbance-affine control policies in the context of one-dimensional, constrained, multistage robust optimization. Our results cover the finite-horizon case, with minimax (worst-case) objective, and convex state costs plus linear control costs. We develop a new proof methodology, which explores the relationship between the geometrical properties of the feasible set of solutions and the structure of the objective function. Apart from providing an elega...
-
作者：Basu, Amitabh; Conforti, Michele; Cornuejols, Gerard; Zambelli, Giacomo
作者单位：Carnegie Mellon University; University of Padua
摘要：We consider a model that arises in integer programming and show that all irredundant inequalities are obtained from maximal lattice-free convex sets in an affine subspace. We also show that these sets are polyhedra. The latter result extends a theorem of Lovasz characterizing maximal lattice-free convex sets in R-n.
-
作者：Cai, Ning; Chen, Nan; Wan, Xiangwei
作者单位：Hong Kong University of Science & Technology; Chinese University of Hong Kong
摘要：In this paper, we provide Laplace transform-based analytical solutions to pricing problems of various occupation-time-related derivatives such as step options, corridor options, and quantile options under Kou's double exponential jump diffusion model. These transforms can be inverted numerically via the Euler Laplace inversion algorithm, and the numerical results illustrate that our pricing methods are accurate and efficient. The analytical solutions can be obtained primarily because we derive...
-
作者：Dai, J. G.; He, Shuangchi
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We study G/G/n + GI queues in which customer patience times are independent, identically distributed following a general distribution. When a customer's waiting time in queue exceeds his patience time, the customer abandons the system without service. For the performance of such a system, we focus on the abandonment process and the queue length process. We prove that under some conditions, a deterministic relationship between the two stochastic processes holds asymptotically under the diffusio...
-
作者：Dupuis, Paul; Leder, Kevin; Wang, Hui
作者单位：Brown University; Columbia University
摘要：This paper considers buffer over flow probabilities for stable queueing systems with one server and different classes of arrivals. The service priority is given to the class of customers whose current weighted queue size is the largest (weighted-serve-the-longest-queue policy). We explicitly identify the exponential decay rate for the rare-event probabilities of interest and construct asymptotically optimal importance-sampling schemes for simulation.
-
作者：Chan, Carri W.; Farias, Vivek F.
作者单位：Stanford University; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：This paper presents a general class of dynamic stochastic optimization problems we refer to as stochastic depletion problems. A number of challenging dynamic optimization problems of practical interest are stochastic depletion problems. Optimal solutions for such problems are difficult to obtain, both from a pragmatic computational perspective as well as from a theoretical perspective. As such, simple heuristics are desirable. We isolate two simple properties that, if satisfied by a problem wi...
-
作者：Klein, Manuel
作者单位：INSEAD Business School
摘要：In a recent contribution to this journal, Decamps et al. [Decamps, J.-P., T. Mariotti, S. Villeneuve. 2005. Investment timing under incomplete information. Math. Oper. Res. 30(2) 472-500] analyze the decision of when to invest in a project whose value is perfectly observable but driven by a parameter that is unknown to the decision maker ex ante. Using filtering and martingale techniques, they find that (i) the decision maker always benefits from an uncertain drift relative to an average drift...
-
作者：Akan, Mustafa; Ata, Baris
作者单位：Carnegie Mellon University; Northwestern University
摘要：We consider a continuous-time, rate-based model of network revenue management. Under mild assumptions, we construct a simple epsilon- optimal bid-price control, which can be viewed as a perturbation of a bid-price control in the classical sense [Williamson, E. L. 1992. Airline network seat control. Ph.D. thesis, MIT, Cambridge, MA]. We show that the associated bid-price process forms a martingale and the corresponding booking controls converge in an appropriate sense to an optimal control as e...
-
作者：Nagarajan, Viswanath; Sviridenko, Maxim
作者单位：Carnegie Mellon University; International Business Machines (IBM); IBM USA
摘要：In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,..., m. In the permutation flow shop problem, it is also required that each machine process the set of all jobs in the same order. Formally, given n jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs sigma: [n] -> [n] that minimizes the maximum job completion time (makespan) of the schedule resulting f...
