On the two-level planning procedure under a Dantzig-Wolfe decomposition†

In this paper a modified Dantzig-Wolfe decomposition algorithm is interpreted as a. decontralized planning process. The main objective is to provide some extensions of the pricing and allocation rules of the original algorithm to make the solution process more efficient. A simple numerical example is included.     

The parallel QZ decomposition method for solving linear equations

The QR orthogonal decomposition method is well established for solving linear systems and both sequential and parallel implementations have been proposed. In this paper, the QZ orthogonal decomposition method is proposed in which 2 elements are eliminated simultaneously. Consequently, the theoretical analyses presented show that the QZ method is faster than the QR method which is confirmed by the numerical results.     

A Benders decomposition based framework for solving cable trench problems

In this work, we present an algorithmic framework based on Benders decomposition for the Capacitated p-Cable Trench Problem with Covering. We show that our approach can be applied to most variants of the Cable Trench Problem (CTP) that have been considered in the literature. The proposed algorithm is augmented with a stabilization procedure to accelerate the convergence of the cut loop and with a primal heuristic to derive high-quality primal solutions. Three different variants of the CTP are considered in a computational study which compares the Benders approach with two compact integer linear programming formulations that are solved with CPLEX. The obtained results show that the proposed algorithm significantly outperforms the two compact models and that it can be used to tackle significantly larger instances than previously considered algorithms based on Lagrangean relaxation.     

Relax-and-fix decomposition technique for solving large scale grid-based location problems

Many problems in business, engineering, defence, resource exploitation, and even the medical sciences with location aspects can be expressed as grid-based location problems (GBLPs), modeled as integer linear programming problems. Such problems are often very computationally complex to solve. We develop a relax-and-fix-based decomposition approach to solve large-scale GBLPs, which we demonstrate will significantly reduce solution runtimes while not severely impacting optimality. We also introduce problem-specific logical restrictions, constraints that reduce the feasible region and the resulting branch-and-bound tree with minimal reductions in optimality.     

Relax-and-fix decomposition technique for solving large scale grid-based location problems

Many problems in business, engineering, defence, resource exploitation, and even the medical sciences with location aspects can be expressed as grid-based location problems (GBLPs), modeled as integer linear programming problems. Such problems are often very computationally complex to solve. We develop a relax-and-fix-based decomposition approach to solve large-scale GBLPs, which we demonstrate will significantly reduce solution runtimes while not severely impacting optimality. We also introduce problem-specific logical restrictions, constraints that reduce the feasible region and the resulting branch-and-bound tree with minimal reductions in optimality.     

Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication

Most shop-floor scheduling policies used in practice rely on dispatching, making use of only local information at individual workcenters. However, in semiconductor manufacturing environments, we have access to real-time shop-floor status information for the entire facility. In these complex facilities, there would appear to be significant potential for improved schedules by considering global shop information and using optimization-based heuristics. To this end, we propose a rolling horizon (RH) heuristic that decomposes the shop into smaller subproblems that can be solved sequentially over time using a workcenter-based decomposition heuristic. We develop test instances for evaluating our heuristic using a simulation model of an industrial facility. The results demonstrate that the proposed heuristic yields better schedules than the dispatching rules in the vast majority of test instances with reasonable computational effort.     

Explicit preconditioned domain decomposition schemes for solving nonlinear boundary value problems

A new class of inner-outer iterative procedures in conjunction with Picard-Newton methods based on explicit preconditioning iterative methods for solving nonlinear systems is presented. Explicit preconditioned iterative schemes, based on the explicit computation of a class of domain decomposition generalized approximate inverse matrix techniques are presented for the efficient solution of nonlinear boundary value problems on multiprocessor systems. Applications of the new composite scheme on characteristic nonlinear boundary value problems are discussed and numerical results are given.     

A C-tree decomposition algorithm for 2D and 3D geometric constraint solving

In this paper, we propose a method which can be used to decompose a 2D or 3D constraint problem into a C-tree. With this decomposition, a geometric constraint problem can be reduced into basic merge patterns, which are the smallest problems we need to solve in order to solve the original problem in certain sense. Based on the C-tree decomposition algorithm, we implemented a software package MMP/Geometer. Experimental results show that MMP/Geometer finds the smallest decomposition for all the testing examples efficiently.     

An improved (G′/G)-expansion method for solving nonlinear evolution equations

An improved (G′/G)-expansion method is proposed to seek more general travelling wave solutions of nonlinear evolution equations. We choose the Zakharov–Kuznetsov–BBM (Benjamin–Bona–Mahony) equation and the (2+1)-dimensional dispersive long wave equations to illustrate the validity and advantages of the proposed method. As a result, many exact travelling wave solutions are obtained, which include soliton, hyperbolic function, trigonometric function and rational, solutions.     

大规模最小二乘奇异值分解的并行处理方法

大规模最小二乘问题求解中,直接进行奇异值分解会产生巨大的内存需求以及漫长的计算时间。为解决该问题,提出了一种基于迭代的并行处理方法。该方法利用奇异值分解降维的特性,通过迭代不断减小矩阵规模,直到可以直接使用奇异值分解求解。在迭代过程中,将矩阵分解为许多足够小的子矩阵,并行处理其奇异值分解过程,从而提升运行速度。实验结果表明,该方法即使是串行处理,也使得大规模最小二乘奇异值分解的时间成本及空间成本大大降低;而并行处理在双机条件下加速比接近200％。     

