A mathematical programming viewpoint for solving the ultimate pit problem

In 1965 Helmut Lerchs and Ingo Grossmann presented to the mining community an algorithm to find the optimum design for an open pit mine. In their words, “the objective is to design the contour of a pit so as to maximize the difference between total mine value of the ore extracted and the total extraction cost of ore and waste”. They modeled the problem in graph theoretic terms and showed that an optimal solution of the ultimate pit problem is equivalent to finding the maximum closure of their graph based model. In this paper, we develop a network flow algorithm based on the dual to solve the same problem. We show how this algorithm is closely related to Lerchs and Grossmann's and how the steps in their algorithm can be viewed in mathematical programming terms. This analysis adds insight to the algorithm of Lerchs and Grossmann and shows where it can be made more efficient. As in the case Lerchs and Grossmann, our algorithm allows us to use very efficient data structures based on graphs that represent the data and constraints.. 1782 1528 V 3     

Multiphysics mixed finite element method with Nitsche's technique for Stokes-poroelasticity problem

In this article, we propose a multiphysics mixed finite element method with Nitsche's technique for Stokes-poroelasticity problem. Firstly, we reformulate the poroelasticity part of the original problem by introducing two pseudo-pressures to into a “fluid–fluid” coupled problem so that we can use the classical stable finite element pairs to deal with this problem conveniently. Then, we prove the existence and uniqueness of weak solution of the reformulated problem. And we use Nitsche's technique to approximate the coupling condition at the interface to propose a loosely-coupled time-stepping method to solve three subproblems at each time step–a Stokes problem, a generalized Stokes problem and a mixed diffusion problem. And the proposed method does not require any restriction on the choice of the discrete approximation spaces on each side of the interface provided that appropriate quadrature methods are adopted. Also, we give the stability analysis and error estimates of the loosely-coupled time-stepping method. Finally, we give the numerical tests to show that the proposed numerical method has a good stability and no “locking” phenomenon.     

Optimization of Batch Reactions in Series with Uncertainty

Certain types of chemical reactions, such as the global deprotection of a polypeptide, are extremely complex. As a result, it may be very difficult or expensive to develop accurate models of these chemical reactions. Without a satisfactory kinetic model for the reaction, it is difficult to develop an optimum operating policy that will maximize the profit. Stochastic optimization is applied in this work to an example process step to obtain the optimum reaction temperature and reaction time. In the case of the “here and now” problem, the optimal conditions are a lower reaction temperature and a longer reaction time than obtained from the deterministic problem. The average reaction time for the “wait and see” problem is also longer than the deterministic case, but the average reaction temperature is very close to that of the deterministic problem. Both normally and uniformly – distributed uncertain parameters are considered.     

Solution of Tikhonov’s Motion-Separation Problem Using the Modified Newton–Kantorovich Theorem

The paper presents a new way to prove the existence of a solution of the well-known Tikhonov’s problem on systems of ordinary differential equations in which one part of the variables performs “fast” motions and the other part, “slow” motions. Tikhonov’s problem has been the subject of a large number of works in connection with its applications to a wide range of mathematical models in natural science and economics. Only a short list of publications, which present the proof of the existence of solutions in this problem, is cited. The aim of the paper is to demonstrate the possibility of applying the modified Newton–Kantorovich theorem to prove the existence of a solution in Tikhonov’s problem. The technique proposed can be used to prove the existence of solutions of other classes of problems with a small parameter.     

A random bit-flipping method for seeking agreement

