-
作者：Pap, Gyula
作者单位：Eotvos Lorand University
摘要：A perfect 2-matching of a graph is a vector assigning values 0,1, or 2 to the edges such that the sum of values of edges incident with any node is equal to 2. For restricted perfect 2-matchings, we are also given a collection of allowed odd cycles, and restrict ourselves to those perfect 2-matchings the support of which contains no odd cycle not in this collection. Given a graph and a collection of allowed odd cycles, we provide a TDI description of the convex hull of restricted perfect 2-matc...
-
作者：Baldacci, Roberto; Mingozzi, Aristide
作者单位：University of Bologna; University of Bologna
摘要：This paper presents a unified exact method for solving an extended model of the well-known Capacitated Vehicle Routing Problem (CVRP), called the Heterogenous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles having different capacities, routing and fixed costs is used to supply a set of customers. The HVRP model considered in this paper contains as special cases: the Single Depot CVRP, all variants of the HVRP presented in the literature, the Site-Dependent Vehicle Routing Probl...
-
作者：Qi, Liqun; Wang, Fei; Wang, Yiju
作者单位：Hong Kong Polytechnic University; Hunan City University; Qufu Normal University
摘要：As a global polynomial optimization problem, the best rank-one approximation to higher order tensors has extensive engineering and statistical applications. Different from traditional optimization solution methods, in this paper, we propose some Z-eigenvalue methods for solving this problem. We first propose a direct Z-eigenvalue method for this problem when the dimension is two. In multidimensional case, by a conventional descent optimization method, we may find a local minimizer of this prob...
-
作者：Faigle, Ulrich; Fujishige, Satoru
作者单位：University of Cologne; Kyoto University
摘要：We present a general model for set systems to be independence families with respect to set families which determine classes of proper weight functions on a ground set. Within this model, matroids arise from a natural subclass and can be characterized by the optimality of the greedy algorithm. This model includes and extends many of the models for generalized matroid-type greedy algorithms proposed in the literature and, in particular, integral polymatroids. We discuss the relationship between ...
-
作者：Ito, Kazufumi; Kunisch, Karl
作者单位：University of Graz; North Carolina State University
摘要：This paper addresses the globalization of the semi-smooth Newton method for non-smooth equations F(x) = 0 in R-m with applications to complementarity and discretized l(1)-regularization problems. Assuming semi-smoothness it is shown that super-linearly convergent Newton methods can be globalized, if appropriate descent directions are used for the merit function |F(x)|(2). Special attention is paid to directions obtained from the primal-dual active set strategy.
-
作者：Orlin, James B.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We consider the problem of minimizing a submodular function f defined on a set V with n elements. We give a combinatorial algorithm that runs in O(n(5)EO + n(6)) time, where EO is the time to evaluate f (S) for some S subset of V. This improves the previous best strongly polynomial running time by more than a factor of n. We also extend our result to ring families.
-
作者：Belloni, Alexandre; Sagastizabal, Claudia
作者单位：Duke University; Eletrobras Cepel
摘要：Lagrangian relaxation is a popular technique to solve difficult optimization problems. However, the applicability of this technique depends on having a relatively low number of hard constraints to dualize. When there are many hard constraints, it may be preferable to relax them dynamically, according to some rule depending on which multipliers are active. From the dual point of view, this approach yields multipliers with varying dimensions and a dual objective function that changes along itera...
-
作者：Anitescu, Mihai; Negrut, Dan; Zapol, Peter; El-Azab, Anter
作者单位：United States Department of Energy (DOE); Argonne National Laboratory; United States Department of Energy (DOE); Argonne National Laboratory; United States Department of Energy (DOE); Argonne National Laboratory; State University System of Florida; Florida State University
摘要：The paper investigates model reduction techniques that are based on a nonlocal quasi-continuum-like approach. These techniques reduce a large optimization problem to either a system of nonlinear equations or another optimization problem that are expressed in a smaller number of degrees of freedom. The reduction is based on the observation that many of the components of the solution of the original optimization problem are well approximated by certain interpolation operators with respect to a r...
-
作者：Heitsch, Holger; Roemisch, Werner
作者单位：Humboldt University of Berlin
摘要：An important issue for solving multistage stochastic programs consists in the approximate representation of the (multivariate) stochastic input process in the form of a scenario tree. In this paper, we develop (stability) theory-based heuristics for generating scenario trees out of an initial set of scenarios. They are based on forward or backward algorithms for tree generation consisting of recursive scenario reduction and bundling steps. Conditions are established implying closeness of optim...
-
作者：Giandomenico, Monia; Letchford, Adam N.; Rossi, Fabrizio; Smriglio, Stefano
作者单位：University of L'Aquila; Lancaster University
摘要：Although the lift-and-project operators of Lovasz and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues...
