The <Emphasis Type="SmallCaps">Mcf</Emphasis>-separator: detecting and exploiting multi-commodity flow structures in MIPs

Given a general mixed integer program, we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of Scip and Cplex. We make use of the complemented mixed integer rounding framework but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of mixed integer programs coming from network design problems by a factor two on average. We show that almost 10% of the instances in general testsets contain consistent embedded networks. For these instances the computation time is decreased by 18% on average.     

Duality gap in convex programming

In this paper, we consider general convex programming problems and give a sufficient condition for the equality of the infimum of the original problem and the supremum of its ordinary dual. This condition may be seen as a continuity assumption on the constraint sets (i.e. on the sublevel sets of the constraint function) under linear perturbation. It allows us to generalize as well as treat previous results in a unified framework. Our main result is in fact based on a quite general constraint qualification result for quasiconvex programs involving a convex objective function proven in the setting of a real normed vector space.Mathematics Subject Classification (2000):90C25, 90C26, 90C30, 90C31     

Programming with a special class of nonlinear functionals

Summary In this paper we consider programming problems in which the constraints are linear and the objective function is the product or the quotient of two functions, each function being a homogeneous form of first degree with a constant added to it.With the proper assumptions of concavity or convexity of the homogeneous forms, this nonlinear programming problem is reduced to that of maximization of a concave function over a convex constraint set.

---

Zusammenfassung In der vorliegenden Arbeit werden Programme untersucht, bei denen die Nebenbedingungen linear sind und die Zielfunktion als Produkt bzw. Quotient zweier Funktionen darstellbar ist, die bis auf additive Konstanten homogen von 1. Grad sind. Bei geeigneten Konvexitäts- oder Konkavitätsannahmen für diese Funktionen lassen sich solche Programme auf die Maximierung einer konkaven Funktion in einem konvexen Gebiet zurückführen.

---

---

Prepared with the partial support of the C.S.I.R., India.

---

Vorgel. v.:J. Nitsche.     

The spherical constraint in Boolean quadratic programs

We propose a new approach to bound Boolean quadratic optimization problems. The idea is to re-express the Boolean constraints as one “spherical” constraint, whose dualization amounts to semidefinite least-squares problems. Studying this dualization provides an alternative interpretation of the sdp relaxation. It also reveals a new class of non-convex problems with no duality gap.     

Aggregating diophantine equations

Summary Mathews [1897] has given a theorem for aggregating two diophantine equations with positive integer coefficients into a single equation that has the same solution set as its parents over the nonnegative integers. Building on this result,Elmaghraby andWig [1970] show how to shrink the inequality constraints of a bounded variable integer program to a single constraint equation. However, such applications are limited, as we show, by a greater than exponential growth in coefficient size as successive constraints are aggregated into one. To mitigate this situation, we give new theorems and implementation procedures that provide exponential order reductions in the coefficient growth attending the aggregation process.

---

Zusammenfassung Mathews [1897] hat ein Theorem zur Zusammenfassung zweier diophantischer Gleichungen mit positiven ganzzahligen Koeffizienten zu einer einzigen Gleichung mit derselben Lösungsmenge wie die beiden ursprünglichen Gleichungen entwickelt. Aufbauend auf dieses Ergebnis zeigtenElmaghraby undWig [1970] eine Möglichkeit, die Ungleichungen eines ganzzahligen Optimierungsproblems mit begrenzten Variablen sukzessive auf eine einzige Gleichung zu reduzieren. Die praktische Anwendbarkeit ist jedoch begrenzt. Bei der sukzessiven Zusammenfassung der Nebenbedingungen zu einer einzigen wachsen die Koeffizienten stärker als exponentiell an. Um diesen Nachteil zu mindern, werden hier neue Theoreme und Anwendungsprozeduren entwickelt. Diese gewährleisten, daß das Anwachsen der Koeffizienten im Verlaufe des Aggregationsprozesses um einen Faktor exponentieller Ordnung geringer ist.

     

Cone contraction and reference point methods for multi-criteria mixed integer optimization

Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).     

A new Pareto set generating method for multi-criteria optimization problems

This paper proposes a new classical method to capture the complete Pareto set of a multi-criteria optimization problem (MOP) even without having any prior information about the location of Pareto surface. The solutions obtained through the proposed method are globally Pareto optimal. Moreover, each and every global Pareto optimal point is within the attainable range. This paper also suggests a procedure to ensure the proper Pareto optimality of the outcomes if slight modifications are allowed in the constraint set of the MOP under consideration. Among the set of all outcomes, the proposed method can effectively detect the regions of unbounded trade-offs between the criteria, if they exist.     