Recently Papadimitriou has proposed a randomized “bit-flipping” method for solving the 2-satisfiability problem, and the author has proposed a randomized recoloring method which, given a 3-colorable graph, finds a 2-coloring of the vertices so that no triangle is monochromatic. Both methods involve finding a “bad” configuration (unsatisfied clause, monochromatic triangle) and randomly changing one of the bits involved. In this paper we see how these problems and methods fit naturally in a more general geometrical context in which we seek a vector which “agrees” with a given collection of vectors; and we propose a simple “bit-flipping” method for the more general problem, which extends the solution methods for the two problems mentioned above. Further, we consider deterministic methods to handle such problems, and in particular we see how to solve the above “triangle problem” for 3-colorable graphs deterministically in polynomial time. © 1996 John Wiley & Sons, Inc.     

Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (“within” and “without” the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that “safe” jobs are to be scheduled before “unsafe” jobs.     

Bayesian nonparametrie inference and monte carlo optimization

As global or combinatorial optimization problems are not effectively tractable by means of deterministic techniques, Monte Carlo methods are used in practice for obtaining ”good“ approximations to the optimum. In order to test the accuracy achieved after a sample of finite size, the Bayesian nonparametric approach is proposed as a suitable context, and the theoretical as well as computational implications of prior distributions in the class of neutral to the right distributions are examined. The feasibility of the approach relatively to particular Monte Carlo procedures is finally illustrated both for the global optimization problem and the {0 - 1} programming problem.     

Computation of worst geometric imperfection profiles of composite cylindrical shell panels by minimizing the non-linear buckling load

In this article the “most unfavorable” shape of initial geometric imperfection profile for laminated cylindrical shell panel is obtained analytically by minimizing the limit point load. The partial differential equations governing the shell stability problem are reduced to a set of non-linear algebraic equations using Galerkin's technique. The non-linear equilibrium path is traced by employing Newton–Raphson method in conjunction with the Riks approach. A double Fourier series is used to represent the initial geometric imperfection profile for the cylindrical shell panel. The optimum values of these Fourier coefficients are determined by minimizing the limit point load using genetic algorithm. The results are determined for simply supported composite cylindrical shell panel. Numerical results show that more number of terms is needed in Fourier series representation to obtain the “worst” geometric imperfection profile which gives lower limit load compared to single term representation of imperfection. We have incorporated constraints on the shape of imperfection to avoid unrealistic limit point loads (due to imperfection shape) as we have assumed that the imperfection is due to machining/manufactuting.     

An immersed-boundary method for compressible viscous flows and its application in the gas-kinetic BGK scheme

An immersed-boundary (IB) method is proposed and applied in the gas-kinetic BGK scheme to simulate incompressible and compressible viscous flows with complex stationary and moving boundaries on stationary Cartesian grids. In this method the ghost-cell technique is used to satisfy the boundary condition on the immersed boundary. A novel idea, “local boundary determination”, is put forward to identify the ghost cells, each of which may have several different ghost-cell constructions corresponding to different boundary segments. Thus, the singular behavior of the ghost cell is eliminated. Furthermore, the so-called “fresh-cell” problem that occurs when implementing the IB method in a moving-boundary simulation is resolved by a simple temporal extrapolation. The method is first applied in the gas-kinetic BGK scheme to simulate the Taylor–Couette flow, wherein the second-order spatial accuracy of the method is validated and the “super-convergence” of the BGK scheme is observed. After that the flow between a circular cylinder and a square cylinder is used as a test case to showcase the advantage of this method in resolving the singularity problem. Then the supersonic flow around a stationary cylinder, the incompressible flow around an oscillating cylinder and the compressible flow around a moving airfoil are simulated to verify that this method can be used to simulate compressible flows and handle moving boundaries. These numerical tests demonstrate the good performance of the proposed immersed-boundary method for the study of incompressible/compressible flow problems with complex stationary/moving boundaries.     

Vertex packings: Structural properties and algorithms

We consider a binary integer programming formulation (VP) for the weighted vertex packing problem in a simple graph. A sufficient “local” optimality condition for (VP) is given and this result is used to derive relations between (VP) and the linear program (VLP) obtained by deleting the integrality restrictions in (VP). Our most striking result is that those variables which assume binary values in an optimum (VLP) solution retain the same values in an optimum (VP) solution. This result is of interest because variables are (0, 1/2, 1). valued in basic feasible solutions to (VLP) and (VLP) can be solved by a “good” algorithm. This relationship and other optimality conditions are incorporated into an implicit enumeration algorithm for solving (VP). Some computational experience is reported.     

Pseudospectral approximation of eigenvalues of derivative operators with non-local boundary conditions

By taking as a “prototype problem” a one-delay linear autonomous system of delay differential equations we present the problem of computing the characteristic roots of a retarded functional differential equation as an eigenvalue problem for a derivative operator with non-local boundary conditions given by the particular system considered. This theory can be enlarged to more general classes of functional equations such as neutral delay equations, age-structured population models and mixed-type functional differential equations.It is thus relevant to have a numerical technique to approximate the eigenvalues of derivative operators under non-local boundary conditions. In this paper we propose to discretize such operators by pseudospectral techniques and turn the original eigenvalue problem into a matrix eigenvalue problem. This approach is shown to be particularly efficient due to the well-known “spectral accuracy” convergence of pseudospectral methods. Numerical examples are given.     

选址-库存-路径问题模型及其集成优化算法

设施选址、库存控制和车辆路径安排是物流系统优化中的三个关键问题,三者之间存在相互依赖的关系,应该根据这种关系来相应地进行综合优化与管理物流活动。以典型的单一生产基地、单一产品、采用不断审查的(Q, r)库存策略的供应链二级分销网络为研究对象,建立了一个随机型选址-库存-路径问题优化模型;在将非线性混合整数规划转化为线性整数集合覆盖模型的基础上,采用列生成算法来获得一个近似最优解,再用分支定价法对初始解进行改进,以实现对整个问题“完全集成”的优化。最后,用随机生成的方式,产生了10至160个客户的计算实例,分析了运输费用和库存费用对总成本的影响,算法运算时间表明本文给出的算法能较快地求解这一复杂问题。     

Spectral problem of the radial Schrödinger equation with confining power potentials

We suggest an approach in which the Schrödinger equation for several widely used potentials is reduced to the eigenvalue problem for an infinite system of algebraic equations. The method is convenient for both analytical and numerical calculations. With the help of this approach, the mass spectra of “charmonium” and “bottomonium” are calculated for the “Cornell” potential, and for the sum of the Coulomb and oscillator potentials. The method proposed allows one to determine the mass spectra of relativistic Schrödinger-type equations. Good agreement with experimental data is achieved.     

A heuristic procedure for the Capacitated m-Ring-Star problem

In this paper we propose a heuristic method to solve the Capacitated m-Ring-Star Problem which has many practical applications in communication networks. The problem consists of finding m rings (simple cycles) visiting a central depot, a subset of customers and a subset of potential (Steiner) nodes, while customers not belonging to any ring must be “allocated” to a visited (customer or Steiner) node. Moreover, the rings must be node-disjoint and the number of customers allocated or visited in a ring cannot be greater than the capacity Q given as an input parameter. The objective is to minimize the total visiting and allocation costs. The problem is a generalization of the Traveling Salesman Problem, hence it is NP-hard. In the proposed heuristic, after the construction phase, a series of different local search procedures are applied iteratively. This method incorporates some random aspects by perturbing the current solution through a “shaking” procedure which is applied whenever the algorithm remains in a local optimum for a given number of iterations. Computational experiments on the benchmark instances of the literature show that the proposed heuristic is able to obtain, within a short computing time, most of the optimal solutions and can improve some of the best known results.     

Problems Involving Infrequent but Significant Contingencies

Problematic situations often arise in which it is required to provide a solution which will tend to avoid events, which, if they occur, would be very costly, or, if not directly costable, they would be highly undesirable. Although direct approaches to this sort of problem exist, they can be unmanageable. If, however, we take as a posit, that the frequency with which the undesirable events arise, in the optimum solution, is small, considerable simplifications can be made. Naturally we need to check the posit once the solution has been found. This paper considers three applications of this principle, viz. determination of how many chargers are needed for steel furnaces, where the undesirable event is “a furnace waits for service”; determination of the number of emergency beds to set aside in a hospital unit, where the undesirable event is “an emergency case arrives and no bed is immediately available”; determination of an inventory reorder rule where the undesirable event is “stock run-out”. The general principle is formalized.     

Prediction quality estimation for a two-phase scheme for solution of the “structure-property” problem

The paper is focused on methods of searching for quantitative structure property relationships for predicting the activity of chemical compounds. A two-phase scheme is proposed for solving the “structure-property” problem. An estimation of the quality of prediction with the use of a two-phase scheme is obtained. In particular, it is proved that the prediction quality is improved by the use of nontrivial rejection rules. Results of practical tests of the proposed method for solving the “structure-property” problem are presented, which confirm the efficiency of this approach.     

“公司+农户”型订单农业供应链“双向补贴”机制研究

基于订单农业特点,构建“公司+农户”型订单农业供应链决策模型。研究发现,订单农业传统价格机制:按“固定价格”收购、按“市场价格”收购、“随行就市,保底收购”,各具优缺点,但均未能很好地协调此类“公司+农户”型订单农业供应链,我国订单农业违约率也是居高不下。为此,提出一种 “双向补贴”价格机制来协调此类订单农业供应链。本研究结果表明,“双向补贴”价格机制能够很好地弥补了按“固定价格”,“市场价格”收购的缺陷,保证了农户和公司获得相对稳定的收入,提高了“公司+农户”型订单农业供应链的稳定性。同时,实施该协调机制后,改善了公司在“随行就市,保底收购”机制下要承担全部风险的缺陷,公司和农户实现了“收益共享,风险同担”。     

Controlling Bivariate Categorical Processes using Scan Rules

In this paper, we introduce a methodology for efficiently monitoring a health process that classify the intervention outcome, in two dependent characteristics, as “absolutely successful”, “with minor but acceptable complications” and “unsuccessful due to severe complications”. The monitoring procedure is based on appropriate 2-dimensional scan rules. The run length distribution is acquired by studying the waiting time distribution for the first occurrence of a 2-dimensional scan in a bivariate sequence of trinomial trials. The waiting time distribution is derived through a Markov chain embedding technique. The proposed procedure is applied on two simulated cases while it is tested against a competing method showing an excellent performance.     

Conformal mapping of long quadrilaterals and thick doubly connected domains

In this paper we investigate theoretically an approximation technique for avoiding the crowding phenomenon in numerical conformal mapping. The method applies to conformal maps from rectangles to “long quadrilaterals,” i.e., Jordan domains bounded by two parallel straight lines and two Jordan arcs, where the two arcs are far apart. We require that these maps take the four corners of the rectangle to the four corners of the quadrilateral. Our main theorem tackles a conformal mapping problem for doubly connected domains, and we derive from this our results for quadrilaterals. As a corollary, we extend the “domain decomposition” mapping technique of Papamichael and Stylianopoulos. Similar results hold for the inverse maps, from quadrilaterals to rectangles.