Decision-theoretic harmony: A first step

This paper presents a novel harmony generation method based on decision-theoretic planning. We are the first to model music generation using Markov decision processes (MDPs). We give a proof of concept for this approach by using MDP planning to generate four-part harmony, given the melody or soprano line. Our initial results show feasibility, and show the variance possible, depending on the choice of reward functions.     

A Differential Free Point Generation Scheme in the Differential Evolution Algorithm

In this paper we derive the probability distribution of trial points in the differential evolution (de) algorithm, in particular the probability distribution of points generated by mutation. We propose a point generation scheme that uses an approximation to this distribution. The scheme can dispense with the differential vector used in the mutation of de. We propose a de algorithm that replaces the differential based mutation scheme with a probability distribution based point generation scheme. We also propose a de algorithm that uses a probabilistic combination of the point generation by the probability distribution and the point generation by mutation. A numerical study is carried out using a set of 50 test problems, many of which are inspired by practical applications. Numerical results suggest that the new algorithms are superior to the original version both in terms of the number of function evaluations and cpu times.     

A note on “A LP-based heuristic for a time-constrained routing problem”

In their paper, Avella et al. (2006) investigate a time-constrained routing problem. The core of the proposed solution approach is a large-scale linear program that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this linear program optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate by using Lagrangian duality that this optimality condition is incorrect and may lead to a suboptimal solution at termination.     

Some Variants of the Controlled Random Search Algorithm for Global Optimization

We suggested some modifications to the controlled random search (CRS) algorithm for global optimization. We introduce new trial point generation schemes in CRS, in particular, point generation schemes using linear interpolation and mutation. Central to our modifications is the probabilistic adaptation of point generation schemes within the CRS algorithm.A numerical study is carried out using a set of 50 test problems many of which are inspired by practical applications. Numerical experiments indicate that the resulting algorithms are considerably better than the previous versions. Thus, they offer a reasonable alternative to many currently available stochastic algorithms, especially for problems requiring direct search type methods.     

Integrating column generation in a method to compute a discrete representation of the non-dominated set of multi-objective linear programmes

In this paper we propose the integration of column generation in the revised normal boundary intersection (RNBI) approach to compute a representative set of non-dominated points for multi-objective linear programmes (MOLPs). The RNBI approach solves single objective linear programmes, the RNBI subproblems, to project a set of evenly distributed reference points to the non-dominated set of an MOLP. We solve each RNBI subproblem using column generation, which moves the current point in objective space of the MOLP towards the non-dominated set. Since RNBI subproblems may be infeasible, we attempt to detect this infeasibility early. First, a reference point bounding method is proposed to eliminate reference points that lead to infeasible RNBI subproblems. Furthermore, different initialisation approaches for column generation are implemented, including Farkas pricing. We investigate the quality of the representation obtained. To demonstrate the efficacy of the proposed approach, we apply it to an MOLP arising in radiotherapy treatment design. In contrast to conventional optimisation approaches, treatment design using column generation provides deliverable treatment plans, avoiding a segmentation step which deteriorates treatment quality. As a result total monitor units is considerably reduced. We also note that reference point bounding dramatically reduces the number of RNBI subproblems that need to be solved.     

Numerical simulations for the contraction flow using grid generation

We study the incomprssible Navier Stokes equations for the flow inside contraction geometry. The governing equations are expressed in the vorticity-stream function formulations. A rectangular computational domain is arised by elliptic grid generation technique. The numerical solution is based on a technique of automatic numerical generation of acurvilinear coordinate system by transforming the governing equation into computational plane. The transformed equations are approximated using central differences and solved simultaneously by successive over relaxation iteration. The time dependent of the vorticity equation solved by using explicit marching procedure. We will apply the technique on several irregularshapes.     

Stochastic Domain Decomposition for Time Dependent Adaptive Mesh Generation

The efficient generation of meshes is an important component in the numerical solution of problems in physics and engineering. Of interest are situations where global mesh quality and a tight coupling to the solution of the physical partial differential equation (PDE) is important. We consider parabolic PDE mesh generation and present a method for the construction of adaptive meshes in two spatial dimensions using stochastic domain decomposition that is suitable for an implementation in a multi- or many-core environment. Methods for mesh generation on periodic domains are also provided. The mesh generator is coupled to a time dependent physical PDE and the system is evolved using an alternating solution procedure. The method uses the stochastic representation of the exact solution of a parabolic linear mesh generator to find the location of an adaptive mesh along the (artificial) subdomain interfaces. The deterministic evaluation of the mesh over each subdomain can then be obtained completely independently using the probabilistically computed solutions as boundary conditions. A small scaling study is provided to demonstrate the parallel performance of this stochastic domain decomposition approach to mesh generation. We demonstrate the approach numerically and compare the mesh obtained with the corresponding single domain mesh using a representative mesh quality measure.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

