-
作者：Sun, DF; Sun, J
作者单位：National University of Singapore; National University of Singapore; National University of Singapore
摘要：We show that the Fischer-Burmeister complementarity functions, associated to the semidefinite cone (SDC) and the second order cone (SOC), respectively, are strongly semismooth everywhere. Interestingly enough, the proof relys on a relationship between the singular value decomposition of a nonsymmetric matrix and the spectral decomposition of a symmetric matrix.
-
作者：Seiden, SS; Woeginger, GJ
作者单位：Louisiana State University System; Louisiana State University; Eindhoven University of Technology
摘要：In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k = 2 stages cannot guara...
-
作者：Dai, YH; Fletcher, R
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：The Barzilai-Borwein (BB) gradient method, and some other new gradient methods have shown themselves to be competitive with conjugate gradient methods for solving large dimension nonlinear unconstrained optimization problems. Little is known about the asymptotic behaviour, even when applied to n-dimensional quadratic functions, except in the case that n = 2. We show in the quadratic case how it is possible to compute this asymptotic behaviour, and observe that as n increases there is a transit...
-
作者：Andersen, K; Cornuéjols, G; Li, YJ
作者单位：Carnegie Mellon University; Purdue University System; Purdue University
摘要：In the seventies, Balas introduced intersection cuts for a Mixed Integer Linear Program (MILP), and showed that these cuts can be obtained by a closed form formula from a basis of the standard linear programming relaxation. In the early nineties, Cook, Kannan and Schrijver introduced the split closure of a MILP, and showed that the split closure is a polyhedron. In this paper, we show that the split closure can be obtained using only intersection cuts. We give two different proofs of this resu...
-
作者：Pritchard, G; Philpott, AB; Neame, PJ
作者单位：University of Auckland; University of Auckland; University of Technology Sydney
摘要：For a price-taking generator operating a hydro-electric reservoir in a pool electricity market, the optimal stack to offer in each trading period over a planning horizon can be computed using dynamic programming. However, the market trading period (usually 1 hour or less) may be much shorter than the inherent time scale of the reservoir (often many months). We devise a dynamic programming model for such situations in which each stage represents many trading periods. In this model, the decision...
-
作者：Meurdesoif, P
作者单位：Universite de Bordeaux
摘要：The Lovasz theta-number is a way to approximate the independence number of a graph, but also its chromatic number. We express the Lovasz bound as the continuous relaxation of a discrete Lovdsz theta-number which we derive from Karger et al.'s formulation, and which is equal to the chromatic number. We also give another relaxation a la Schrijver-McEliece, which is better than the Lovasz theta-number.
-
作者：Peña, J
作者单位：Carnegie Mellon University
摘要：We show that the block-structured distance to non-surjectivity of a set-valued sublinear mapping equals the reciprocal of a suitable block-structured norm of its inverse. This gives a natural generalization of the classical Eckart and Young identity for square invertible matrices.
-
作者：Koivu, M
作者单位：University of Helsinki
摘要：This paper studies the use of randomized Quasi-Monte Carlo methods (RQMC) in sample approximations of stochastic programs. In numerical integration, RQMC methods often substantially reduce the variance of sample approximations compared to Monte Carlo (MC). It seems thus natural to use RQMC methods in sample approximations of stochastic programs. It is shown, that RQMC methods produce epi-convergent approximations of the original problem. RQMC and MC methods are compared numerically in five dif...
-
作者：Vandenbussche, D; Nemhauser, GL
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology
摘要：By reformulating quadratic programs using necessary optimality conditions, we obtain a linear program with complementarity constraints. For the case where the only constraints are bounds on the variables, we study a relaxation based on a subset of the optimality conditions. By characterizing its convex hull, we obtain a large class of valid inequalities. These inequalities are used in a branch-and-cut scheme, see [13].
-
作者：Anjos, MF
作者单位：University of Waterloo
摘要：The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial ...
