Capacitated Multiple Item Ordering with Incremental Quantity Discounts

This paper presents a heuristic algorithm for determining order quantities for multiple items given incremental quantity discounts and a single resourse constraint. The heuristic is based on Lagrangian relaxation. The performance of the heuristic is compared, for small problems, with a procedure that generates optimal solutions. Results from computational experiments are given that demonstrate the quality and computational efficiency of the heuristic algorithm.     

Locating semi-obnoxious facilities with expropriation: minisum criterion

This paper considers the problem of locating semi-obnoxious facilities assuming that demand points within a certain distance from an open facility are expropriated at a given price. The objective is to locate the facilities so as to minimize the total weighted transportation cost and expropriation cost. Models are developed for both single and multiple facilities. For the case of locating a single facility, finite dominating sets are determined for the problems on a plane and on a network. An efficient algorithm is developed for the problem on a network. For the case of locating multiple facilities, a branch-and-bound procedure using Lagrangian relaxation is proposed and its efficiency is tested with computational experiments.     

Description of the mechanical relaxation of highly oriented polymers based on their relaxation spectra

Both the shape and width of the relaxation spectra of polymers with different draw ratios are analyzed in regions of relaxation transitions. The analysis substantiates an empirically ascertained linear law governing the frequency distribution of the dynamic modulus E'(ω) of highly oriented polymers in E' = ln ω coordinates, which corresponds to the uniform distribution of a single relaxation time H(τ) ? const. The possibility of describing the temperature dependence of the modulus of highly oriented polymers within a broad temperature range is demonstrated, where a single relaxation time is used and consideration given to the nonuniform distribution of the energy of fundamental vibrations with respect to oscillatory modes.     

Relaxation methods for solving the tensor equation arising from the higher‐order Markov chains

In this paper, we propose several relaxation algorithms for solving the tensor equation arising from the higher‐order Markov chain and the multilinear PageRank. The semi‐symmetrization technique on the original equation is also employed to modify the proposed algorithms. The convergence analysis is given for the proposed algorithms. It is shown that the new algorithms are more efficient than the existing ones by some numerical experiments when relaxation parameters are chosen suitably.     

MULTIDIMENSIONAL RELAXATION APPROXIMATIONS FOR HYPERBOLIC SYSTEMS OF CONSERVATION LAWS

We construct and implement a non-oscillatory relaxation scheme for multidimensional hyperbolic systems of conservation laws. The method transforms the nonlinear hyperbolic system to a semilinear model with a relaxation source term and linear characteristics which can be solved numerically without using either Riemann solver or linear iterations. To discretize the relaxation system we consider a high-resolution reconstruction in space and a TVD Runge-Kutta time integration. Detailed formulation of the scheme is given for problems in three space dimensions and numerical experiments are implemented in both scalar and system cases to show the effectiveness of the method.     

一类比式和问题的全局优化方法

对于一类比式和问题(P)给出一全局优化算法.首先利用线性约束的特征推导出问题(P)的等价问题(P1),然后利用新的线性松弛方法建立了问题(P1)的松弛线性规划(RLP),通过对目标函数可行域线性松弛的连续细分以及求解一系列线性规划,提出的分枝定界算法收敛到问题(P)的全局最优解.最终数值实验结果表明了该算法的可行性和高效性.     

Windowing Waveform Relaxation of Initial Value Problems

We present a windowing technique of waveform relaxation for dynamic systems.An effectiveestimation on window length is derived by an iterative error expression provided here.Relaxation processes canbe speeded up if one takes the windowing technique in advance.Numerical experiments are given to furtherillustrate the theoretical analysis.     

Direct separation of two-dimensional vector fields into irrotational and solenoidal parts

An iterative technique is given for separating a two-dimensional vector into irrotational and solenoidal parts. In contrast to classical methods, the procedure operates directly on the orthogonal scalar components of the vector field, and gives the two separate fields as the result of a single sequence of operations. The manipulations are somewhat similar to a relaxation process. An example of the decomposition of a meteorological wind field is given.     

求广义几何规划全局最优解的线性化方法

对广义几何规划问题(GGP)提出了一个确定型全局优化算法，这类优化问题能广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中，使用指数变换及对目标函数和约束函数的线性下界估计，建立了GGP的松弛线性规划(RLP)，通过对RLP可行域的细分以及一系列RLP的求解过程，从理论上证明了算法能收敛到GGP的全局最优解，对一个化学工程设计问题应用本文算法，数值实验表明本文方法是可行的。     

Time relaxation algorithm for flow ensembles

Modeling for fast calculation of fluid flow ensembles based on time relaxation regularization is studied herein. At each time step, the proposed model requires the storage of a single coefficient matrix with multiple right‐hands sides, corresponding to each ensemble member. The time relaxation regularization penalizes the deviation of the fluctuations from the ensemble average. The algorithm is shown to be stable under a time step restriction, which holds provided fluctuations are small enough. Also, the numerical tests show that a grad‐div stabilization weakened the condition considerably. Finite element convergence results for the time relaxation ensemble algorithm are studied too. Then, 2D and 3D numerical experiments that support the theoretical results are presented. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 757–777, 2016     

求解最大割问题的半定规划松驰的序列线性规划方法

