A primal all-integer algorithm based on irreducible solutions

 This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method. Received: April 23, 2001 / Accepted: May 2002 Published online: March 21, 2003 RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="#" ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202. Mathematics Subject Classification (1991): 90C10     

Integer programming models and linearizations for the traveling car renter problem

The traveling car renter problem (CaRS) is an extension of the classical traveling salesman problem (TSP) where different cars are available for use during the salesman’s tour. In this study we present three integer programming formulations for CaRS, of which two have quadratic objective functions and the other has quadratic constraints. The first model with a quadratic objective function is grounded on the TSP interpreted as a special case of the quadratic assignment problem in which the assignment variables refer to visitation orders. The second model with a quadratic objective function is based on the Gavish and Grave’s formulation for the TSP. The model with quadratic constraints is based on the Dantzig–Fulkerson–Johnson’s formulation for the TSP. The formulations are linearized and implemented in two solvers. An experiment with 50 instances is reported.     

On the serial cost sharing rule

In this paper we study a solution for discrete cost allocation problems, namely, the serial cost sharing method. We show that this solution can be computed by applying the Shapley value to an appropriate TU game and we present a probabilistic formula. We also define for cost allocation problems a multilinear function in order to obtain the serial cost sharing method as Owen (1972) did for the Shapley value in the cooperative TU context. Moreover we show that the pseudo average cost method is equivalent to an extended Shapley value. Received April 2000/Revised January 2003 RID="*" ID="*"  Authors are indebted to two anonymous referees for especially careful and useful comments. This research has been partially supported by the University of the Basque Country (projects UPV 036.321-HA197/98, UPV 036.321-HA042/99) and DGES Ministerio de Educación y Ciencia (project PB96-0247).     

A likelihood-MPEC approach to target classification

In this paper we develop a method for classifying an unknown data vector as belonging to one of several classes. This method is based on the statistical methods of maximum likehood and borrowed strength estimation. We develop an MPEC procedure (for Mathematical Program with Equilibrium Constraints) for the classification of a multi-dimensional observation, using a finite set of observed training data as the inputs to a bilevel optimization problem. We present a penalty interior point method for solving the resulting MPEC and report numerical results for a multispectral minefield classification application. Related approaches based on conventional maximum likehood estimation and a bivariate normal mixture model, as well as alternative surrogate classification objective functions, are described. Received: October 26, 1998 / Accepted: June 11, 2001?Published online March 24, 2003 RID="***" ID="***"The authors of this work were all partially supported by the Wright Patterson Air Force Base via Veda Contract F33615-94-D-1400. The first and third author were also supported by the National Science Foundation under grant DMS-9705220. RID="*" ID="*"The work of this author was based on research supported by the U.S. National Science Foundation under grant CCR-9624018. RID="**" ID="**"The work of this author was supported by the Office of Naval Research under grant N00014-95-1-0777.     

Dense subgroups of <Emphasis Type="Italic">n</Emphasis>-dimensional Möbius groups

We will derive a new discreteness condition for n-dimensional M?bius subgroups as well as obtain some results concerning classification of such groups. We will also discuss dense subgroups of n-dimensional M?bius groups. The main result is that any dense group of an n-dimensional M?bius group contains a dense subgroup which is generated by at most n elements if . Received: 5 June 2001 / Published online: 24 February 2003 RID="*" ID="*" The research was partly supported by FNS of China, grant number 19801011     

Valuation theory of exponential Hardy fields I

We describe the valuation theoretic properties of the Hardy fields associated to models of , where T is the theory of a polynomially bounded o-minimal expansion of the reals and is the real exponential function. We deduce that has levels with parameters and is exponentially bounded. We establish a maximality property of , the Hardy field of the expansion by the restricted analytic functions and power functions. Received: 10 July 2000 ; in final form: 15 April 2002/Published online: 24 February 2003 RID="*" ID="*" This paper was written while both authors were partially supported by a Canadian NSERC research grant.     

Applications of convex optimization in signal processing and digital communication

 In the last two decades, the mathematical programming community has witnessed some spectacular advances in interior point methods and robust optimization. These advances have recently started to significantly impact various fields of applied sciences and engineering where computational efficiency is essential. This paper focuses on two such fields: digital signal processing and communication. In the past, the widely used optimization methods in both fields had been the gradient descent or least squares methods, both of which are known to suffer from the usual headaches of stepsize selection, algorithm initialization and local minima. With the recent advances in conic and robust optimization, the opportunity is ripe to use the newly developed interior point optimization techniques and highly efficient software tools to help advance the fields of signal processing and digital communication. This paper surveys recent successes of applying interior point and robust optimization to solve some core problems in these two fields. The successful applications considered in this paper include adaptive filtering, robust beamforming, design and analysis of multi-user communication system, channel equalization, decoding and detection. Throughout, our emphasis is on how to exploit the hidden convexity, convex reformulation of semi-infinite constraints, analysis of convergence, complexity and performance, as well as efficient practical implementation. Received: January 22, 2003 / Accepted: April 29, 2003 Published online: May 28, 2003 RID="*" ID="*" This research was supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant No. OPG0090391, and by the Canada Research Chair program. New address after April 1, 2003: Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA     

