-
作者：Lamm, Michael; Lu, Shu; Budhiraja, Amarjit
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine; University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：Stochastic variational inequalities (SVIs) provide a means for modeling various optimization and equilibrium problems where data are subject to uncertainty. Often the SVI cannot be solved directly and requires a numerical approximation. This paper considers the use of a sample average approximation and proposes three methods for computing confidence intervals for components of the true solution. The first two methods use an indirect approach that requires initially computing asymptotically exa...
-
作者：Rockafellar, R. Tyrrell; Wets, Roger J-B
作者单位：University of Washington; University of Washington Seattle; University of California System; University of California Davis
摘要：Variational inequality modeling, analysis and computations are important for many applications, but much of the subject has been developed in a deterministic setting with no uncertainty in a problem's data. In recent years research has proceeded on a track to incorporate stochasticity in one way or another. However, the main focus has been on rather limited ideas of what a stochastic variational inequality might be. Because variational inequalities are especially tuned to capturing conditions ...
-
作者：Queyranne, Maurice; Wolsey, Laurence A.
作者单位：Universite Catholique Louvain; University of British Columbia
摘要：Switching machines on and off is an important aspect of unit commitment problems and production planning problems, among others. Here we study tight mixed integer programming formulations for two aspects of such problems: bounded length on- and off-intervals, and interval-dependent start-ups. The problem with both these aspects admits a general Dynamic Programming (shortest path) formulation which leads to a tight extended formulation with a number of binary variables that is quadratic in the ...
-
作者：Wolsey, Laurence A.
摘要：For an n-period uncapacitated lot-sizing problem with stock upper bounds, stock fixed costs, stock overload and backlogging, we present a tight extended shortest path formulation of the convex hull of solutions with O variables and constraints, also giving an O algorithm for the problem. This corrects and extends a formulation in Section 4.4 of our article Lot-sizing with production and delivery time windows, Mathematical Programming A, 107:471-489, 2006, for the problem with just stock upper ...
-
作者：Wang, Yiming; Buchanan, Austin; Butenko, Sergiy
作者单位：Texas A&M University System; Texas A&M University College Station; Oklahoma State University System; Oklahoma State University - Stillwater
摘要：In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two nontrivial classes of valid inequalities. The first are the a, b-separator inequalities, which have been successfully used to enforce connectivity in previous computational...
-
作者：Bauschke, Heinz H.; Moursi, Walaa M.
作者单位：University of British Columbia; Egyptian Knowledge Bank (EKB); Mansoura University
摘要：The Douglas-Rachford algorithm is a very popular splitting technique for finding a zero of the sum of two maximally monotone operators. The behaviour of the algorithm remains mysterious in the general inconsistent case, i.e., when the sum problem has no zeros. However, more than a decade ago, it was shown that in the (possibly inconsistent) convex feasibility setting, the shadow sequence remains bounded and its weak cluster points solve a best approximation problem. In this paper, we advance t...
-
作者：Azar, Yossi; Hoefer, Martin; Maor, Idan; Reiffenhaeuser, Rebecca; Voecking, Berthold
作者单位：Tel Aviv University; Max Planck Society; Saarland University; RWTH Aachen University
摘要：A powerful algorithmic technique for truthful mechanism design is the maximal-in-distributional-range (MIDR) paradigm. Unfortunately, many such algorithms use heavy algorithmic machinery, e.g., the ellipsoid method and (approximate) solution of convex programs. In this paper, we present a correlated rounding technique for designing mechanisms that are truthful in expectation. It is elementary and can be implemented quickly. The main property we rely on is that the domain offers fractional opti...
-
作者：Feizollahi, Mohammad Javad; Ahmed, Shabbir; Sun, Andy
作者单位：University System of Georgia; Georgia State University; University System of Georgia; Georgia Institute of Technology
摘要：We investigate the augmented Lagrangian dual (ALD) for mixed integer linear programming (MIP) problems. ALD modifies the classical Lagrangian dual by appending a nonlinear penalty function on the violation of the dualized constraints in order to reduce the duality gap. We first provide a primal characterization for ALD for MIPs and prove that ALD is able to asymptotically achieve zero duality gap when the weight on the penalty function is allowed to go to infinity. This provides an alternative...
-
作者：Bianchi, S.; Escalante, M.; Nasini, G.; Tuncel, L.
作者单位：National University of Rosario; University of Waterloo
摘要：We study the Lovasz-Schrijver lift-and-project operator () based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the -operator generates the stable set polytope in one step has been open since 1990. We call these graphs -perfect. In the current contribution, we pursue a full combinatorial characterization of -perfect graphs and make progress towards s...
-
作者：Lee, Troy; Wei, Zhaohui; de Wolf, Ronald
作者单位：Nanyang Technological University; National University of Singapore; Centrum Wiskunde & Informatica (CWI); University of Amsterdam
摘要：Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on it...
