-
作者：Van den Heuvel, Wilco; Kundakcioglu, O. Erhun; Geunes, Joseph; Romeijn, H. Edwin; Sharkey, Thomas C.; Wagelmans, Albert P. M.
作者单位：Erasmus University Rotterdam; Erasmus University Rotterdam - Excl Erasmus MC; University of Houston System; University of Houston; State University System of Florida; University of Florida; University of Michigan System; University of Michigan; Rensselaer Polytechnic Institute
摘要：Emphasis on effective demand management is becoming increasingly recognized as an important factor in operations performance. Operations models that account for supply costs and constraints as well as a supplier's ability to influence demand characteristics can lead to an improved match between supply and demand. This paper presents a class of optimization models that allow a supplier to select, from a set of potential markets, those markets that provide maximum profit when production/procurem...
-
作者：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,...
-
作者：Malick, Jerome; Roupin, Frederic
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：This paper deals with the computation of exact solutions of a classical NP-hard problem in combinatorial optimization, the -cluster problem. This problem consists in finding a heaviest subgraph with nodes in an edge weighted graph. We present a branch-and-bound algorithm that applies a novel bounding procedure, based on recent semidefinite programming techniques. We use new semidefinite bounds that are less tight than the standard semidefinite bounds, but cheaper to get. The experiments show t...
-
作者：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...
-
作者：de Klerk, Etienne; Pasechnik, Dmitrii; Sotirov, Renata; Dobre, Cristian
作者单位：Tilburg University; Nanyang Technological University
摘要：We derive a new semidefinite programming bound for the maximum -section problem. For (i.e. for maximum bisection), the new bound is at least as strong as a well-known bound by Poljak and Rendl (SIAM J Optim 5(3):467-487, 1995). For the new bound dominates a bound of Karisch and Rendl (Topics in semidefinite and interior-point methods, 1998). The new bound is derived from a recent semidefinite programming bound by De Klerk and Sotirov for the more general quadratic assignment problem, but only ...
-
作者：Sagastizabal, C.
摘要：Modern electricity systems provide a plethora of challenging issues in optimization. The increasing penetration of low carbon renewable sources of energy introduces uncertainty in problems traditionally modeled in a deterministic setting. The liberalization of the electricity sector brought the need of designing sound markets, ensuring capacity investments while properly reflecting strategic interactions. In all these problems, hedging risk, possibly in a dynamic manner, is also a concern. The...
-
作者：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...
