An Algorithm for the 0-1 Equality Knapsack Problem

The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10,000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection.     

An Interactive Heuristic Approach for Multi-Objective Integer-Programming Problems

An interactive approach to solve the multi-objective integer-programming problem heuristically is described. The approach consists of two main parts. The first is an algorithm to guide the search for a set of weights to the objective functions which would produce the solution most preferred by the decision-maker given a linear utility function. The search area is successively decreased through an interaction process, with the decision-maker using a selection and contraction method. During each stage of this algorithm, a number of single integer-programming problems are solved heuristically. The motivation for this approach, along with some computational experimentation, is provided.     

Approximate Solutions and Error Bounds for Solving Matrix Differential Equations Without Increasing the Dimension of the Problem

In this paper we present a method for solving initial value problems related to second order matrix differential equations. This method is based on the existence of a solution of a certain algebraic matrix equation related to the problem, and it avoids the increase of the dimension of the problem for its resolution. Approximate solutions, and their error bounds in terms of error bounds for the approximate solutions of the algebraic problem, are given.     

带准备时间的单机指数时间学习效应排序问题

研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。     

二次比式和问题的加速分枝定界算法

本文给出非凸二次约束上二次比式和问题(P)的一个新的加速分枝定界算法.该算法利用线性化技术建立了问题(P)的松弛线性规划问题(RLP),通过对其可行域的细分和求解一系列线性规划问题,不断更新(P)的全局最优值的上下界.为了提高收敛速度,从最优性和可行性两方面,提出了新的删除技术,理论上证明该算法是收敛的,数值试验表明了算法的有效性和可行性.     

Efficient Solution of the Single-item,Capacitated Lot-sizing Problem with Start-up and Reservation Costs

A capacitated dynamic lot-sizing model, where the costs incurred are a start-up cost for switching the production facility on and another reservation cost for keeping the facility on, whether or not it is producing, is considered. The resulting scheduling problem is NP-hard. An efficient shortest path model of the uncapacitated version of the problem is developed. This model is then included, via a redefinition of variables, into a tight capacitated model; tight in the sense that sharp lower bounds can be produced from it. The lower bound problems are solved efficiently by recovering the shortest path structure through column generation, and effective upper bounds are generated by solving a small capacitated trans-shipment problem. The results of computational tests to verify the computational efficiency of the resulting solution scheme are presented.     

A Posteriori Error Analysis for Mixed Finite Element Solution of the Two-Dimensional Stationary Stokes Problem

In this paper we present a posteriori error estimator in a suitable norm of mixed finite element solution for two-dimensional stationary Stokes problem. The estimator is optimal in the sense that, up to multiplicative constant, the upper and lower bounds of the error are the same. The constants are independent of the mesh and the true solution of the problem.     

On the Neumann Problem for some Linear and Non-linear Uniformly Elliptic Difference Equations

In this paper we obtain a priori bounds on difference quotientsto the solution of the second boundary value problem for somelinear uniformly elliptic difference equations over rectangularregions. These results are applied to the constructive solutionof mildly non-linear and mildly quasi-linear uniformly ellipticdifference equations.     

Bounds and Tabu Search for a Cyclic Max-Min Scheduling Problem

A cyclic scheduling problem with applications to transport efficiency is considered. Given a set of regular polygons, whose vertices represent regularly occurring events and are lying on a common circle line, the objective is to maximize the distance between the closest vertices of different polygons on the circle line. Lower and upper bounds for the optimal solution of this NP-hard scheduling problem are presented. They are used to improve the quality of a procedure which is applied to solve this problem heuristically. It consists of a greedy starting algorithm and a Tabu Search algorithm. The numerical results show the efficiency of the procedure proposed.     

Lagrangian Relaxation and the Single-Source Capacitated Facility-Location Problem

Lagrangian relaxation has been widely used in solving a number of hard combinatorial optimization problems. The success of the approach depends on the structure of the problem and on the values assigned to the Lagrange multipliers. A recent paper on the single-source capacitated facility-location problem proposed the use of Lagrangian relaxation in which the capacity constraints were relaxed. In this paper, a class of such problems is defined for which the proposed relaxation is guaranteed to result in an infeasible solution, irrespective of the values assigned to the Lagrange multipliers. In these cases, the bounds on the optimal solution, obtained from the relaxation, are generally poor. It is concluded that, when using Lagrangian relaxation, it may be worthwhile carrying out a preliminary analysis to determine the potential viability of the approach before extensive development takes place.     

Multipoint Problem with Multiple Nodes for Partial Differential Equations

We establish conditions for the existence and uniqueness of a solution of a problem with multipoint conditions with respect to a selected variable t (in the case of multiple nodes) and periodic conditions with respect to x ₁,..., x _p for a nonisotropic partial differential equation with constant complex coefficients. We prove metric theorems on lower bounds for small denominators appearing in the course of the solution of this problem.     

Upper and Lower Bounds of a Solution of the Cauchy Problem for a Stochastic Differential Equation of Parabolic Type with Power Nonlinearities (Weak Source)