本文基于最大割问题的半定规划松弛,利用矩阵分解的方法给出了与半定规划松弛等价的非线性规划模型,提出一种序列线性规划方法求解该模型.并在适当的条件下,证明了算法的全局收敛性.数值实验表明:序列线性规划方法在时间上要优于半定规划的内点算法.所以序列线性规划方法能更有效地求解大规模的最大割问题的半定规划松弛.     

A SUCCESSIVE QUADRATIC PROGRAMMING ALGORITHM FOR SDP RELAXATION OF MAX-BISECTION

A successive quadratic programming algorithm for solving SDP relaxation of Max- Bisection is provided and its convergence result is given.The step-size in the algorithm is obtained by solving n easy quadratic equations without using the linear search technique.The numerical experiments show that this algorithm is rather faster than the interior-point method.     

Waveform relaxation method for stochastic differential equations with constant delay

This paper extends the waveform relaxation method to stochastic differential equations with constant delay terms, gives sufficient conditions for the mean square convergence of the method. A lot of attention is paid to the rate of convergence of the method. The conditions of the superlinear convergence for a special case, which bases on the special splitting functions, are given. The theory is applied to a one-dimensional model problem and checked against results obtained by numerical experiments.     

Accelerating Branch-and-Bound through a Modeling Language Construct for Relaxation-Specific Constraints

In the tradition of modeling languages for optimization, a single model is passed to a solver for solution. In this paper, we extend BARON’s modeling language in order to facilitate the communication of problem-specific relaxation information from the modeler to the branch-and-bound solver. This effectively results into two models being passed from the modeling language to the solver. Three important application areas are identified and computational experiments are presented. In all cases, nonlinear constraints are provided only to the relaxation constructor in order to strengthen the lower bounding step of the algorithm without complicating the local search process. In the first application area, nonlinear constraints from the reformulation–linearization technique (RLT) are added to strengthen a problem formulation. This approach is illustrated for the pooling problem and computational results show that it results in a scheme that makes global optimization nearly as fast as local optimization for pooling problems from the literature. In the second application area, we communicate with the relaxation constructor the first-order optimality conditions for unconstrained global optimization problems. Computational experiments with polynomial programs demonstrate that this approach leads to a significant reduction of the size of the branch-and-bound search tree. In the third application, problem-specific nonlinear optimality conditions for the satisfiability problem are used to strengthen the lower bounding step and are found to significantly expedite the branch-and-bound algorithm when applied to a nonlinear formulation of this problem.     

Efficient solution of large scale,single-source,capacitated plant location problems

The single-source, capacitated plant location problem is considered. This problem differs from the capacitated plant location problem by the additional requirement that each customer must be supplied with all its demand from a single plant. An efficient heuristic solution, capable of solving large problem instances, is presented. The heuristic combines Lagrangian relaxation with restricted neighbourhood search. Computational experiments on two sets of problem instances are presented.     

试探算法与SSOR预处理共轭梯度算法的拟最佳因子

1引言在求解系数矩阵为对称正定的大型线性代数方程组Au=b (1．1)的迭代法方面,七十年代以来发展了各种预处理共轭梯度法．由于SSOR分裂中具有对称因子,可用于加速共轭梯度法,称为SSOR预处理共轭梯度法(简记为;SSORPCG．同时,由于当松弛因子ω∈(0,2)时,SSOR迭代法收敛,从而进一步发展了m步SSOR预处理共轭梯度法(简记为:m-step SSORPCG．胡家赣证明,经过最优的SSOR预条件,预优     

Improved integer programming bounds using intersections of corner polyhedra

Consider the relaxation of an integer programming (IP) problem in which the feasible region is replaced by the intersection of the linear programming (LP) feasible region and the corner polyhedron for a particular LP basis. Recently a primal-dual ascent algorithm has been given for solving this relaxation. Given an optimal solution of this relaxation, we state criteria for selecting a new LP basis for which the associated relaxation is stronger. These criteria may be successively applied to obtain either an optimal IP solution or a lower bound on the cost of such a solution. Conditions are given for equality of the convex hull of feasible IP solutions and the intersection of all corner polyhedra.     

Bandwidth packing with priority classes

The bandwidth packing problem is defined as the selection and routing of messages from a given list of messages with prespecified requirements on demand for bandwidth. The messages have to be routed over a network with given topology so that the generated revenue is maximized. Messages to be routed are classified into two priority classes. An integer programming based formulation of this problem is proposed and a Lagrangean relaxation based methodology is described for solving this problem. A general purpose heuristic is then developed for generating feasible solutions of good quality. Several numerical experiments are conducted using a number of problem parameters such as number of messages, ratio of messages for lower and higher priority classes, capacity of links, and demand distribution of messages belonging to different classes and high quality solutions to the priority bandwidth packing problem are generated under the different situations.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

Asymptotic properties of a nonlinear diffusion process arising in articular cartilage

Stress relaxation experiments in articular cartilage studies give rise to a nonlinear diffusion process. The paper demonstrates that the nonlinear model admits a solution which possesses certain salient features that are observed experimentally. A relaxation constant is defined for the nonlinear model in order to examine the asymptotic behavior of solutions as time approaches infinity. An explicit formula relating the relaxation constant to the nonlinear permeability function, and the displacement at the “motor cutoff time” is derived. Finally, upper and lower bounds to the solution and certain of its derivatives are provided.