-
作者：Chubanov, Sergei
作者单位：Universitat Siegen
摘要：This paper proposes a strongly polynomial algorithm which either finds a solution of a linear system Ax = b, 0 a parts per thousand currency sign x a parts per thousand currency sign 1, or correctly decides that the system has no 0,1-solutions. The algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming.
-
作者：Zheng, Xi Yin; Ng, Kung Fu
作者单位：Yunnan University; Chinese University of Hong Kong
摘要：We first consider subsmoothness for a function family and provide formulas of the subdifferential of the pointwise supremum of a family of subsmooth functions. Next, we consider subsmooth infinite and semi-infinite optimization problems. In particular, we provide several dual and primal characterizations for a point to be a sharp minimum or a weak sharp minimum for such optimization problems.
-
作者：Anstreicher, Kurt M.
作者单位：University of Iowa
摘要：We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on is dominated by an alternative methodology based on convexifying the range of the quadratic form for . We next show that the use of BB underestimators as ...
-
作者：D'Ambrosio, Claudia; Frangioni, Antonio; Liberti, Leo; Lodi, Andrea
作者单位：University of Bologna; Institut Polytechnique de Paris; Ecole Polytechnique; University of Pisa
摘要：One of the foremost difficulties in solving Mixed-Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed-Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and con...
-
作者：Amaldi, Edoardo; Bosio, Sandro; Malucelli, Federico
作者单位：Polytechnic University of Milan
摘要：Motivated by a challenging problem arising in wireless network design, we investigate a new nonlinear variant of the set covering problem with hyperbolic objective function. Each ground-set element (user) competes with all its neighbors (interfering users) for a shared resource (the network access time), and the goal is to maximize the sum of the resource share assigned to each ground-set element (the network efficiency) while covering all of them. The hyperbolic objective function privileges ...
-
作者：Luedtke, James; Namazifar, Mahdi; Linderoth, Jeff
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, this approach yiel...
-
作者：Ben Gharbia, Ibtihel; Gilbert, J. Charles
作者单位：Universite PSL; Universite Paris-Dauphine
摘要：The plain Newton-min algorithm to solve the linear complementarity problem (LCP for short) can be viewed as a semismooth Newton algorithm without globalization technique to solve the system of piecewise linear equations min(x, Mx + q) = 0, which is equivalent to the LCP. When M is an M-matrix of order n, the algorithm is known to converge in at most n iterations. We show in this paper that this result no longer holds when M is a P-matrix of order a parts per thousand yen 3, since then the algo...
-
作者：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...
-
作者：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...
-
作者：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 ...
