A note on the interpretation of closed H-surfaces in physical terms

A variational problem for closed H-surfaces contains conditions which firstly are not evident if compared with related geometrical problems. The formulation turns out to be quite natural, however, if the problem is derived from a mechanical one and hence can be interpreted in physical terms.     

A spreadsheet modelling approach to the assortment problem

A list of similar items of different sizes are required on a regular basis, but it is impractical to stock each of the different sizes. Demands for any size that is not stocked must be met by supplying the nearest acceptable size that is stocked, resulting in increased cost or trim wastage for example. The problem of determining which sizes should be stocked to minimise or maximise an appropriate objective function is formulated as a shortest or longest path problem on a directed acyclic network. A spreadsheet model is used to solve the problem, in such a way that showing precedents on the spreadsheet results in the basis tree for the shortest or longest path solution being drawn without the need for special software. The basis tree produced by this method is shown to be planar for practical applications, enabling improved efficiency of the algorithm used. Examples are given to illustrate the application of this approach.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Ordering the structural set of jobs,minimizing the total penalty

The problem of setting up a schedule minimizing the total penalty is solved. A job set is specified. There are no precedence conditions. Each job consists of elementary operations. Job interruptions are allowed. Interruptions of elementary operations are not allowed. The penalty for an operation of a job to be executed at instantt is. A schedule is evaluated by a penalty that is the sum of the penalties of all the elementary operations of all jobs in set. It is assumed that set is structural. The problem is to find the schedule with a start in a prescribed interval [ T₁,T₂] with the least penalty. Compatible structural schedules are introduced into consideration. The class of compatible structural schedules contains the solution of the problem. An algorithm solving the problem is proposed having complexity, in the worst case, whereK is the number of jobs in the set.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 90, pp. 229–264, 1979.     

On Some Generalizations of the Travelling-Salesman Problem

We discuss generalized travelling-salesman problems where nodes are visited either once or not, and a penalty cost is incurred for each unvisited node. The generalization includes the longest-path problem and the shortest-path problem with specified nodes to be visited. A new transformation of generalized into standard travelling-salesman problem is presented. We give computational results for the shortest-path problem with specified nodes. The transformation makes it possible to solve symmetric problems with a relatively large number of specified nodes, which cannot be solved by previously published algorithms based on a linear assignment relaxation. Furthermore, we show how to obtain improved lower bounds for a special Euclidean-type variant.     

Bounds on the Optimal Location to the Weber Problem under Conditions of Uncertainty

Optimal and Heuristic bounds are given for the optimal location to the Weber problem when the locations of demand points are not deterministic but may be within given circles. Rectilinear, Euclidean and square Euclidean types of distance measure are discussed. The exact shape of all possible optimal points is given in the rectilinear and square Euclidean cases. A heuristic method for the computation of the region of possible optimal points is developed in the case of Euclidean distance problem. The maximal distance between a possible optimal point and the deterministic solution is also computed heuristically.     

Review and comparison of three methods for the solution of the car sequencing problem

The car sequencing problem is the ordering of the production of a list of vehicles which are of the same type, but which may have options or variations that require higher work content and longer operation times for at least one assembly workstation. A feasible production sequence is one that does not schedule vehicles with options in such a way that one or more workstations are overloaded. In variations of the problem, other constraints may apply. We describe and compare three approaches to the modeling and solution of this problem. The first uses integer programming to model and solve the problem. The second approaches the question as a constraint satisfaction problem (CSP). The third method proposes an adaptation of the Ant Colony Optimization for the car sequencing problem. Test-problems are drawn from CSPLib, a publicly available set of problems available through the Internet. We quote results drawn both from our own work and from other research. The literature review is not intended to be exhaustive but we have sought to include representative examples and the more recent work. Our conclusions bear on likely research avenues for the solution of problems of practical size and complexity. A new set of larger benchmark problems was generated and solved. These problems are available to other researchers who may wish to solve them using their own methods.     

鲁棒动态设施选址问题的近似算法

