Decomposition of test sets in stochastic integer programming

 We study Graver test sets for linear two-stage stochastic integer programs and show that test sets can be decomposed into finitely many building blocks whose number is independent on the number of scenarios of the stochastic program. We present a finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Finally, we report preliminary computational experience. Received: March 14, 2002 / Accepted: March 27, 2002 Published online: September 27, 2002 Key words. test sets – stochastic integer programming – decomposition methods Mathematics Subject Classification (2000): 90C15, 90C10, 13P10     

Maximum stable set formulations and heuristics based on continuous optimization

 The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics. Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 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. Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous optimization heuristics – nonlinear programming Mathematics Subject Classification (2000): 90C06, 90C27, 90C30     

Aspects of strong compactness, measurability, and indestructibility

 We prove three theorems concerning Laver indestructibility, strong compactness, and measurability. We then state some related open questions. Received: 11 December 1999 / Revised version: 17 September 2000 / Published online: 2 September 2002 Mathematics Subject classification (2000): 03E35, 03E55 Keywords or phrases: Measurable cardinal – Strongly compact cardinal – Supercompact cardinal – Indestructibility     

Optimization in forestry

 Optimization models and methods have been used extensively in the forest industry. In this paper we describe the general wood-flow in forestry and a variety of planning problems. These cover planning periods from a fraction of a second to more than one hundred years. The problems are modelled using linear, integer and nonlinear models. Solution methods used depend on the required solution time and include for example dynamic programming, LP methods, branch & bound methods, heuristics and column generation. The importance of modelling and qualitative information is also discussed. Received: January 15, 2003 / Accepted: April 24, 2003 Published online: May 28, 2003 Key words. Forestry – modelling – routing – transportation – production planning Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra

 We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example. Received: October 8, 2000 / Accepted: August 13, 2002 Published online: September 27, 2002 Key words. stochastic programming – integer programming – valid inequalities     

On the partition function of a directed polymer in a Gaussian random environment

 The purpose of this work is the study of the partition function of a -dimensional lattice directed polymer in a Gaussian random environment being the inverse of temperature). In the low-dimensional cases , we prove that for all , the renormalized partition function converges to 0 and the correlation of two independent configurations does not converge to 0. In the high dimensional case (), a lower tail of has been obtained for small . Furthermore, we express some thermodynamic quantities in terms of the path measure alone. Received: 8 June 2001 / Revised version: 8 February 2002 / Published online: 22 August 2002 Mathematics Subject Classification (2000): 60K37, 82D30 Key words or phrases: Directed polymer in random environment – Gaussian environment – partition function     

A Gentzen-style axiomatization for basic predicate calculus

 We introduce a Gentzen-style sequent calculus axiomatization for Basic Predicate Calculus. Our new axiomatization is an improvement of the previous axiomatizations, in the sense that it has the subformula property. In this system the cut rule is eliminated. Received: 18 April 2000 / Published online: 2 September 2002 Mathematics Subject Classification (2000): Primary 03F05; Secondary 03F99, 03B60 Key words or phrases: Basic predicate calculus – Cut elimination – Sequent     

Renormalization and homogenization of fractional diffusion equations with random data

 This paper presents a renormalization and homogenization theory for fractional-in-space or in-time diffusion equations with singular random initial conditions. The spectral representations for the solutions of these equations are provided. Gaussian and non-Gaussian limiting distributions of the renormalized solutions of these equations are then described in terms of multiple stochastic integral representations. Received: 30 May 2000 / Revised version: 9 November 2001 / Published online: 10 September 2002 Mathematics Subject Classification (2000): Primary 62M40, 62M15; Secondary 60H05, 60G60 Key words or phrases: Fractional diffusion equation – Scaling laws – Renormalised solution – Long-range dependence – Non-Gaussian scenario – Mittag-Leffler function – Stable distributions – Bessel potential – Riesz potential     

