-
作者：Balas, Egon; Saxena, Anureet
作者单位：Carnegie Mellon University
摘要：The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation P of a mixed integer program (MIP) is termed the (elementary, or rank 1) split closure of P. This paper deals with the problem of optimizing over the elementary split closure. This is accomplished by repeatedly solving the following separation problem: given a fractional point, say x, find a rank-1 split cut violated by x or show that none exists. Following Caprara and...
-
作者：Chua, Chek Beng
作者单位：Nanyang Technological University
摘要：The purpose of this paper is two-fold. Firstly, we show that every Cholesky-based weighted central path for semidefinite programming is analytic under strict complementarity. This result is applied to homogeneous cone programming to show that the central paths defined by the known class of optimal self-concordant barriers are analytic in the presence of strictly complementary solutions. Secondly, we consider a sequence of primal-dual solutions that lies within a prescribed neighborhood of the ...
-
作者：Avis, David; Imai, Hiroshi; Ito, Tsuyoshi
作者单位：University of Tokyo; McGill University; Japan Science & Technology Agency (JST)
摘要：The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lift...
-
作者：Baldacci, Roberto; Christofides, Nicos; Mingozzi, Aristide
作者单位：University of Bologna; Imperial College London; University of Bologna
摘要：This paper presents a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. The exact algorithm uses a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation o...
-
作者：Jeyakumar, V.; Lee, G. M.
作者单位：University of New South Wales Sydney; Pukyong National University
摘要：We establish necessary and sufficient conditions for a stable Farkas' lemma. We then derive necessary and sufficient conditions for a stable duality of a cone-convex optimization problem, where strong duality holds for each linear perturbation of a given convex objective function. As an application, we obtain stable duality results for convex semi-definite programs and convex second-order cone programs.
-
作者：Giallombardo, Giovanni; Ralph, Daniel
作者单位：University of Calabria; University of Cambridge
摘要：We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determ...
-
作者：Corvellec, Jean-Noel; Motreanu, Viorica V.
作者单位：Universite Perpignan Via Domitia
摘要：As a development of the theory of linear error bounds for lower semicontinuous functions defined on complete metric spaces, introduced in Aze et al. (Nonlinear Anal 49, 643-670, 2002) and refined in Aze and Corvellec (ESAIM Control Optim Calc Var 10, 409-425, 2004), we propose a similar approach to nonlinear error bounds, based on the notion of strong slope, the variational principle, and the change-of-metric principle, the latter allowing to obtain sharp estimates for such error bounds throug...
-
作者：Hu, Jian-Feng; Pan, Ping-Qi
作者单位：Southeast University - China
摘要：The simplex algorithm computes the simplex multipliers by solving a system (or two triangular systems) at each iteration. This note offers an efficient approach to updating the simplex multipliers in conjunction with the Bartels-Golub and Forrest-Tomlin updates for LU factors of the basis. It only solves one triangular system. The approach was implemented within and tested against MINOS 5.51 on 129 problems from Netlib, Kennington and BPMPD. Computational results show that the new approach imp...
-
作者：Naumann, Uwe
作者单位：RWTH Aachen University
摘要：We show that the problem of accumulating Jacobian matrices by using a minimal number of floating-point operations is NP-complete by reduction from Ensemble Computation. The proof makes use of the fact that, deviating from the state-of-the-art assumption, algebraic dependences can exist between the local partial derivatives. It follows immediately that the same problem for directional derivatives, adjoints, and higher derivatives is NP-complete, too.
-
作者：Noyan, Nilay; Ruszczynski, Andrzej
作者单位：Rutgers University System; Rutgers University New Brunswick; Sabanci University
摘要：Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of t...
