Orbital branching

We introduce orbital branching, an effective branching method for integer programs containing a great deal of symmetry. The method is based on computing groups of variables that are equivalent with respect to the symmetry remaining in the problem after branching, including symmetry that is not present at the root node. These groups of equivalent variables, called orbits, are used to create a valid partitioning of the feasible region that significantly reduces the effects of symmetry while still allowing a flexible branching rule. We also show how to exploit the symmetries present in the problem to fix variables throughout the branch-and-bound tree. Orbital branching can easily be incorporated into standard integer programming software. Through an empirical study on a test suite of symmetric integer programs, the question as to the most effective orbit on which to base the branching decision is investigated. The resulting method is shown to be quite competitive with a similar method known as isomorphism pruning and significantly better than a state-of-the-art commercial solver on symmetric integer programs.     

Information-theoretic approaches to branching in search

Deciding what question to branch on at each node is a key element of search algorithms. In this paper, we describe a collection of techniques for branching decisions that are motivated from an information-theoretic perspective. The idea is to drive the search to reduce the uncertainty (entropy) in the current subproblem. We present four families of methods for branch question selection in mixed integer programming that use this idea. In the first, a variable to branch on is selected based on lookahead. This method performs comparably to strong branching on MIPLIB, and better than strong branching on hard real-world procurement optimization instances on which CPLEX’s default strong branching outperforms CPLEX’s default branching strategy. The second family combines this idea with strong branching. The third family does not use lookahead, but instead exploits the tie between indicator variables and the variables they govern. This significantly outperforms the state-of-the-art branching strategies on both combinatorial procurement problems and facility location problems. The fourth family concerns branching using carefully constructed linear inequality constraints over sets of variables.     

Continuous state branching semigroups

Summary This paper is concerned with Markov processes with continuous creation where the phase space is a general separable compact metric space. The transition probabilities for such a process determine a semigroup of operators acting on a function space over the collection of bounded Borel measures on the phase space. Such a semigroup is characterized by a particular convolution condition and is called a continuous state branching semigroup. A connection is established between continuous state branching semigroups and certain semigroups of nonlinear operators and then this connection is exploited to establish an existence theorem for the former.Research associated with a project in probability at Princeton University supported by the Office of Army Research.     

Local branching

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box ``tactical' tool to explore effectively suitable solution subspaces defined and controlled at a ``strategic' level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. Mathematics Subject Classification (2000):90C06, 90C10, 90C11, 90C27, 90C59     

A simple branching scheme for vertex coloring problems

We present a branching scheme for some vertex coloring problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as graph multicoloring, where each vertex requires a multiplicity of colors, graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, which generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the effectiveness of the new branching scheme.     

Critical Bellman-Harris branching processes with long-living particles

A critical indecomposable two-type Bellman-Harris branching process is considered in which the life-length of the first-type particles has finite variance while the tail of the life-length distribution of the second-type particles is regularly varying at infinity with parameter β ∈ (0, 1]. It is shown that, contrary to the critical indecomposable Bellman-Harris branching processes with finite variances of the life-lengths of particles of both types, the probability of observing first-type particles at a distant moment t is infinitesimally less than the survival probability of the whole process. In addition, a Yaglom-type limit theorem is proved for the distribution of the number of the first-type particles at moment t given that the population contains particles of the first type at this moment.     

Convergence of branching transport processes to branching brownian motion

Two models are given of branching transport processes that converge to branching Brownian motion starting with one initial particle. The martingale problem method is used.     

Toric degeneration of branching algebras

For each classical symmetric pair (G,H), there is a naturally defined multi-graded algebra , called the branching algebra for (G,H), which encodes the branching rule from G to H. This algebra has a natural family of subalgebras, depending on integer parameters. For a certain range of the parameters, the subalgebras have a particularly simple structure and are called stable branching algebras.In this paper, we show that the stable branching algebras for eight out of the ten families of classical symmetric pairs are flat deformations of the semigroup algebras of explicitly described lattice cones.     

Limit distributions arising in branching random walks on integer lattices

The paper completes the investigation of limit distribution of the number of particles at the source of branching in the model of critical catalytic branching random walk on ^dd N {{\mathbb Z}^d}\;d \in {\mathbb N} . Limit theorems of such kind were established only for d = 1, 2, 3, 4 under the assumption that, at the initial moment, there is a single particle at the source of branching. We prove their analog for d \geqslant 5 d \geqslant 5 . Moreover, in any dimension, we generalize the previous results by permitting the initial particle to start at an arbitrary point of the lattice.     

