A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs

 The authors of this paper recently introduced a transformation [4] that converts a class of semidefinite programs (SDPs) into nonlinear optimization problems free of matrix-valued constraints and variables. This transformation enables the application of nonlinear optimization techniques to the solution of certain SDPs that are too large for conventional interior-point methods to handle efficiently. Based on the transformation, we proposed a globally convergent, first-order (i.e., gradient-based) log-barrier algorithm for solving a class of linear SDPs. In this paper, we discuss an efficient implementation of the proposed algorithm and report computational results on semidefinite relaxations of three types of combinatorial optimization problems. Our results demonstrate that the proposed algorithm is indeed capable of solving large-scale SDPs and is particularly effective for problems with a large number of constraints. Received: June 22, 2001 / Accepted: January 20, 2002 Published online: December 9, 2002 RID="†" ID="†"Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. RID="⋆" ID="⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203426 RID="⋆⋆" ID="⋆⋆"This author was supported in part by NSF Grants CCR-9902010, INT-9910084 and CCR-0203113 RID="⋆⋆⋆" ID="⋆⋆⋆"This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23 and NSF Grant DMS-9973339. Key Words. semidefinite program – semidefinite relaxation – nonlinear programming – interior-point methods – limited memory quasi-Newton methods. Mathematics Subject Classification (1991): 90C06, 90C27, 90C30.     

Propagation of polarization in elastodynamics with residual stress and travel times

 We show that knowing the displacement-to-traction map associated to the equations of isotropic elastodynamics with residual stress we can determine the lens maps of compressional and shear waves. We derive several consequences of this for the inverse problem of determining the residual stress and the Lamé parameters from the displacement-to-traction map. Received: 6 December 2001 / Revised version: 29 October 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" The author thanks the Department of Mathematics at the University of Washington for its hospitality during his visit in fall 2000. RID="⋆⋆" ID="⋆⋆" Partly supported by NSF grant DMS-0070488 and a John Simon Guggenheim fellowship. The author also thanks MSRI for partial support and for providing a very stimulating environment during the inverse problems program in fall 2001.     

On the extreme inequalities of infinite group problems

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous. S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611.     

A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

 We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also maps bases of the higher-dimensional cut generating linear program (CGLP) into bases of the linear programming relaxation. It provides new bounds on the number of facets of the elementary closure, and on the rank, of the standard linear programming relaxation of the mixed 0-1 polyhedron with respect to the above families of cutting planes. Based on the above correspondence, we develop an algorithm that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional (LP) simplex tableau. In particular, we show how to calculate the reduced costs of the big tableau from the entries of the small tableau and based on this, how to identify a pivot in the small tableau that corresponds to one or several improving pivots in the big tableau. The overall effect is a much improved lift-and-project cut generating procedure, which can also be interpreted as an algorithm for a systematic improvement of mixed integer Gomory cuts from the small tableau. Received: October 5, 2000 / Accepted: March 19, 2002 Published online: September 5, 2002 Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

A uniqueness result for a Neumann problem involving the critical Sobolev exponent

 In this paper we consider the problem

The value function of an integer program

We consider integer programs in which the objective function and constraint matrix are fixed while the right-hand side varies. The value function gives, for each feasible right-hand side, the criterion value of the optimal solution. We provide a precise characterization of the closed-form expression for any value function. The class of Gomory functions consists of those functions constructed from linear functions by taking maximums, sums, non-negative multiples, and ceiling (i.e., next highest integer) operations. The class of Gomory functions is identified with the class of all possible value functions by the following results: (1) for any Gomory functiong, there is an integer program which is feasible for all integer vectorsv and hasg as value function; (2) for any integer program, there is a Gomory functiong which is the value function for that program (for all feasible right-hand sides); (3) for any integer program there is a Gomory functionf such thatf(v)≤0 if and only ifv is a feasible right-hand side. Applications of (1)–(3) are also given.     

A direct impedance tomography algorithm for locating small inhomogeneities

Summary.  Impedance tomography seeks to recover the electrical conductivity distribution inside a body from measurements of current flows and voltages on its surface. In its most general form impedance tomography is quite ill-posed, but when additional a-priori information is admitted the situation changes dramatically. In this paper we consider the case where the goal is to find a number of small objects (inhomogeneities) inside an otherwise known conductor. Taking advantage of the smallness of the inhomogeneities, we can use asymptotic analysis to design a direct (i.e., non-iterative) reconstruction algorithm for the determination of their locations. The viability of this direct approach is documented by numerical examples. Received May 28, 2001 / Revised version received March 15, 2002 / Published online July 18, 2002 RID="⋆" ID="⋆" Supported by the Deutsche Forschungsgemeinschaft (DFG) under grant HA 2121/2-3 RID="⋆⋆" ID="⋆⋆" Supported by the National Science Foundation under grant DMS-0072556 Mathematics Subject Classification (2000): 65N21, 35R30, 35C20     

