-
作者：Stein, Oliver
作者单位：Helmholtz Association; Karlsruhe Institute of Technology
摘要：We present a new smoothing approach for mathematical programs with complementarity constraints, based on the orthogonal projection of a smooth manifold. We study regularity of the lifted feasible set and, since the corresponding optimality conditions are inherently degenerate, introduce a regularization approach involving a novel concept of tilting stability. A correspondence between the C-index in the original problem and the quadratic index in the lifted problem is shown. In particular, a lo...
-
作者：Magos, D.; Mourtos, I.; Appa, G.
作者单位：University of West Attica; Athens University of Economics & Business; University of London; London School Economics & Political Science
摘要：This paper examines the facial structure of the convex hull of integer vectors satisfying a system of alldifferent predicates, also called an alldifferent system. The underlying analysis is based on a property, called inclusion, pertinent to such a system. For the alldifferent systems for which this property holds, we present two families of facet-defining inequalities, establish that they completely describe the convex hull and show that they can be separated in polynomial time. Consequently,...
-
作者：Epstein, Leah; Levin, Asaf
作者单位：Technion Israel Institute of Technology; University of Haifa
摘要：Following the work of Anily et al., we consider a variant of bin packing called bin packing with general cost structures (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave...
-
作者：Ahmadi, Amir Ali; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：A multivariate polynomial p(x) = p(x (1), . . . , x (n) ) is sos-convex if its Hessian H(x) can be factored as H(x) = M (T) (x) M(x) with a possibly nonsquare polynomial matrix M(x). It is easy to see that sos-convexity is a sufficient condition for convexity of p(x). Moreover, the problem of deciding sos-convexity of a polynomial can be cast as the feasibility of a semidefinite program, which can be solved efficiently. Motivated by this computational tractability, it is natural to study wheth...
-
作者：Buchheim, Christoph; Caprara, Alberto; Lodi, Andrea
作者单位：University of Bologna; Dortmund University of Technology
摘要：We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast ...
-
作者：Letchford, Adam N.; Sorensen, Michael M.
作者单位：Lancaster University; Aarhus University
摘要：We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature-the cut, boolean quadric, multicut and clique partitioning polytopes-are faces of binary psd polytopes. Finally, we present some implications of these polyhedral relationships. In particular, we answer an open question in...
-
作者：Liberti, Leo
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique
摘要：If a mathematical program has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and for reformulating the problem by means of static symmetry breaking constraints. The reformulated problem-which is likely to have fewer symmetric optima-can then be solve...