设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务 (带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的 (带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。     

Embedding covers and the theory of frobenius fields

We show that the theory of Frobenius fields is decidable. This is conjectured in [4], [8] and [13], and we prove it by solving a group theoretic problem to which this question is reduced there. To do this we present and develop the notion of embedding covers of finite and pro-finite groups. We also answer two other problems from [8], again by solving a corresponding group theoretic problem: A finite extension of a Frobenius field need not be Frobenius and there are PAC fields which are not Frobenius fields. Portions of this work will be incorporated in the doctoral dissertation of the first author done in Tel Aviv University under the supervision of Prof. Moshe Jarden.     

On the existence and uniqueness of solutions in nonlinear complementarity theory

A complementarity problem is said to be globally uniquely solvable (GUS) if it has a unique solution, and this property will not change, even if any constant term is added to the mapping generating the problem.A characterization of the GUS property which generalizes a basic theorem in linear complementarity theory is given. Known sufficient conditions given by Cottle, Karamardian, and Moré for the nonlinear case are also shown to be generalized. In particular, several open questions concerning Cottle's condition are settled and a new proof is given for the sufficiency of this condition.A simple characterization for the two-dimensional case and a necessary condition for then-dimensional case are also given.The research described in this paper was carried out while N. Megiddo was visiting Tokyo Institute of Technology under a Fellowship of the Japan Society for the Promotion of Science.     

Computers and the Civil Engineer

The tasks engaged upon by a civil or structural engineer when designing a road or multistorey structure would appear to be ideal for digital computers. Some of the reasons why engineers do not use computers more heavily are examined and the fundamental difficulty due to the variable nature of the work is outlined. Some successful applications in structural and highway engineering are described where the calculation steps are sufficiently well ordered for a standard computer program to be successful. A new development, that of problem‐oriented language is described showing the advantages such systems have over conventional programs. Reference is made to GENESYS, a General Engineering System now being developed for the Ministry of Public Building and Works of the United Kingdom, which allows problem‐oriented languages to be devised for use in application.     

Tracking nonperiodic trajectories with the overtaking criterion

A tracking problem on an infinite time interval is studied, where the plant is linear with quadratic cost, and the tracked trajectory is not necessarily period. Optimal solutions with respect to the overtaking criterion are studied. Existence and uniqueness of such optimal solutions are proved and they are shown to be given by a linear feedback law which is the same as in the periodic case. A close relation between the solutions of tracking problems where the tracked trajectories are different only for very large times is established.     

The primal mixed finite element method and the LBB condition

Spurious or kinematic modes have posed a major obstacle to the implementation of the mixed finite element method. This research shows that spurious modes resulting from the approximation spaces not satisfying the LBB condition do not prevent a well posed problem. When the LBB condition is not satisfied, the resulting matrix equations are singular. A direct solution method is presented for the efficient solution of the possibly singular equations. Orthogonal flux basis functions are introduced to simplify the problem. Then the solution procedure is based on nested domain decomposition. This solution procedure is shown to be competitive with direct solution methods for the displacement finite element method. Examples are included to demonstrate various aspects of the LBB condition and the solution procedure.     

A neural network system for solving an assortment problem in the steel industry

A neural network model for solving an assortment problem found in the iron and steel industry is discussed in this paper. The problem arises in the yard where steel plate is cut into rectangular pieces. The neural network model can be categorized as a Hopfield model, but the model is expanded to handle inequality constraints. The idea of a penalty function is used. A large penalty is applied to the network if a constraint is not satisfied. The weights are updated based on the penalty values. A special term is added to the energy function of the network to guarantee the convergence of the neural network which has this feature. The performance of the neural network was evaluated by comparison with an existing expert system. The results showed that the neural network has the potential to identify in a short time near-optimal solutions to the assortment problem. The neural network is used as the core of a system for dealing with the assortment problem. In building the neural networks system for practical use, there were many implementation issues. Some of them are presented here, and the fundamental ideas are explained. The performance of the neural network system is compared to that of the expert system and evaluated from the practical viewpoint. The results show that the neural network system is useful in handling the assortment problem.     

Lagrange multipliers for regular and singular problems in the calculus of variations

A Lagrange multiplier rule is presented for a variational problem of Bolza type under hypotheses that allow certain components of the coefficient matrices involved in the functional being minimized to fail to be integrable near an endpoint of the interval on which the relevant functions are defined. The problem is also addressed when all coefficients are of classL ², but not necessarily bounded. Applications are made to ascertain properties of functions providing equality to certain singular and regular integral inequalities appearing in the literature.     

Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time

We consider the problem of scheduling multi-operation jobs on a singe machine to minimize the total completion time. Each job consists of several operations that belong to different families. In a schedule each family of job operations may be processed as batches with each batch incurring a set-up time. A job is completed when all of its operations have been processed. We first show that the problem is strongly NP-hard even when the set-up times are common and each operation is not missing. When the operations have identical processing times and either the maximum set-up time is sufficiently small or the minimum set-up time is sufficiently large, the problem can be solved in polynomial time. We then consider the problem under the job-batch restriction in which the operations of each batch is partitioned into operation batches according to a partition of the jobs. We show that this case of the problem can be solved in polynomial time under a certain condition.     

排课问题分组优化决策中的CourseRank

时间表(T im etab ling)问题是NP-完全的,因此很难寻求一个有效的整体优化算法.分组作为重要的优化策略,可以将课程按优先等级逐次分组,每组再采用组合优化方法.通常认为课程的规模是优先等级的决定性因素.然而选课的模式允许学生在一定的范围内选择课程,这就使得课程的关联关系更复杂.该文将课程的关联关系描述为一个M arkov链,进而给出了课程优先度(CourseR ank)的概念.通过对清华大学2002年度学生选课数据的分析和计算,结果表明课程的规模仍然是重要的因素,但并不完全是决定性的.     

一种部分约束满足车辆路线问题及其求解算法

描述了一类过度约束车辆路线问题，其中可用车辆数较少而时间窗口等其它约束又不允许放松，因而导致不存在满足所有约束的可行解。此时问题求解可以转化为一类部分约束满足问题来处理，相应的优化目标是最小化未访问顾客的损失和。本给出了求解这类特殊问题的一种禁忌搜索算法设计，并通过规模不同的几个算例与其它常用方法进行了比较。最后分析了模型和算法的实用意义。     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

Heuristics—the relational approach

A review of the literature on heuristics would suggest two approaches to their use in problem solving: mathematical and engineering. It is suggested however that there is a third approach for real world application, which the authors have called relational. Instead of investigating a problem through the medium of mathematical models and then deriving heuristics because direct optimising techniques are not available, it is advocated that a close relationship between problem owner and problem solver can be achieved by setting down together the decision rules that the owner employs. In this way, a heuristic model is developed directly, with the opportunity to introduce additional procedures as the situation allows. The result is a consistent control mechanism which is invaluable for both strategic and operational decision making. The model can be a predictor of the effects of policy decisions as well as a means by which those decisions can be implemented and monitored, dependent as much upon the balancing of sometimes conflicting objectives by management as upon the setting of bounds to achieve a guaranteed performance.