Comparing constraint programming and mathematical programming approaches to discrete optimisation—the change problem

This paper is aimed at researchers and practitioners in Operational Research who are interested in the new field of Constraint Programming/Constraint Logic Programming. Due to differing terminology and problem representation they might have found it difficult to access the field. The paper focuses on discrete optimisation problems. The first part lists frequently used terms in Constraint Programming (CP), contrasting them with their counterparts in Mathematical Programming (MP). The second part explains some of the most important concepts and techniques in more detail by comparing the CP and MP implementations of a small example problem, the ‘Change Problem’. It includes an overview of the respective results. In conclusion a more generalised comparison of CP and MP techniques is given.     

Finite-Temperature Coarse-Graining of One-Dimensional Models: Mathematical Analysis and Computational Approaches

We present a possible approach for the computation of free energies and ensemble averages of one-dimensional coarse-grained models in materials science. The approach is based upon a thermodynamic limit process, and makes use of ergodic theorems and large deviations theory. In addition to providing a possible efficient computational strategy for ensemble averages, the approach allows for assessing the accuracy of approximations commonly used in practice.     

Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints

We consider the generalized Nash equilibrium problem (GNEP), in which each player’s strategy set may depend on the rivals’ strategies through shared constraints. A practical approach to solving this problem that has received increasing attention lately entails solving a related variational inequality (VI). From the viewpoint of game theory, it is important to find as many GNEs as possible, if not all of them. We propose two types of parametrized VIs related to the GNEP, one price-directed and the other resource-directed. We show that these parametrized VIs inherit the monotonicity properties of the original VI and, under mild constraint qualifications, their solutions yield all GNEs. We propose strategies to sample in the parameter spaces and show, through numerical experiments on benchmark examples, that the GNEs found by the parametrized VI approaches are widely distributed over the GNE set.     

Exact approaches for integrated aircraft fleeting and routing at TunisAir

We describe models and exact solutions approaches for an integrated aircraft fleeting and routing problem arising at TunisAir. Given a schedule of flights to be flown, the problem consists of determining a minimum cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenance activity constraints. We investigate two tailored approaches for this problem: Benders decomposition and branch-and-price. Computational experiments conducted on real-data provide evidence that the branch-and-price approach outperforms the Benders decomposition approach and delivers optimal solutions within moderate CPU times. On the other hand, the Benders algorithm yields very quickly high quality near-optimal solutions.     

Tools of mathematical modeling of arbitrary object packing problems

The article reviews the concept of and further develops phi-functions (Φ-functions) as an efficient tool for mathematical modeling of two-dimensional geometric optimization problems, such as cutting and packing problems and covering problems. The properties of the phi-function technique and its relationship with Minkowski sums and the nofit polygon are discussed. We also describe the advantages of phi-functions over these approaches. A clear definition of the set of objects for which phi-functions may be derived is given and some exceptions are illustrated. A step by step procedure for deriving phi-functions illustrated with examples is provided including the case of continuous rotation.     

Some Inequalities Related to Transience and Recurrence of Markov Processes and Their Applications

For an irreducible symmetric Markov process on a (not necessarily compact) state space associated with a symmetric Dirichlet form, we give Poincaré-type inequalities. As an application of the inequalities, we consider a time-inhomogeneous diffusion process obtained by a time-dependent drift transformation from a diffusion process and give general conditions for the transience or recurrence of some sets. As a particular case, the diffusion process appearing in the theory of simulated annealing is considered.     

Wine and maths: mathematical solutions to wine–inspired problems

We deal with an application of partial differential equations to the correct definition of a wine cellar. We present some historical details about this problem. We also discuss how to build or renew a wine cellar, creating ideal conditions for the ageing process and improving the quality of wines. Our goal is to calculate the optimal depth z₀ of a wine cellar in order to attenuate the periodic temperature fluctuations. What follows is a kind of survey of wine-related and optimization problems which have been solved by means of powerful math tools.     

A Sampling-and-Discarding Approach to Chance-Constrained Optimization: Feasibility and Optimality

In this paper, we study the link between a Chance-Constrained optimization Problem (CCP) and its sample counterpart (SP). SP has a finite number, say N, of sampled constraints. Further, some of these sampled constraints, say k, are discarded, and the final solution is indicated by x^*_N,kx^{ast}_{N,k}. Extending previous results on the feasibility of sample convex optimization programs, we establish the feasibility of x^*_N,kx^{ast}_{N,k} for the initial CCP problem.     

On the Wave Equation Associated to the Hermite and the Twisted Laplacian

The dispersive properties of the wave equation u _tt +Au=0 are considered, where A is either the Hermite operator −Δ+|x|² or the twisted Laplacian −(∇ _x −iy)²/2−(∇ _y +ix)²/2. In both cases we prove optimal L ¹−L ^∞ dispersive estimates. More generally, we give some partial results concerning the flows exp (itL ^ν ) associated to fractional powers of the twisted Laplacian for 0<ν<1.     

