-
作者：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.
-
作者：Stolpe, M; Kawamoto, A
作者单位：Technical University of Denmark
摘要：This paper considers an optimization model and a solution method for the design of two-dimensional mechanical mechanisms. The mechanism design problem is modeled as a nonconvex mixed integer program which allows the optimal topology and geometry of the mechanism to be determined simultaneously. The underlying mechanical analysis model is based on a truss representation allowing for large displacements. For mechanisms undergoing large displacements elastic stability is of major concern. We deri...
-
作者：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].
-
作者：Puerto, J; Tamir, A
作者单位：University of Sevilla; Tel Aviv University
摘要：In this paper we consider the location of a tree-shaped facility Son a tree network, using the ordered median function of the weighted distances to represent the total transportation cost objective. This function unifies and generalizes the most common criteria used in location modeling, e.g., median and center. If there are n demand points at the nodes of the tree T = (V, E), this function is characterized by a sequence of reals, Lambda = (lambda(1),...,lambda(n)), satisfying lambda(1) >= lam...
-
作者：Frangioni, A; Lodi, A; Rinaldi, G
作者单位：University of Pisa; University of Bologna; Consiglio Nazionale delle Ricerche (CNR); Istituto di Analisi dei Sistemi ed Informatica Antonio Ruberti (IASI-CNR)
摘要：The semimetric polytope is an important polyhedral structure lying at the heart of several hard combinatorial problems. Therefore, linear optimization over the semimetric polytope is crucial for a number of relevant applications. Building on some recent polyhedral and algorithmic results about a related polyhedron, the rooted semimetric polytope, we develop and test several approaches, based over Lagrangian relaxation and application of Non Differentiable Optimization algorithms, for linear op...
-
作者：Cánovas, MJ; López, MA; Parra, J; Toledo, FJ
作者单位：Universidad Miguel Hernandez de Elche; Universitat d'Alacant
摘要：In this paper we consider the parameter space of all the linear inequality systems, in the n-dimensional Euclidean space, with a fixed and arbitrary (possibly infinite) index set. This parameter space is endowed with the topology of the uniform convergence of the coefficient vectors by means of an extended distance. Some authors, in a different context in which the index set is finite and, accordingly, the coefficients are bounded, consider the boundary of the set of consistent systems as the ...
-
作者：Filippi, C; Agnetis, A
作者单位：University of Padua; University of Siena
摘要：The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C-2 bins more than the optimal solution, i.e., an algorithm that is asymptoti...
-
作者：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 ...
-
作者：Vandenbussche, D; Nemhauser, GL
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology
摘要：We present the implementation of a branch-and-cut algorithm for bound constrained nonconvex quadratic programs. We use a class of inequalities developed in [12] as cutting planes. We present various branching strategies and compare the algorithm to several other methods to demonstrate its effectiveness.