Utilitarianism,prioritarianism, and intergenerational equity: A cake eating model

We use a simple consumption model, the so-called cake eating model, to study the interaction of equity, time and risk in social decision making. Total consumption, the “cake”, is uncertain. The social planner allocates consumption between two agents (representing two generations), by assigning the first a determinate amount, with the second receiving the risky remainder. We study this consumption allocation decision using three social welfare functions: utilitarianism, ex ante prioritarianism, and ex post prioritarianism. Under standard assumptions, ex ante prioritarianism allocates more consumption to the first generation than utilitarianism. Thus, a concern for equity, in the ex ante prioritarian sense, means less concern for the risky future. By contrast, ex post prioritarianism normally chooses less consumption for the first generation than utilitarianism. We discuss the robustness of these optimal consumption allocations to learning and to more complicated social welfare functions.     

Generation of interfaces for Lotka-Volterra competition-diffusion system with large interaction rates

We discuss the generation and motion of interfaces for Lotka-Volterra competition-diffusion system with large interaction. An asymptotic analysis of solutions shows that the two competing species are segregated and an interface appears on the common boundary of their habitats. The motion of the interface is governed by a free boundary problem. In this paper we establish a mathematical theory for the formation of interfaces (at the initial stage) by using an upper and lower solutions method. In addition, combining our results and a known result for the motion of interfaces (after the initial stage), we obtain some information on the generation and motion of interfaces for given almost any smooth initial data.     

Entropy Generation and Thermal Radiation Effects on Nanofluid over Permeable Stretching Sheet

In the present paper, effects of entropy generation and nonlinear thermal radiation on Jeffery nanofluid over permeable stretching sheet with partial slip effect were analyzed. The suitable similarity transformation is utilized for the reduction of a set of governing equations, which are solved by using Differential Transformation Method (DTM) with the help of symbolic software MATHEMATICA. The accuracy of impact of slip parameter on coefficient of skin friction by using DTM and numerical method (Shooting technique with fourth-order Runge-Kutta) is illustrated and good agreement is found. Further, velocity, temperature, nanoparticle volume fraction and entropy generation profiles are shown graphically and studied in detail for various physical parameters. We notice that, as slip parameter rises the velocity and entropy generation profile rises. Enhancement in the effect of nonlinear thermal radiation reduces the entropy generation.     

Models and algorithms for three-stage two-dimensional bin packing

We consider the three-stage two-dimensional bin packing problem (2BP) which occurs in real-world applications such as glass, paper, or steel cutting. We present new integer linear programming formulations: models for a restricted version and the original version of the problem are developed. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. Those models are solved using CPLEX. Furthermore, a branch-and-price (B&P) algorithm is presented for a set covering formulation of the unrestricted problem, which corresponds to a Dantzig-Wolfe decomposition of the polynomially-sized model. We consider column generation stabilization in the B&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX. Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to quickly obtain near-optimal solutions. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.     

Detection of cellular aging in a Galton–Watson process

We consider the bifurcating Markov chain model introduced by Guyon to detect cellular aging from cell lineage. To take into account the possibility for a cell to die, we use an underlying super-critical binary Galton–Watson process to describe the evolution of the cell lineage. We give in this more general framework a weak law of large number, an invariance principle and thus fluctuation results for the average over all individuals in a given generation, or up to a given generation. We also prove that the fluctuations over each generation are independent. Then we present the natural modifications of the tests given by Guyon in cellular aging detection within the particular case of the auto-regressive model.     

Unstructured tetrahedral mesh generation technology

We present a robust unstructured tetrahedral mesh generation technology. This technology is a combination of boundary discretization methods, an advancing front technique and a Delaunay-based mesh generation technique. For boundary mesh generation we propose four different approaches using analytical boundary parameterization, interface with CAD systems, surface mesh refinement, and constructive solid geometry. These methods allow us to build a flexible grid generation technology with a user friendly interface.     

Parameter estimation in stochastic scenario generation systems

Scenario analysis offers an effective tool for addressing the stochastic elements in multi-period financial planning models. Critical to any scenario generation process is the estimation of the input parameters of the underlying stochastic model for economic factors. In this paper, we propose a new approach for estimation, known as the integrated parameter estimation (IPE). This approach combines the significant features of other well-known estimation techniques within a non-convex multiple objective optimization framework, with the objective weights controlling the relative importance of the features. We solve the non-convex optimization problem using adaptive memory programming – a variation of tabu search. Based on a short interest rate model using UK treasury rates from 1980 to 1995, the integrated approach compares favorably with maximum likelihood and the generalized method of moments. We also evaluate performance with Towers Perrin's CAP:Link scenario generation system.     

