-
作者：Addi, Khalid; Brogliato, B.; Goeleven, D.
作者单位：University of La Reunion; Inria
摘要：The main object of this paper is to present a general mathematical theory applicable to the study of a large class of linear variational inequalities arising in electronics. Our approach uses recession tools so as to define a new class of problems that we call semi-complementarity problems. Then we show that the study of semi-complementarity problems can be used to prove new qualitative results applicable to the study of linear variational inequalities of the second kind.
-
作者：Alfakih, A. Y.
作者单位：University of Windsor
摘要：A bar framework G(p) in r-dimensional Euclidean space is a graph G on the vertices 1,2,...,n, where each vertex i is located at point p(i) in R-r. Given a framework G(p) in R-r, a problem of great interest is that of determining whether or not there exists another framework G(q), not obtained from G(p) by a rigid motion, such that parallel to q(i) - q(j)parallel to(2) = parallel to p(i) - p(j)parallel to(2) for each edge (i, j) of G. This problem is known as either the global rigidity problem ...
-
作者：Fabian, Csaba I.; Mitra, Gautam; Roman, Diana
作者单位：Brunel University; Eotvos Lorand University
摘要：Second-order stochastic dominance (SSD) is widely recognised as an important decision criterion in portfolio selection. Unfortunately, stochastic dominance models are known to be very demanding from a computational point of view. In this paper we consider two classes of models which use SSD as a choice criterion. The first, proposed by Dentcheva and RuszczyAski (J Bank Finance 30:433-451, 2006), uses a SSD constraint, which can be expressed as integrated chance constraints (ICCs). The second, ...
-
作者：Gollmer, Ralf; Gotzes, Uwe; Schultz, Ruediger
作者单位：University of Duisburg Essen
摘要：We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed-integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instan...
-
作者：Zhao, Wenhui; Posner, Marc E.
作者单位：Washington University (WUSTL); University System of Ohio; Ohio State University
摘要：The polyhedral structure of the K-median problem is examined. We present an extended formulation that is integral but grows exponentially with the number of nodes. Then, some extra variables are projected out. Based on the reduced formulation, we develop two basic properties for facets of K-median problem. By applying the two properties, we generalize two known classes of facets, de Vries facets and de Farias facets. The computational study illustrates that the generalization is significant.
-
作者：Chakrabarty, Deeparnab; Devanur, Nikhil R.; Vazirani, Vijay V.
作者单位：University of Waterloo; Microsoft; University System of Georgia; Georgia Institute of Technology
摘要：Determining the integrality gap of the bidirected cut relaxation for the metric Steiner tree problem, and exploiting it algorithmically, is a long-standing open problem. We use geometry to define an LP whose dual is equivalent to this relaxation. This opens up the possibility of using the primal-dual schema in a geometric setting for designing an algorithm for this problem. Using this approach, we obtain a 4/3 factor algorithm and integrality gap bound for the case of quasi-bipartite graphs; t...
-
作者：Geunes, Joseph; Levi, Retsef; Romeijn, H. Edwin; Shmoys, David B.
作者单位：Massachusetts Institute of Technology (MIT); State University System of Florida; University of Florida; University of Michigan System; University of Michigan; Cornell University; Cornell University
摘要：We propose generalizations of a broad class of traditional supply chain planning and logistics models that we call supply chain planning and logistics problems with market choice. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. In the first stage, one chooses a subset of markets and rejects the others. Once that market choice is made, one needs to construct a minimum-cost...
-
作者：Ma, Shiqian; Goldfarb, Donald; Chen, Lifeng
作者单位：Columbia University
摘要：The linearly constrained matrix rank minimization problem is widely applicable in many fields such as control, signal processing and system identification. The tightest convex relaxation of this problem is the linearly constrained nuclear norm minimization. Although the latter can be cast as a semidefinite programming problem, such an approach is computationally expensive to solve when the matrices are large. In this paper, we propose fixed point and Bregman iterative algorithms for solving th...
-
作者：Ge, Dongdong; Jiang, Xiaoye; Ye, Yinyu
作者单位：Shanghai Jiao Tong University; Stanford University; Stanford University
摘要：We discuss the L-p (0 <= p < 1) minimization problem arising from sparse solution construction and compressed sensing. For any fixed 0 < p < 1, we prove that finding the global minimal value of the problem is strongly NP-Hard, but computing a local minimizer of the problem can be done in polynomial time. We also develop an interior-point potential reduction algorithm with a provable complexity bound and demonstrate preliminary computational results of effectiveness of the algorithm.
-
作者：Dey, Santanu S.
作者单位：Universite Catholique Louvain
摘要：In this note, we present a simple geometric argument to determine a lower bound on the split rank of intersection cuts. As a first step of this argument, a polyhedral subset of the lattice-free convex set that is used to generate the intersection cut is constructed. We call this subset the restricted lattice-free set. It is then shown that [log(2)(l)] is a lower bound on the split rank of the intersection cut, where l is the number of integer points lying on the boundary of the restricted latt...