Eine Ungleichung von van der Corput und Kemperman

The tool of van der Corput's difference theorem in the theory of uniform distribution is his so-called fundamental inequality.Kemperman showed that even the non-constructive proofs of the difference theorem byBass, Bertrandias andCigler implicitly use a more general form of van der Corput's fundamental inequality. In this article, the inequality which constitutes the basis of the difference theorem will be proved under a very general setting, applications will be demonstrated in connection with the uniform distribution of products of linear forms and a quantitative version of the difference theorem, i. e. an estimation of discrepancies, will be derived.     

Alcune limitazioni per le soluzioni di equazioni paraboliche

Sunto Si discute il problema diCauchy relativo all'equazione del calore, u_t=u_xx, ed a condizioni iniziali sull'asse t. Si provano inoltre alcune proprietà delle soluzioni positive di tale problema e di analoghi problemi diCauchy relativi a più generali equazioni paraboliche.

---

Summary We consider theCauchy problem for the heat equation, u_t=u_xx, with initial conditions on the t-axis. We prove some property of positive solutions of this problem, and of similarCauchy problems for more general parabolic equations.

---

---

A Giovanni Sansone nel suo 70^mo compleanno.     

Über die Konvergenz des Verfahrens vonGrammel und seine mögliche Erweiterung

Summary The paper deals with the convergence ofR. Grammel's method for the solution of boundary-eigenvalue-problems. It is further shown thatGrammel's method can be extended to the case where it is difficult to find the exactGreen function. In this case one may use a different, relatedGreen function if one adds certain supplemental terms to the properGrammel equations.     

A class of quadratically convergent algorithms for constrained function minimization

The problem of minimizing a functionf(x) subject to the constraint ?(x)=0 is considered. Here,f is a scalar,x is ann-vector, and ? is anm-vector, wherem <n. A general quadratically convergent algorithm is presented. The conjugate-gradient algorithm and the variable-metric algorithms for constrained function minimization can be obtained as particular cases of the general algorithm. It is shown that, for a quadratic function subject to a linear constraint, all the particular algorithms behave identically if the one-dimensional search for the stepsize is exact. Specifically, they all produce the same sequence of points and lead to the constrained minimal point in no more thann ?r descent steps, wherer is the number of linearly independent constraints. The algorithms are then modified so that they can also be employed for a nonquadratic function subject to a nonlinear constraint. Some particular algorithms are tested through several numerical examples.     

Fictitious states,coupled laws and local time

Summary The work of Ray and Neveu has established that, for any transition function P on a countable set E, (i) there exists a best possible entrance boundary E ⁺ supporting a right continuous, strong Markov process X with transition function P and that (ii) the points y of E ⁺ are in one-one correspondence with the extremal entrance laws g ^y of P. Here, it is shown that, if a point y of E ⁺ is regular for itself, then the derived characteristic f ^y of the local time at y is a regular extremal entrance law coupled with g ^y in the sense of Neveu. Further, coupled laws arise only in this fashion. By using excursion theory, a simple explicit formula for f ^y in terms of g ^y may be obtained. The paper contains a conjecture about the intrinsic character of the Ray-Neveu topology and an example which shows emphatically that, in general, local time is not a derivative of occupation time.     

Bimeasures and their integral extensions

Summary The object of this paper is to motivate three papers byM. Morse andW. Transue, which will presently appear, where the Authors will lay the foundations of a general theory of C-bimeasures and their integral extensions. To Mauro Picone on his 70^th birth day.     

An optimization problem on subsets of the symmetric positive-semidefinite matrices

Motivated by the metricsstress problem in multidimensional scaling, the authors consider the more general problem of minimizing a strictly convex function on a particular subset ofR ^{n × n} . The subset in question is the intersection of a linear subspace with the symmetric positive-semidefinite matrices of rank p. Because of the rank restriction, this subset is not convex. Several equivalent formulations of this problem are derived, and the advantages and disadvantages of each formulation are discussed.Part of this research was conducted while the authors were visitors at the Center for Research on Parallel Computation, Rice University, Houston, Texas. The first author was partially supported by National Science Foundation Grant RII-89-05080.     