A notion of rank in set theory without choice

 Starting from the definition of `amorphous set' in set theory without the axiom of choice, we propose a notion of rank (which will only make sense for, at most, the class of Dedekind finite sets), which is intended to be an analogue in this situation of Morley rank in model theory. Received: 22 September 2000 / Revised version: 14 May 2002 Published online: 19 December 2002 The research of the first author was supported by the SERC. Mathematics Subject Classification (2000): 03E25 Key words or phrases: Rank – Degree – Amorphous     

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     

Integer linear programming models for 2-staged two-dimensional Knapsack problems

 We are given a unique rectangular piece of stock material S, with height H and width W, and a list of m rectangular shapes to be cut from S. Each shape's type i (i = 1, ..., m) is characterized by a height , a width , a profit , and an upper bound ub _i indicating the maximum number of items of type i which can be cut. We refer to the Two-Dimensional Knapsack (TDK) as the problem of determining a cutting pattern of S maximizing the sum of the profits of the cut items. In particular, we consider the classical variant of TDK in which the maximum number of cuts allowed to obtain each item is fixed to 2, and we refer to this problem as 2-staged TDK (2TDK). For the 2TDK problem we present two new Integer Linear Programming models, we discuss their properties, and we compare them with other formulations in terms of the LP bound they provide. Finally, both models are computationally tested within a standard branch-and-bound framework on a large set of instances from the literature by reinforcing them with the addition of linear inequalities to eliminate symmetries. Received: October 17, 2000 / Accepted: December 19, 2001 Published online: September 27, 2002 Key words. packing – cutting – integer linear programming     

On the polyhedral structure of a multi–item production planning model with setup times

 We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated production planning problems and other fixed charge network flow problems. We analyze the polyhedral structure of the convex hull of this model, as well as of a strengthened LP relaxation. Among other results, we present valid inequalities that induce facets of the convex hull under certain conditions. We also discuss how to strengthen these inequalities by using known results for lifting valid inequalities for 0–1 continuous knapsack problems. Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002 Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network flow Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

A new correctness criterion for multiplicative non-commutative proof nets

 We introduce a new correctness criterion for multiplicative non commutative proof nets which can be considered as the non-commutative counterpart to the Danos-Regnier criterion for proof nets of linear logic. The main intuition relies on the fact that any switching for a proof net (obtained by mutilating one premise of each disjunction link) can be naturally viewed as a series-parallel order variety (a cyclic relation) on the conclusions of the proof net. Received: 8 November 2000 / Revised version: 21 June 2001 / Published online: 2 September 2002 Research supported by the EU TMR Research Programme ``Linear Logic and Theoretical Computer Science'. Mathematics Subject Classification (2000): 03F03, 03F07, 03F52, 03B70 Key words or phrases: Linear and non-commutative logic – Proof nets – Series-parallel orders and order varieties     

Preemptive scheduling with rejection

 We consider the problem of preemptively scheduling a set of n jobs on m (identical, uniformly related, or unrelated) parallel machines. The scheduler may reject a subset of the jobs and thereby incur job-dependent penalties for each rejected job, and he must construct a schedule for the remaining jobs so as to optimize the preemptive makespan on the m machines plus the sum of the penalties of the jobs rejected. We provide a complete classification of these scheduling problems with respect to complexity and approximability. Our main results are on the variant with an arbitrary number of unrelated machines. This variant is APX-hard, and we design a 1.58-approximation algorithm for it. All other considered variants are weakly -hard, and we provide fully polynomial time approximation schemes for them. Finally, we argue that our results for unrelated machines can be carried over to the corresponding preemptive open shop scheduling problem with rejection. Received: October 30, 2000 / Accepted: September 26, 2001 Published online: September 5, 2002 Key words. scheduling – preemption – approximation algorithm – worst case ratio – computational complexity – in-approximability Supported in part by the EU Thematic Network APPOL, Approximation and Online Algorithms, IST-1999-14084 Supported by the START program Y43-MAT of the Austrian Ministry of Science.     

On the capacitated vehicle routing problem

 We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY. Received: October 30, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002 Key words. vehicle routing problem – integer programming – decomposition algorithm – separation algorithm – branch and cut Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

On the separation of split cuts and related inequalities

 The split cuts of Cook, Kannan and Schrijver are general-purpose valid inequalities for integer programming which include a variety of other well-known cuts as special cases. To detect violated split cuts, one has to solve the associated separation problem. The complexity of split cut separation was recently cited as an open problem by Cornuéjols & Li CL01. In this paper we settle this question by proving strong 𝒩𝒫-completeness of separation for split cuts. As a by-product we also show 𝒩𝒫-completeness of separation for several other classes of inequalities, including the MIR-inequalities of Nemhauser and Wolsey and some new inequalities which we call balanced split cuts and binary split cuts. We also strengthen 𝒩𝒫-completeness results of Caprara & Fischetti CF96 (for -cuts) and Eisenbrand E99 (for Chvátal-Gomory cuts). To compensate for this bleak picture, we also give a positive result for the Symmetric Travelling Salesman Problem. We show how to separate in polynomial time over a class of split cuts which includes all comb inequalities with a fixed handle. Received: October 23, 2000 / Accepted: October 03, 2001 Published online: September 5, 2002 Key words. cutting planes – separation – complexity – travelling salesman problem – comb inequalities     

Backward SDEs and Cauchy problem for semilinear equations in divergence form

 We extend the definition of solutions of backward stochastic differential equations to the case where the driving process is a diffusion corresponding to symmetric uniformly elliptic divergence form operator. We show existence and uniqueness of solutions of such equations under natural assumptions on the data and show its connections with solutions of semilinear parabolic partial differential equations in Sobolev spaces. Received: 22 January 2002 / Revised version: 10 September 2002 / Published online: 19 December 2002 Research supported by KBN Grant 0253 P03 2000 19. Mathematics Subject Classification (2002): Primary 60H30; Secondary 35K55 Key words or phrases: Backward stochastic differential equation – Semilinear partial differential equation – Divergence form operator – Weak solution     

Solving Problems with Semidefinite and Related Constraints Using Interior-Point Methods for Nonlinear Programming

 In this paper, we describe how to reformulate a problem that has second-order cone and/or semidefiniteness constraints in order to solve it using a general-purpose interior-point algorithm for nonlinear programming. The resulting problems are smooth and convex, and numerical results from the DIMACS Implementation Challenge problems and SDPLib are provided. Received: March 10, 2001 / Accepted: January 18, 2002 Published online: September 27, 2002 Key Words. semidefinite programming – second-order cone programming – interior-point methods – nonlinear programming Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

On the infinite divisibility of squared Gaussian processes

 We show that fractional Brownian motions with index in (0,1] satisfy a remarkable property: their squares are infinitely divisible. We also prove that a large class of Gaussian processes are sharing this property. This property then allows the construction of two-parameters families of processes having the additivity property of the squared Bessel processes. Received: 1 April 2002 / Revised version: 7 September 2002 / Published online: 19 December 2002 Mathematics Subject Classification (2000): 60E07, 60G15, 60J25, 60J55 Key words or phrases: Gaussian processes – Infinite divisibility – Markov processes     

Refined common knowledge logics or logics of common information

 In terms of formal deductive systems and multi-dimensional Kripke frames we study logical operations know, informed, common knowledge and common information. Based on [6] we introduce formal axiomatic systems for common information logics and prove that these systems are sound and complete. Analyzing the common information operation we show that it can be understood as greatest open fixed points for knowledge formulas. Using obtained results we explore monotonicity, omniscience problem, and inward monotonocity, describe their connections and give dividing examples. Also we find algorithms recognizing these properties for some particular cases. Received: 21 October 2000 / Published online: 2 September 2002 Key words or phrases: Multi-agent systems – Non-standard logic – Knowledge representation – Common knowledge – Common information – Fixed points, Kripke models – Modal logic