Extension of primal-dual interior point algorithms to symmetric cones

 In this paper we show that the so-called commutative class of primal-dual interior point algorithms which were designed by Monteiro and Zhang for semidefinite programming extends word-for-word to optimization problems over all symmetric cones. The machinery of Euclidean Jordan algebras is used to carry out this extension. Unlike some non-commutative algorithms such as the XS+SX method, this class of extensions does not use concepts outside of the Euclidean Jordan algebras. In particular no assumption is made about representability of the underlying Jordan algebra. As a special case, we prove polynomial iteration complexities for variants of the short-, semi-long-, and long-step path-following algorithms using the Nesterov-Todd, XS, or SX directions. Received: April 2000 / Accepted: May 2002 Published online: March 28, 2003 RID="⋆" ID="⋆" Part of this research was conducted when the first author was a postdoctoral associate at Center for Computational Optimization at Columbia University. RID="⋆⋆" ID="⋆⋆" Research supported in part by the U.S. National Science Foundation grant CCR-9901991 and Office of Naval Research contract number N00014-96-1-0704.     

Prüfer ⋆–multiplication domains and ⋆–coherence

Abstract The purpose of this paper is to deepen the study of the Prüfer ⋆–mul-tiplication domains, where ⋆ is a semistar operation. For this reason, we introduce the ⋆–domains, as a natural extension of the v-domains. We investigate their close relation with the Prüfer ⋆-multiplication domains. In particular, we obtain a characterization of Prüfer ⋆-multiplication domains in terms of ⋆–domains satisfying a variety of coherent-like conditions. We extend to the semistar setting the notion of -domain introduced by Glaz and Vasconcelos and we show, among the other results that, in the class of the –domains, the Prüfer ⋆-multiplication domains coincide with the ⋆-domains. Keywords: Star and semistar operation, Prüfer (⋆-multiplication) domain, -domain, Localizing system, Coherent domain, Divisorial and invertible ideal Mathematics Subject Classification (2000): 13F05, 13G05, 13E99     

On representations and <Emphasis Type="Italic">K</Emphasis>-theory of the braid groups

 Let Γ be the fundamental group of the complement of a K(Γ, 1) hyperplane arrangement (such as Artin's pure braid group) or more generally a homologically toroidal group as defined below. The triviality of bundles arising from orthogonal representations of Γ is characterized completely as follows. An orthogonal representation gives rise to a trivial bundle if and only if the representation factors through the spinor groups. Furthermore, the subgroup of elements in the complex K-theory of BΓ which arises from complex unitary representations of Γ is shown to be trivial. In the case of real K-theory, the subgroup of elements which arises from real orthogonal representations of Γ is an elementary abelian 2-group, which is characterized completely in terms of the first two Stiefel-Whitney classes of the representation. In addition, quadratic relations in the cohomology algebra of the pure braid groups which correspond precisely to the Jacobi identity for certain choices of Poisson algebras are shown to give the existence of certain homomorphisms from the pure braid group to generalized Heisenberg groups. These cohomology relations correspond to non-trivial Spin representations of the pure braid groups which give rise to trivial bundles. Received: 6 February 2002 / Revised version: 19 September 2002 / Published online: 8 April 2003 RID="⋆" ID="⋆" Partially supported by the NSF RID="⋆⋆" ID="⋆⋆" Partially supported by grant LEQSF(1999-02)-RD-A-01 from the Louisiana Board of Regents, and by grant MDA904-00-1-0038 from the National Security Agency RID="⋆" ID="⋆" Partially supported by the NSF Mathematics Subject Classification (2000): 20F36, 32S22, 55N15, 55R50     

Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems

Branch and cut methods for integer programming problems solve a sequence of linear programming problems. Traditionally, these linear programming relaxations have been solved using the simplex method. The reduced costs available at the optimal solution to a relaxation may make it possible to fix variables at zero or one. If the solution to a relaxation is fractional, additional constraints can be generated which cut off the solution to the relaxation, but donot cut off any feasible integer points. Gomory cutting planes and other classes of cutting planes are generated from the final tableau. In this paper, we consider using an interior point method to solve the linear programming relaxations. We show that it is still possible to generate Gomory cuts and other cuts without having to recreate a tableau, and we also show how variables can be fixed without using the optimal reduced costs. The procedures we develop do not require that the current relaxation be solved to optimality; this is useful for an interior point method because early termination of the current relaxation results in an improved starting point for the next relaxation.     

Unique continuation for the linearized Benjamin-Bona-Mahony equation with space-dependent potential

 In this paper, we analyze a unique continuation problem for the linearized Benjamin-Bona-Mahony equation with space-dependent potential in a bounded interval with Dirichlet boundary conditions. The underlying Cauchy problem is a characteristic one. We prove two unique continuation results by means of spectral analysis and the (generalized) eigenvector expansion of the solution, instead of the usual Holmgren-type method or Carleman-type estimates. It is found that the unique continuation property depends very strongly on the nature of the potential and, in particular, on its zero set, and not only on its boundedness or integrability properties. Received: 6 December 2001 / Revised version: 13 June 2002 / Published online: 10 February 2003 RID="⋆" ID="⋆" Supported by a Postdoctoral Fellowship of the Spanish Education and Culture Ministry, the Foundation for the Author of National Excellent Doctoral Dissertation of P.R. China (Project No: 200119), and the NSF of China under Grant 19901024 RID="⋆⋆" ID="⋆⋆" Supported by grant PB96-0663 of the DGES (Spain) and the EU TMR Project "Homogenization and Multiple Scales". Mathematics Subject Classification (2000): 35B60, 47A70, 47B07     

Projected Chvátal–Gomory cuts for mixed integer linear programs

Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically be solved in a reasonable amount of computing time. Gérard Cornuéjols was supported in part by NSF grant DMI-0352885, ONR grant N00014-03-1-0188, and ANR grant BLAN 06-1-138894. Matteo Fischetti was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2). Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2).     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables. Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001     