Maße für gerichtete Geraden und nicht-symmetrische Pseudometriken in der Ebene

We consider random orientated straight lines in the Euclidian plane.R. Ambartzumian has pointed out that general measures of straight lines are linked with certain pseudo-metrics. He has proved that any pseudometric satisfying certain conditions is generated by a measure of straight lines. In this paper, we investigate general measures of orientated straight lines and show that they are linked with functions whose properties are similar to those of pseudo-metrics. In general, the symmetry is not given. Starting from these non-symmetric pseudo-metrics it is possible to define some sort of length of a curve such that the theorem ofCrofton giving the number of common points of random straight lines and fixed curves remains valid for general measures.     

Machine learning for global optimization

In this paper we introduce the LeGO (Learning for Global Optimization) approach for global optimization in which machine learning is used to predict the outcome of a computationally expensive global optimization run, based upon a suitable training performed by standard runs of the same global optimization method. We propose to use a Support Vector Machine (although different machine learning tools might be employed) to learn the relationship between the starting point of an algorithm and the final outcome (which is usually related to the function value at the point returned by the procedure). Numerical experiments performed both on classical test functions and on difficult space trajectory planning problems show that the proposed approach can be very effective in identifying good starting points for global optimization.     

Stability analysis of the cell centered finite-volume M<Emphasis Type="SmallCaps">uscl</Emphasis> method on unstructured grids

The goal of this study is to apply the Muscl scheme to the linear advection equation on general unstructured grids and to examine the eigenvalue stability of the resulting linear semi-discrete equation. Although this semi-discrete scheme is in general stable on cartesian grids, numerical calculations of spectra show that this can sometimes fail for generalizations of the Muscl method to unstructured three-dimensional grids. This motivates our investigation of the influence of the slope reconstruction method and stencil on the eigenvalue stability of the Muscl scheme. A theoretical stability analysis of the first order upwind scheme proves that this method is stable on arbitrary grids. In contrast, a general theoretical result is very difficult to obtain for the Muscl scheme. We are able to identify a local property of the slope reconstruction that is strongly related to the appearance of unstable eigenmodes. This property allows to identify the reconstruction methods that are best suited for stable discretizations. The explicit numerical computation of spectra for a large number of two- and three-dimensional test cases confirms and completes the theoretical results.     

Convergence of an implicit, constraint preserving finite element discretization of p-harmonic heat flow into spheres

We propose an implicit discretization of the p-harmonic map heat flow into the sphere S ² that enjoys a discrete energy inequality and converges under only a mild mesh constraint to a weak solution. A fully practical iterative scheme that approximates the solution of the nonlinear system of equations in each time step is proposed and analyzed. Computational studies to motivate possible finite-time blow-up behavior of solutions for p ≠ 2 are included. Supported by Deutsche Forschungsgemeinschaft through the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

On the asymptotic behaviour of subcritical branching processes with continuous state space

Summary A detailed account is given of the asymptotic behaviour, in the subcritical case, of a simple class of continuous-state branching processes. In particular, a recent theorem of Kuczma from the theory of functional equations is used to obtain necessary and sufficient conditions for theorems of Kolmogorov-Yaglom type to hold, thus strengthening, for the class of processes treated, some general results of Jirina. It is also shown that these results are closely related to a theorem on the convergence of sums of independent branching processes, and to certain properties of infinitely divisible distributions on the non-negative reals. The theorems are obtained in the first place for processes with unit initial quantity of ancestor, but in a final section it is shown that they can be extended to processes with a general initial distribution if, and only if, this distribution satisfies a regular variation condition.     

Fehlerabschätzung für die numerische Differentiation analytischer Funktionen durch Quadratur

Summary Numerical treatment of the integral in Cauchy's integral formula produces approximations for the derivatives of an analytic functionf; this fact has already been utilized byLyness andMoler [3, 4]. In the present paper this idea is investigated especially in view of the accuracy of these formulas regarded as quadrature formulas. Since the integration can be reduced to the integration of a periodic analytic function, it is possible to continue the considerations ofDavis [2] in order to find bounds for the error of the differentiation rules. For the application of these bounds one essentially needs estimations of the maximum off on a circle inside of its region of analyticity. Examples show the practical use of the bounds.

---

---

Meinem verehrten LehrerH. Görtler zur Vollendung seines 60. Lebensjahres gewidmet