Parametric integer linear programming: A synthesis of branch and bound with cutting planes

A branch and bound algorithm is designed to solve the general integer linear programming problem with parametric right-hand sides. The right-hand sides have the form b + θd where b and d are comformable vectors, d consists of nonnegative constants, and θ varies from zero to one.The method consists of first determining all possible right-hand side integer constants and appending this set of integer constants to the initial tableau to form an expanded problem with a finite number of family members. The implicit enumeration method gives a lower bound on the integer solutions. The branch and bound method is used with fathoming tests which allow one family member possibly to fathom other family members. A cutting plane option applies a finite number of cuts to each node before branching. In addition, the cutting plane method is invoked whenever some members are feasible at a node and others are infeasible. The branching and cutting process is repeated until the entire family of problem has been solved.     

A Galerkin Approximation for the Initial-Value Problem for Linear Second-Order Differential Equations

In this paper, a Galerkin type algorithm is given for the numerical solution of L(x)=(r(t)x'(t))'-p(t)x(t)=g(t); x(a)=x_a, x'(a)=x'_a, where r (t)>f0, and Spline hat functions form the approximating basis. Using the related quadratic form, a two-step difference equation is derived for the numerical solutions. A discrete Gronwall type lemma is then used to show that the error at the node points satisfies e_k=0(h²). If e(t) is the error function on a?t?b; it is also shown (in a variety of norms) that e(t)?Ch² and e'(t)?C₁h. Test case runs are also included. A (one step) Richardson or Rhomberg type procedure is used to show that e^R_k=0(h⁴). Thus our results are comparable to Runge-Kutta with half the function evaluations.     

Quantitative stability of mixed-integer two-stage quadratic stochastic programs

For our introduced mixed-integer quadratic stochastic program with fixed recourse matrices, random recourse costs, technology matrix and right-hand sides, we study quantitative stability properties of its optimal value function and optimal solution set when the underlying probability distribution is perturbed with respect to an appropriate probability metric. To this end, we first establish various Lipschitz continuity results about the value function and optimal solutions of mixed-integer parametric quadratic programs with parameters in the linear part of the objective function and in the right-hand sides of linear constraints. The obtained results extend earlier results about quantitative stability properties of stochastic integer programming and stability results for mixed-integer parametric quadratic programs.     

Small time two-sided LIL behavior for Lévy processes at zero

We wish to characterize when a Lévy process X _t crosses boundaries b(t), in a two-sided sense, for small times t, where b(t) satisfies very mild conditions. An integral test is furnished for computing the value of sup _t→0|X _t |/b(t) = c. In some cases, we also specify a function b(t) in terms of the Lévy triplet, such that sup _t→0 |X _t |/b(t) = 1.     

Multiplicative representations of integers

Lehh ≧ 2, and let ?=(B ₁, …,B _h ), whereB ₁ ? N={1, 2, 3, …} fori=1, …,h. Denote by g_?(n) the number of representations ofn in the formn=b ₁ …b _h , whereb _i ∈B _i . If v (n) > 0 for alln >n ₀, then ? is anasymptotic multiplicative system of order h. The setB is anasymptotic multiplicative basis of order h ifn=b ₁ …b _n is solvable withb _i ∈B for alln >n ₀. Denote byg(n) the number of such representations ofn. LetM(h) be the set of all pairs (s, t), wheres=lim g_? (n) andt=lim g_? (n) for some multiplicative system ? of orderh. It is proved that {fx129-1} In particular, it follows thats ≧ 2 impliest=∞. A corollary is a theorem of Erdös that ifB is a multiplicative basis of orderh ≧ 2, then lim g_? g(n)=∞. Similar results are obtained for asymptotic union bases of finite subsets of N and for asymptotic least common multiple bases of integers.     

Isolated singularities for weighted quasilinear elliptic equations

We classify all the possible asymptotic behavior at the origin for positive solutions of quasilinear elliptic equations of the form div(|∇u|^p−2∇u)=b(x)h(u) in Ω?{0}, where 1<p?N and Ω is an open subset of RN with 0∈Ω. Our main result provides a sharp extension of a well-known theorem of Friedman and Véron for h(u)=uq and b(x)≡1, and a recent result of the authors for p=2 and b(x)≡1. We assume that the function h is regularly varying at ∞ with index q (that is, limt→∞h(λt)/h(t)=λq for every λ>0) and the weight function b(x) behaves near the origin as a function b₀(|x|) varying regularly at zero with index θ greater than −p. This condition includes b(x)=θ|x| and some of its perturbations, for instance, b(x)=θ|x|m(−log|x|) for any m∈R. Our approach makes use of the theory of regular variation and a new perturbation method for constructing sub- and super-solutions.     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

Differentiation formulas for stochastic integrals in the plane

For a one-parameter process of the form X_t=X₀+∫^t₀φ_sdW_s+∫^t₀ψ_sds, where W is a Wiener process and ∫φdW is a stochastic integral, a twice continuously differentiable function f(X_t) is again expressible as the sum of a stochastic integral and an ordinary integral via the Ito differentiation formula. In this paper we present a generalization for the stochastic integrals associated with a two-parameter Wiener process.Let {W₂, z∈R²₊} be a Wiener process with a two-dimensional parameter. Ertwhile, we have defined stochastic integrals ∫ φdWand ∫ψdWdW, as well as mixed integrals ∫h dz dW and ∫gdW dz. Now let X_z be a two-parameter process defined by the sum of these four integrals and an ordinary Lebesgue integral. The objective of this paper is to represent a suitably differentiable function f(X_z) as such a sum once again. In the process we will also derive the (basically one-dimensional) differentiation formulas of f(X_z) on increasing paths in $\text{R}{}^2{}_{\mathrm{+}}$.     

On the total multiplicity of zeros of generalized polynomials related to nonoscillating trajectories

For a continuous curve L = {x: x = Z(t), t ∈ [a, b]} in R ⁿ , we study the number of zeros of the function l _h (t) = 〈h, Z(t)〉, where h ∈ R ⁿ . We introduce the notion of multiple zeros for such functions and study the possibility of estimating the total multiplicity of such zeros under the assumption that the system {z ₁(t), z ₂(t), …, z _n (t)} of coordinates of the function Z(t) is a Chebyshev system on [a, b].     

Diffusion approximations of age-and-position dependent branching processes

By a (G, F, h) age-and-position dependent branching process we mean a process in which individuals reproduce according to an age dependent branching process with age distribution function G(t) and offspring distribution generating function F, the individuals (located in R^N) can not move and the distance of a new individual from its parent is governed by a probability density function h(r). For each positive integer n, let Z_n(t,dx) be the number of individuals in dx at time t of the (G, F_n,h_n) age-and-position dependent branching process. It is shown that under appropriate conditions on G, F_n and h_n, the finite dimensional distribution of $\text{Z}{}_{\mathrm{n}}\text{(nt, dx)}\text{n}$ converges, as n → ∞, to the corresponding law of a diffusion continuous state branching process X(t,dx) determined by a ψ-semigroup {ψ_t: t ? 0}. The ψ-semigroup {ψ_t} is the solution of a non-linear evolution equation. A semigroup convergence theorem due to Kurtz [10], which gives conditions for convergence in distribution of a sequence of non-Markovian processes to a Markov process, provides the main tools.     

Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse

For mixed-integer quadratic program where all coefficients in the objective function and the right-hand sides of constraints vary simultaneously, we show locally Lipschitz continuity of its optimal value function, and derive the corresponding global estimation; furthermore, we also obtain quantitative estimation about the change of its optimal solutions. Applying these results to two-stage quadratic stochastic program with mixed-integer recourse, we establish quantitative stability of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. The obtained results generalize available results on continuity properties of mixed-integer quadratic programs and extend current results on quantitative stability of two-stage quadratic stochastic programs with mixed-integer recourse.     

Feasibility in reverse convex mixed-integer programming

In this paper we address the problem of the infeasibility of systems defined by reverse convex inequality constraints, where some or all of the variables are integer. In particular, we provide a polynomial algorithm that identifies a set of all constraints critical to feasibility (CF), that is constraints that may affect a feasibility status of the system after some perturbation of the right-hand sides. Furthermore, we will investigate properties of the irreducible infeasible sets and infeasibility sets, showing in particular that every irreducible infeasible set as well as infeasibility sets in the considered system, are subsets of the set CF of constraints critical to feasibility.     

Approximations from Subspaces of C0(X)

We show among other things that if B is a linear space of continuous real-valued functions vanishing at infinity on a locally compact Hausdorff space X, for which there is a continuous function h defined in a neighbourhood of 0 in the real line which is non-affine in every neighbourhood of 0 and satisfies |h(t)|k |t| for all t, such that hb is in B whenever b is in B and the composite function is defined, then every function in C₀(X) which can be approximated on every pair of points in X by functions in B can be approximated uniformly by functions in B.     

Optimal control of capital injections by reinsurance in a diffusion approximation

In this paper we consider a diffusion approximation to a classical risk process, where the claims are reinsured by some reinsurance with deductible b ∈ [0,b?], where b = b? means “no reinsurance” and b = 0 means “full reinsurance”. The cedent can choose an adapted reinsurance strategy (b _t ) _{t ≥0}, i.?e. the deductible can be changed continuously. In addition, the cedent has to inject fresh capital in order to keep the surplus positive. The problem is to minimise the expected discounted cost over all admissible reinsurance strategies. We find an explicit expression for the value function and the optimal strategy using the Hamilton–Jacobi–Bellman approach. Some examples illustrate the method.     

Self-adjusting stochastic processes

Let A_t(i, j) be the transition matrix at time t of a process with n states. Such a process may be called self-adjusting if the occurrence of the transition from state h to state k at time t results in a change in the hth row such that A_t+1(h, k) ? A_t(h, k). If the self-adjustment (due to transition h → kx) is A_{t + 1}(h, j) = λA_t(h, j) + (1 ? λ)δ_jk (0 < λ < 1), then with probability 1 the process is eventually periodic. If A₀(i, j) < 1 for all i, j and if the self-adjustment satisfies A_{t + 1}(h, k) = ?(A_t(h, k)) with ?(x) twice differentiable and increasing, x < ?(x) < 1 for 0 ? x < 1,?(1) = ?′(1) = 1, then, with probability 1, lim A_t does not exist.     

Quantitative Stability Analysis of Two-Stage Stochastic Linear Programs with Full Random Recourse

Abstract

In this paper, we apply the parametric linear programing technique and pseudo metrics to study the quantitative stability of the two-stage stochastic linear programing problem with full random recourse. Under the simultaneous perturbation of the cost vector, coefficient matrix, and right-hand side vector, we first establish the locally Lipschitz continuity of the optimal value function and the boundedness of optimal solutions of parametric linear programs. On the basis of these results, we deduce the locally Lipschitz continuity and the upper bound estimation of the objective function of the two-stage stochastic linear programing problem with full random recourse. Then by adopting different pseudo metrics, we obtain the quantitative stability results of two-stage stochastic linear programs with full random recourse which improve the current results under the partial randomness in the second stage problem. Finally, we apply these stability results to the empirical approximation of the two-stage stochastic programing model, and the rate of convergence is presented.     

A note on the MIR closure and basic relaxations of polyhedra

Anderson et al. (2005) [1] show that for a polyhedral mixed integer set defined by a constraint system Ax≥b, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a basic relaxation, i.e., one defined by a subset of linearly independent constraints. This result implies that any split cut can be obtained as an intersection cut. Equivalence between split cuts obtained from simple disjunctions of the form x_j≤0 or x_j≥1 and intersection cuts was shown earlier for 0/1-mixed integer sets by Balas and Perregaard (2002) [4]. We give a short proof of the result of Anderson, Cornuéjols and Li using the equivalence between mixed integer rounding (MIR) cuts and split cuts.     

Stability of multistage stochastic programming

In this paper, we study the stability of multistage stochastic programming with recourse in a way that is different from that used in studying stability of two-stage stochastic programs. Here, we transform the multistage programs into mathematical programs in the space ⁿ ×L _p with a simple objective function and multistage stochastic constraints. By investigating the continuity of the multistage multifunction defined by the multistage stochastic constraints and applying epi-convergence theory we obtain stability results for linear and linear-quadratic multistage stochastic programs.Project supported by the National Natural Science Foundation of China.     

On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming

We present a framework for solving large-scale multistage mixed 0–1 optimization problems under uncertainty in the coefficients of the objective function, the right-hand side vector, and the constraint matrix. A scenario tree-based scheme is used to represent the Deterministic Equivalent Model of the stochastic mixed 0–1 program with complete recourse. The constraints are modeled by a splitting variable representation via scenarios. So, a mixed 0–1 model for each scenario cluster is considered, plus the nonanticipativity constraints that equate the 0–1 and continuous so-called common variables from the same group of scenarios in each stage. Given the high dimensions of the stochastic instances in the real world, it is not realistic to obtain the optimal solution for the problem. Instead we use the so-called Fix-and-Relax Coordination (FRC) algorithm to exploit the characteristics of the nonanticipativity constraints of the stochastic model. A mixture of the FRC approach and the Lagrangian Substitution and Decomposition schemes is proposed for satisfying, both, the integrality constraints for the 0–1 variables and the nonanticipativity constraints. This invited paper is discussed in the comments available at: doi:, doi:, doi:, doi:.