Hybrid one-dimensional reversible cellular automata are regular

It is shown that the set of hybrid one-dimensional reversible cellular automata (CA) with the periodic boundary condition is a regular set. This has several important consequences. For example, it allows checking whether a given CA is reversible and the random generation of a reversible CA from the uniform distribution, both using time polynomial in the size of the CA. Unfortunately, the constant term in the resulting random generation algorithm is much too large to be of practical use. We show that for the less general case of null boundary (NB) CA, this constant can be reduced drastically, hence facilitating a practical algorithm for uniform random generation. Our techniques are further applied asymptotically to count the number of reversible NBCA.     

A detailed study of the generation of optically detectable watermarks using the logistic map

A digital watermark is a visible, or preferably invisible, identification code that is permanently embedded in digital media, to prove owner authentication and provide protection for documents. Given the interest in watermark generation using chaotic functions a detailed study of one chaotic function for this purpose is performed. In this paper, we present an approach for the generation of watermarks using the logistic map. Using this function, in conjunction with seed management, it is possible to generate chaotic sequences that may be used to create highpass or lowpass digital watermarks. In this paper we provide a detailed study on the generation of optically detectable watermarks and we provide some guidelines on successful chaotic watermark generation using the logistic map, and show using a recently published scheme, how care must be taken in the selection of the function seed.     

A goal-driven prototype column generation strategy for the multiple container loading cost minimization problem

In the multiple container loading cost minimization problem (MCLCMP), rectangular boxes of various dimensions are loaded into rectangular containers of various sizes so as to minimize the total shipping cost. The MCLCMP can be naturally modeled as a set cover problem. We generalize the set cover formulation by introducing a new parameter to model the gross volume utilization of containers in a solution. The state-of-the-art algorithm tackles the MCLCMP using the prototype column generation (PCG) technique. PCG is an effective technique for speeding up the column generation technique for extremely hard optimization problems where their corresponding pricing subproblems are NP-hard. We propose a new approach to the MCLCMP that combines the PCG technique with a goal-driven search. Our goal-driven prototype column generation (GD-PCG) algorithm improves the original PCG approach in three respects. Computational experiments suggest that all three enhancements are effective. Our GD-PCG algorithm produces significantly better solutions for the 350 existing benchmark instances than all other approaches in the literature using less computation time. We also generate two new set instances based on industrial data and the classical single container loading instances.     

A system for the design of short term harvesting strategy

Short term harvesting requires decisions on which stands to harvest, what timber volume to cut, what bucking patterns (how to cut up the logs) to apply to logs in order to obtain products that satisfy demand and which harvesting machinery to use. This is an important problem in forest management and difficult to solve well in satisfying demand, while maximizing net profits. Traditionally, foresters have used manual approaches to find adequate solutions, which has shortcomings both in time spent by analysts and the quality of solutions. Since demand for timber products is defined by length, diameter and quality of each piece, this leads to a complex combinatorial problem in matching supply (standing trees) and demand. We developed one of the few reported approaches for solving the short term harvesting problem based on a computerized system, using a linear programming approach. Determining adequate bucking patterns is not trivial. We develop a column generation approach to generate such patterns. The subproblem is a specially designed branch and bound scheme. The generation of bucking patterns implemented within the LP formulation led to a significant improvement of solutions. We believe this is the first system implemented with this level of detail. This system has been advantageously implemented in several forest companies. The results obtained show improvements obtained by the firms of 5–8% in net revenues over traditional manual approaches.     

A non-commutative cryptosystem based on quaternion algebras

We propose BQTRU, a non-commutative NTRU-like cryptosystem over quaternion algebras. This cryptosystem uses bivariate polynomials as the underling ring. The multiplication operation in our cryptosystem can be performed with high speed using quaternions algebras over finite rings. As a consequence, the key generation and encryption process of our cryptosystem is faster than NTRU in comparable parameters. Typically using Strassen’s method, the key generation and encryption process is approximately 16 / 7 times faster than NTRU for an equivalent parameter set. Moreover, the BQTRU lattice has a hybrid structure that makes inefficient standard lattice attacks on the private key. This entails a higher computational complexity for attackers providing the opportunity of having smaller key sizes. Consequently, in this sense, BQTRU is more resistant than NTRU against known attacks at an equivalent parameter set. Moreover, message protection is feasible through larger polynomials and this allows us to obtain the same security level as other NTRU-like cryptosystems but using lower dimensions.