Symmetric and quasi-symmetric functions associated to polymatroids

To every subspace arrangement X we will associate symmetric functions ℘[X] and ℋ[X]. These symmetric functions encode the Hilbert series and the minimal projective resolution of the product ideal associated to the subspace arrangement. They can be defined for discrete polymatroids as well. The invariant ℋ[X] specializes to the Tutte polynomial . Billera, Jia and Reiner recently introduced a quasi-symmetric function ℱ[X] (for matroids) which behaves valuatively with respect to matroid base polytope decompositions. We will define a quasi-symmetric function for polymatroids which has this property as well. Moreover, specializes to ℘[X], ℋ[X], and ℱ[X]. The author is partially supported by the NSF, grant DMS 0349019.     

Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds

Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that the objective function is continuously differentiable and that the points of the level set have at least one component strictly between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model.     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.     

Matrix Extension with Symmetry and Applications to Symmetric Orthonormal Complex M-wavelets

Matrix extension with symmetry is to find a unitary square matrix P of 2π-periodic trigonometric polynomials with symmetry such that the first row of P is a given row vector p of 2π-periodic trigonometric polynomials with symmetry satisfying p[`(p)]^T=1\mathbf {p}\overline{\mathbf{p}}^{T}=1 . Matrix extension plays a fundamental role in many areas such as electronic engineering, system sciences, wavelet analysis, and applied mathematics. In this paper, we shall solve matrix extension with symmetry by developing a step-by-step simple algorithm to derive a desired square matrix P from a given row vector p of 2π-periodic trigonometric polynomials with complex coefficients and symmetry. As an application of our algorithm for matrix extension with symmetry, for any dilation factor M, we shall present two families of compactly supported symmetric orthonormal complex M-wavelets with arbitrarily high vanishing moments. Wavelets in the first family have the shortest possible supports with respect to their orders of vanishing moments; their existence relies on the establishment of nonnegativity on the real line of certain associated polynomials. Wavelets in the second family have increasing orders of linear-phase moments and vanishing moments, which are desirable properties in numerical algorithms.     

A Differential Game Related to Terrorism: Nash and Stackelberg Strategies

The question of how best to prosecute the ‘war on terror’ leads to strategic interaction in an intertemporal setting. We consider a nonzero sum differential game between a government and a terrorist organisation. Due to the state-separability of the game we are able to determine Nash and Stackelberg solutions in analytic form. Their comparison as well as the sensitivity analysis deliver interesting insight into the design of efficient measures to combat terror.     

Introduction to the theory and applications of uncertainty

We introduce the special volume “The theory and applications of uncertainty”.     

Stable-Range Approach to Short Wave and Khokhlov-Zabolotskaya Equations

Short wave equations were introduced in connection with the nonlinear reflection of weak shock waves. They also relate to the modulation of a gas-fluid mixture. Khokhlov-Zabolotskaya equation is used to describe the propagation of a diffraction sound beam in a nonlinear medium. We give a new algebraic method of solving these equations by using certain finite-dimensional stable range of the nonlinear terms and obtain large families of new explicit exact solutions parameterized by several functions for them. These parameter functions enable one to find the solutions of some related practical models and boundary value problems. Research supported by China NSF 10871193.     

Exterior Differential Systems Prolongations and Application to a Study of Two Nonlinear Partial Differential Equations

A generalized Korteweg-de Vries equation is formulated as an exterior differential system, which is used to determine the prolongation structure of the equation. The prolongation structure is obtained for several cases of the variable powers, and nontrivial algebras are determined. The analysis is extended to a differential system which gives the Camassa-Holm equation as a particular case. The subject of conservation laws is briefly discussed for each of the equations. A Bäcklund transformation is determined using one of the prolongations.     

Inexact Josephy–Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization

We propose and analyze a perturbed version of the classical Josephy–Newton method for solving generalized equations. This perturbed framework is convenient to treat in a unified way standard sequential quadratic programming, its stabilized version, sequential quadratically constrained quadratic programming, and linearly constrained Lagrangian methods. For the linearly constrained Lagrangian methods, in particular, we obtain superlinear convergence under the second-order sufficient optimality condition and the strict Mangasarian–Fromovitz constraint qualification, while previous results in the literature assume (in addition to second-order sufficiency) the stronger linear independence constraint qualification as well as the strict complementarity condition. For the sequential quadratically constrained quadratic programming methods, we prove primal-dual superlinear/quadratic convergence under the same assumptions as above, which also gives a new result.     

On the mathematical formulation of the problem of reassembling fragmented objects: two new theorems

In this paper two new theorems are proved in association with the problem of matching three dimensional solid bodies. Rigorous mathematical criteria are given in order to test if two such bodies actually match in a certain position. Since this problem finds important application to the actual problem of reassembling fragmented objects e.g. archaeological, special care is taken to account for small gaps between matching fragments and fuzziness of the matching parameters.