Buyer-seller exactness in the assignment game

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a “45^o-lattice” by means of the core of an assignment game can now be answered. Received: March 2002/Revised version: January 2003 RID="*" ID="*"  Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged RID="**" ID="**"  The authors thank the referees for their comments     

On the Oka principle in a Banach space,I

 Let X be a complex Banach space with a countable unconditional basis, Ω⊂X pseudoconvex open, G a complex Banach Lie group. We show that a Runge–type approximation hypothesis on X, G (which we also prove for G a solvable Lie group) implies that any holomorphic cocycle on Ω with values in G can be resolved holomorphically if it can be resolved continuously. Received: 1 March 2002 / Published online: 28 March 2003 Mathematics Subject Classification (2000): 32L05, 32E30, 46G20 RID="*" ID="*" Kedves Szímuskának. RID="*" ID="*" To my dear Wife.     

Morse theory on spaces of braids and Lagrangian dynamics

In the first half of the paper we construct a Morse-type theory on certain spaces of braid diagrams. We define a topological invariant of closed positive braids which is correlated with the existence of invariant sets of parabolic flows defined on discretized braid spaces. Parabolic flows, a type of one-dimensional lattice dynamics, evolve singular braid diagrams in such a way as to decrease their topological complexity; algebraic lengths decrease monotonically. This topological invariant is derived from a Morse-Conley homotopy index.?In the second half of the paper we apply this technology to second order Lagrangians via a discrete formulation of the variational problem. This culminates in a very general forcing theorem for the existence of infinitely many braid classes of closed orbits. Oblatum 11-V-2001 & 13-XI-2002?Published online: 24 February 2003 RID="*" ID="*"The first author was supported by NSF DMS-9971629 and NSF DMS-0134408. The second author was supported by an EPSRC Fellowship. The third author was supported by NWO Vidi-grant 639.032.202.     

Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem

The stable-set problem is an NP-hard problem that arises in numerous areas such as social networking, electrical engineering, environmental forest planning, bioinformatics clustering and prediction, and computational chemistry. While some relaxations provide high-quality bounds, they result in very large and expensive conic optimization problems. We describe and test an integrated interior-point cutting-plane method that efficiently handles the large number of nonnegativity constraints in the popular doubly-nonnegative relaxation. This algorithm identifies relevant inequalities dynamically and selectively adds new constraints in a build-up fashion. We present computational results showing the significant benefits of this approach in comparison to a standard interior-point cutting-plane method.     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

A spectral bundle method with bounds

Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. In addition, we introduce inexact null steps. This abolishes the need of computing exact eigenvectors for subgradients, which brings along significant advantages in theory and in practice. Encouraging preliminary computational results are reported. Received: February 1, 2000 / Accepted: September 26, 2001?Published online August 27, 2002 RID="*" ID="*"A preliminary version of this paper appeared in the proceedings of IPCO ’98 [12].     

On rational cuspidal curves

Let be a rational curve of degree d which has only one analytic branch at each point. Denote by m the maximal multiplicity of singularities of C. It is proven in [MS] that . We show that where is the square of the “golden section”. We also construct examples which show that this estimate is asymptotically sharp. When , we show that and this estimate is sharp. The main tool used here, is the logarithmic version of the Bogomolov-Miyaoka-Yau inequality. For curves as above we give an interpretation of this inequality in terms of the number of parameters describing curves of a given degree and the number of conditions imposed by singularity types. Received: 11 February 2000 / Published online: 8 November 2002 RID="*" ID="*" Partially supported by Grants RFFI-96-01-01218 and DGICYT SAB95-0502     

Implementing the simplex method as a cutting-plane method, with a view to regularization

We show that the simplex method can be interpreted as a cutting-plane method, assuming that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We focus on the special linear programming problem of finding the largest ball that fits into a given polyhedron. In a computational study we demonstrate that ball-fitting problems have such special characteristics which indicate their utility in regularization schemes.     

Design and verify: a new scheme for generating cutting-planes

A cutting-plane procedure for integer programming (IP) problems usually involves invoking a black-box procedure (such as the Gomory–Chvátal procedure) to compute a cutting-plane. In this paper, we describe an alternative paradigm of using the same cutting-plane black-box. This involves two steps. In the first step, we design an inequality $cx \le d$ where $c$ and $d$ are integral, independent of the cutting-plane black-box. In the second step, we verify that the designed inequality is a valid inequality by verifying that the set $P \cap \{x\in \mathbb R ^n \mid cx \ge d + 1\} \cap \mathbb Z ^n$ is empty using cutting-planes from the black-box. Here $P$ is the feasible region of the linear-programming relaxation of the IP. We refer to the closure of all cutting-planes that can be verified to be valid using a specific cutting-plane black-box as the verification closure of the considered cutting-plane black-box. This paper undertakes a systematic study of properties of verification closures of various cutting-plane black-box procedures.