Minimal surfaces of rotation in Finsler space with a Randers metric

 We consider Finsler spaces with a Randers metric F=α+β, on the three dimensional real vector space, where α is the Euclidean metric and β=bdx ₃ is a 1-form with norm b,0≤b<1. By using the notion of mean curvature for immersions in Finsler spaces introduced by Z. Shen, we get the ordinary differential equation that characterizes the minimal surfaces of rotation around the x ₃ axis. We prove that for every b,0≤b<1, there exists, up to homothety, a unique forward complete minimal surface of rotation. The surface is embedded, symmetric with respect to a plane perpendicular to the rotation axis and it is generated by a concave plane curve. Moreover, for every there are non complete minimal surfaces of rotation, which include explicit minimal cones. Received: 30 November 2001 / Published online: 10 February 2003 RID="⋆" ID="⋆" Partially supported by CAPES RID="⋆⋆" ID="⋆⋆" Partially supported by CNPq and PROCAD.     

Seshadri-exceptional foliations

 The maximal Seshadri number μ(L) of an ample line bundle L on a smooth projective variety X measures the local positivity of the line bundle L at a general point of X. By refining the method of Ein-Küchle-Lazarsfeld, lower bounds on μ(L) are obtained in terms of L ⁿ , n=dim(X), for a class of varieties. The main idea is to show that if a certain lower bound is violated, there exists a non-trivial foliation on the variety whose leaves are covered by special curves. In a number of examples, one can show that such foliations must be trivial and obtain lower bounds for μ(L). The examples include the hyperplane line bundle on a smooth surface in ℙ³ and ample line bundles on smooth threefolds of Picard number 1. Received: 29 June 2001 / Published online: 16 October 2002 RID="⋆" ID="⋆" Supported by Grant No. 98-0701-01-5-L from the KOSEF. RID="⋆⋆" ID="⋆⋆" Supported by Grant No. KRF-2001-041-D00025 from the KRF.     

Integral decomposition of polyhedra and some applications in mixed integer programming

 This paper addresses the question of decomposing an infinite family of rational polyhedra in an integer fashion. It is shown that there is a finite subset of this family that generates the entire family. Moreover, an integer analogue of Carathéodory's theorem carries over to this general setting. The integer decomposition of a family of polyhedra has some applications in integer and mixed integer programming, including a test set approach to mixed integer programming. Received: May 22, 2000 / Accepted: March 19, 2002 Published online: December 19, 2002 Key words. mixed integer programming – test sets – indecomposable polyhedra – Hilbert bases – rational polyhedral cones This work was supported partially by the DFG through grant WE1462, by the Kultusministerium of Sachsen Anhalt through the grants FKZ37KD0099 and FKZ 2945A/0028G and by the EU Donet project ERB FMRX-CT98-0202. The first named author acknowledges the hospitality of the International Erwin Schr?dinger Institute for Mathematical Physics in Vienna, where a main part of his contribution to this work has been completed. Mathematics Subject Classification (1991): 52C17, 11H31     

On complexity reduction of Σ<Subscript>1</Subscript> formulas

 For a fixed q  ℕ and a given Σ₁ definition φ(d,x), where d is a parameter, we construct a model M of 1 Δ₀ + ? exp and a non standard d  M such that in M either φ has no witness smaller than d or phgr; is equivalent to a formula ϕ(d,x) having no more than q alternations of blocks of quantifiers. Received: 29 September 1998 / Revised version: 7 November 2001 Published online: 10 October 2002 RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13. RID="⋆" ID="⋆" Research supported in part by The State Committee for Scientific Research (Poland), KBN, grant number 2 PO3A 018 13.     

Valid Inequalities for the Lasdon-Terjung Production Model

We consider a very simple integer program involving production of a single item and start-up costs for the standard machines first studied by Lasdon and Terjung. Solving directly as an integer program leads to prohibitively large branch and bound trees. Here, we show how using a simple family of valid inequalities and a heuristic procedure to choose one of these inequalities as a cut, it is possible to reduce substantially the size of the tree, and in several cases to eliminate the need for branch and bound. The valid inequalities used are all simple Gomory cuts. However, they are derived from the initial problem formulation rather than from the optimal linear programming tableau.