Comparison of the Adomian decomposition method and the variational iteration method in solving the moving boundary problem

In this paper, a comparison between two methods: the Adomian decomposition method and the variational iteration method, used for solving the moving boundary problem, is presented. Both of the methods consist in constructing the appropriate iterative or recurrence formulas, on the basis of the equation considered and additional conditions, enabling one to determine the successive elements of a series or sequence approximating the function sought. The precision and speed of convergence of the procedures compared are verified with an example.     

Scalability analysis of a two level domain decomposition approach in space and time solving data assimilation models

We are concerned with the mapping on high performance hybrid architectures of a parallel software implementing a two level overlapping domain decomposition, that is, along space and time directions, of the four dimensional variational data assimilation model. The reference architecture belongs to the SCoPE (Sistema Cooperativo Per Elaborazioni scientifiche multidisciplinari) data center, located at University of Naples Federico II. We consider the initial boundary problem of the shallow water equation and analyse both strong and weak scaling. Keeping the efficiency always greater than $$ and about $$ in most cases, we experimentally find that the isoefficiency function grows a little more than linearly with respect to the number of processes. Results, obtained by using the parallel computing toolbox of MATLABR2013a, are in agreement with the algorithm's performance prevision based on the scale up factor, confirming the appropriate mapping of the algorithm on the hybrid architecture.     

A branch-and-price algorithm for an integrated production and inventory routing problem

With globalization, the need to better integrate production and distribution decisions has become ever more pressing for manufacturers trying to streamline their supply chain. This paper investigates a previously developed mixed-integer programming (MIP) model aimed at minimizing production, inventory, and delivery costs across the various stages of the system. The problem being modeled includes a single production facility, a set of customers with time varying demand, a finite planning horizon, and a fleet of homogeneous vehicles. Demand can be satisfied from either inventory held at a customer site or from daily product distribution. Whether a customer is visited on a particular day is determined by an implicit tradeoff between inventory and distribution costs. Once the decision is made, a vehicle routing problem must be solved for those customers who are scheduled for a delivery.A hybrid methodology that combines exact and heuristic procedures within a branch-and-price framework is developed to solve the underlying MIP. The approach takes advantage of the efficiency of heuristics and the precision of branch and price. Implementation required devising a new branching strategy to accommodate the unique degeneracy characteristics of the master problem, and a new procedure for handling symmetry. A novel column generation heuristic and a rounding heuristic were also implemented to improve algorithmic efficiency. Computational testing on standard data sets showed that the hybrid scheme can solve instances with up to 50 customers and 8 time periods within 1 h. This level of performance could not be matched by either CPLEX or standard branch and price alone.     

Software for solving identification and identifiability problems,E.G. in compartmental systems

The identification problem for a system with a known structure is considered. The mathematical background of the identifiability problem is shortly discussed. Two minicomputer programs which have been used in several studies to solve the identifiability and the identification problem for biomedical systems are described.     

A New Method of Solving Kernels in Algebraic Decomposition for the Synthesis of Logic Cell Array

In this paper,an improvement has been made on the algorithm of solving the kernels of new functions which are generated after a common divisor appearing in the original functions is replaced by a new intermediate variable.And an efficient method based on kernel heritage is presented.This method has been successfully used in synthesis of LCA (Logic Cell Array).     

Adomian’s decomposition method for solving an intermediate fractional advection–dispersion equation

This paper is concerned with a model that describes the intermediate process between advection and dispersion via fractional derivative in the Caputo sense. Adomian’s decomposition method is used for solving this model. The solution is obtained as an infinite series which always converges to the exact solution.     

A parallel unified transform solver based on domain decomposition for solving linear elliptic PDEs

The Journal of Supercomputing - A hybrid approach for the solution of linear elliptic PDEs, based on the unified transform method in conjunction with domain decomposition techniques, is introduced....     

Sequencing surgical cases in a day-care environment: An exact branch-and-price approach

In this paper we investigate how to sequence surgical cases in a day-care facility. We specify a multi-criteria objective function in which we minimize the peak use of recovery beds, the occurrence of recovery overtime and the violation of various patient and surgeon preferences. The limited availability of resources and the occurrence of medical precautions, such as an additional cleaning of the operating room after the surgery of an infected patient, are taken into account. We apply column generation to solve this combinatorial optimization problem and propose a dynamic programming algorithm to solve the pricing problem. The computational efficiency of this dynamic programming approach is validated through comparison with a mixed integer linear programming approach. In order to obtain integer variables, we embed the column generation loop in an enumerative branch-and-price framework. We elaborate on various branching strategies and branching schemes and examine their impact on the solution quality. The test instances for the computational experiments are generated using real-life data of the surgical day-care center at the academic hospital UZ Leuven Campus Gasthuisberg (Belgium).     

An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems

Journal of Scheduling - This paper presents the problem of batching and scheduling jobs belonging to incompatible job families on unrelated-parallel machines. More specifically, we investigate...