Statistical estimation in a randomly structured branching population

We consider a binary branching process structured by a stochastic trait that evolves according to a diffusion process that triggers the branching events, in the spirit of Kimmel’s model of cell division with parasite infection. Based on the observation of the trait at birth of the first $n$ generations of the process, we construct nonparametric estimator of the transition of the associated bifurcating chain and study the parametric estimation of the branching rate. In the limit $n\to \infty$, we obtain asymptotic efficiency in the parametric case and minimax optimality in the nonparametric case.     

Sesqui-type branching processes

We consider branching processes consisting of particles (individuals) of two types (type $L$ and type $S$) in which only particles of type $L$ have offspring, proving estimates for the survival probability and the (tail of) the distribution of the total number of particles. Such processes are in some sense closer to single- than to multi-type branching processes. Nonetheless, the second, barren, type complicates the analysis significantly. The results proved here (about point and survival probabilities) are a key ingredient in the analysis of bounded-size Achlioptas processes in a recent paper by the last two authors.     

A continuous-state polynomial branching process

A continuous-state polynomial branching process is constructed as the pathwise unique solution of a stochastic integral equation with absorbing boundary condition. The process can also be obtained from a spectrally positive Lévy process through Lamperti type transformations. The extinction and explosion probabilities and the mean extinction and explosion times are computed explicitly. Some of those are also new for the classical linear branching process. We present necessary and sufficient conditions for the process to extinguish or explode in finite times. In the critical or subcritical case, we give a construction of the process coming down from infinity. Finally, it is shown that the continuous-state polynomial branching process arises naturally as the rescaled limit of a sequence of discrete-state processes.     

Scenery reconstruction with branching random walk

We study the problem of scenery reconstruction in arbitrary dimension using observations registered in boxes of size k (for k fixed), seen along a branching random walk. We prove that, using a large enough k for almost all the realizations of the branching random walk, almost all sceneries can be reconstructed up to equivalence.     

Large scale localization of a spatial version of Neveu’s branching process

Recently a spatial version of Neveu’s (1992) continuous-state branching process was constructed by Fleischmann and Sturm (2004). This superprocess with infinite mean branching behaves quite differently from usual supercritical spatial branching processes. In fact, at macroscopic scales, the mass renormalized to a (random) probability measure is concentrated in a single space point which randomly fluctuates according to the underlying symmetric stable motion process.     

Continuous branching processes and spectral positivity

Certain properties of continuous-state branching processes are studied via the random time-change linking them with spectrally positive Lévy processes. The results are compared and contrasted with those for simple branching processes.     

Limit distributions for the number of particles in branching random walks

We study branching random walks with continuous time. Particles performing a random walk on ?², are allowed to be born and die only at the origin. It is assumed that the offspring reproduction law at the branching source is critical and the random walk outside the source is homogeneous and symmetric. Given particles at the origin, we prove a conditional limit theorem for the joint distribution of suitably normalized numbers of particles at the source and outside it as time unboundedly increases. As a consequence, we establish the asymptotic independence of such random variables.     

The monotonicity of the probability of return into the source in models of branching random walks

The paper discusses two models of a branching random walk on a many-dimensional lattice with birth and death of particles at a single node being the source of branching. The random walk in the first model is assumed to be symmetric. In the second model an additional parameter is introduced which enables “artificial” intensification of the prevalence of branching or walk at the source and, as the result, violating the symmetry of the random walk. The monotonicity of the return probability into the source is proved for the second model, which is a key property in the analysis of branching random walks.     

Small solutions of nonlinear differential equations near branching points

We construct parametric families of small branching solutions to nonlinear differential equations of the nth order near branching points. We use methods of the analytical theory of branching solutions of nonlinear equations and the theory of differential equations with a regular singular point. We illustrate the general existence theorems with an example of a nonlinear differential equation in a certain magnetic insulation problem.     

Lower-order branching and conjugate function discontinuities

An example is given of a fourth-order linear ordinary differential operator K on (? ∞, ∞) for which the higher-order conjugate point functions η₂ and η₃ are discontinuous. Introduced to settle the issue of discontinuity are the notions of lower-order branching and degenerate branching of boundary value problems of de la Vallée-Poussin type.     

On branching index of algebraic extension spectrum points

The paper studies the branching A-index and the topological branching index of points of the spectrum of Arens-Hoffman algebraic extension of a semisimple commutative Banach algebras A.