We study the time evolution of a solution of the Cauchy problem for a stochastic differential equation of the parabolic type with power nonlinearities. We construct upper and lower bounds for this solution.     

Solving the p-Median Problem with a Semi-Lagrangian Relaxation

Lagrangian relaxation is commonly used in combinatorial optimization to generate lower bounds for a minimization problem. We study a modified Lagrangian relaxation which generates an optimal integer solution. We call it semi-Lagrangian relaxation and illustrate its practical value by solving large-scale instances of the p-median problem. This work was partially supported by the Fonds National Suisse de la Recherche Scientifique, grant 12-57093.99 and the Spanish government, MCYT subsidy dpi2002-03330.     

A Multipoint Problem for Pseudodifferential Equations

We investigate the well-posedness of a problem with multipoint conditions with respect to a chosen variable t and periodic conditions with respect to coordinates x ₁,...,x _p for equations unsolved with respect to the leading derivative with respect to t and containing pseudodifferential operators. We establish conditions for the unique solvability of this problem and prove metric assertions related to lower bounds for small denominators appearing in the course of its solution.     

Estimation of Deviations from the Exact Solution for the Reissner-Mindlin Plate Problem

In this paper, we obtain a majorant of the difference between the exact solution and any conforming approximate solution of the Reissner-Mindlin plate problem. This majorant is explicitly computable and involves constants that depend only on given data of the problem. The majorant allows us to compute guaranteed upper bounds of errors with any desired accuracy and vanishes if and only if the approximate solution coincides with the exact one. Bibliography: 12 titles. To N. N. Uraltseva with gratitude __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 310, 2004, pp. 145–157.     

A Fourth-Order Modified Method for the Cauchy Problem of the Modified Helmholtz Equation

This paper is concerned with the Cauchy problem for the modified Helmholtz equation in an infinite strip domain 0 < x≤ 1, y ∈ R. The Cauchy data at x = 0 is given and the solution is then sought for the interval 0 < x ≤1. This problem is highly ill-posed and the solution (if it exists) does not depend continuously on the given data. In this paper, we propose a fourth-order modified method to solve the Cauchy problem. Convergence estimates are presented under the suitable choices of regularization parameters and the a priori assumption on the bounds of the exact solution. Numerical implementation is considered and the numerical examples show that our proposed method is effective and stable.     

具有初始跳跃的双曲型方程奇异摄动问题的数值解法

本文考虑具有初始跳跃的二阶双曲型方程初边值问题.首先给出解的导数估计.然后在一非均匀网格上构造了一个差分格式,最后在能量范数意义下证明了差分格式解的一致收敛性.     

Branch and Bound Algorithm for the <Emphasis Type="Italic">p</Emphasis>-Median Transportation Problem

The p-median transportation problem is to determine an optimal solution to a transportation problem having an additional constraint restricting the number of active supply points. The model is discussed as an example of a public sector location/allocation problem. A branch and bound procedure is proposed to solve the problem. Lagrangian relaxation is used to provide lower bounds. Computational results are given.     

A Global Optimization Approach to a Water Distribution Network Design Problem

In this paper, we address a global optimization approach to a waterdistribution network design problem. Traditionally, a variety of localoptimization schemes have been developed for such problems, each new methoddiscovering improved solutions for some standard test problems, with noknown lower bound to test the quality of the solutions obtained. A notableexception is a recent paper by Eiger et al. (1994) who present a firstglobal optimization approach for a loop and path-based formulation of thisproblem, using a semi-infinite linear program to derive lower bounds. Incontrast, we employ an arc-based formulation that is linear except forcertain complicating head-loss constraints and develop a first globaloptimization scheme for this model. Our lower bounds are derived through thedesign of a suitable Reformulation-Linearization Technique (RLT) thatconstructs a tight linear programming relaxation for the given problem, andthis is embedded within a branch-and-bound algorithm. Convergence to anoptimal solution is induced by coordinating this process with an appropriatepartitioning scheme. Some preliminary computational experience is providedon two versions of a particular standard test problem for the literature forwhich an even further improved solution is discovered, but one that isverified for the first time to be an optimum, without any assumed boundson the flows. Two other variants of this problem are also solved exactly forillustrative purposes and to provide researchers with additional test caseshaving known optimal solutions. Suggestions on a more elaborate study involving several algorithmic enhancements are presented for futureresearch.     

Stoxes方程初边值问题的Phragmen－Lindelof二择性原理

本文对非定常的Ｓｔｏｋｅｓ方程的初边值问题证明了Ｐｈｒａｇｍｅｎ－Ｌｉｎｄｅｌｏｆ二择性原理，即证明Ｓｔｏｋｅｓ流函数的能量，随着与带状区域有限端距离的增加必定或者按指数率增长或者按指数率衰减．对能量衰减情况建立了Ｓｔｏｋｅｓ流速度的最大模的点点估计．并提出求全能量上界的方法．