A truncated Newton method in an augmented Lagrangian framework for nonlinear programming

In this paper we propose a primal-dual algorithm for the solution of general nonlinear programming problems. The core of the method is a local algorithm which relies on a truncated procedure for the computation of a search direction, and is thus suitable for large scale problems. The truncated direction produces a sequence of points which locally converges to a KKT pair with superlinear convergence rate.     

Graded and Koszul Categories

Koszul algebras have arisen in many contexts; algebraic geometry, combinatorics, Lie algebras, non-commutative geometry and topology. The aim of this paper and several sequel papers is to show that for any finite dimensional algebra there is always a naturally associated Koszul theory. To obtain this, the notions of Koszul algebras, linear modules and Koszul duality are extended to additive (graded) categories over a field. The main focus of this paper is to provide these generalizations and the necessary preliminaries.     

Inverse Coefficient Problems for Elliptic Hemivariational Inequalities

This paper is devoted to a class of inverse coefficient problems for nonlinear elliptic hemivariational inequalities. The unknown coefficient of elliptic hemivariational inequalities depends on the gradient of the solution and belongs to a set of admissible coefficients. It is shown that the nonlinear elliptic hemivariational inequalities are uniquely solvable for the given class of coefficients. The result of existence of quasisolutions of the inverse problems is obtained.     

Timetabling for Greek high schools

The timetabling process and the resulting weekly schedules are important components for the daily operation of any school. This paper presents an efficient solution to the timetabling problem for the secondary educational system in Greece. Such a problem involves scheduling a large number of classes, teachers, courses, and classrooms to a number of time-periods. The development of the basic structure and the modelling of the problem as an integer mathematical program allows for the generation of constraints necessary for the satisfaction of all the school system rules and regulations. The integer programming approach and the commercial tools available for this class of problems facilitated the process of locating the optimal solution for the problem. The model is flexible and modular allowing for adaptations to satisfy the local characteristics of each school by changing the parameters of the model and adding or replacing constraints. A fully defined timetabling problem for a typical Greek high school is presented and optimally solved in order to demonstrate the effectiveness of the model in satisfying both the hard and the soft operational rules of the problem. Implementation of the new methodology for regular use for high schools is currently being attempted.     

A Cutting Planes Algorithm for the <Emphasis Type="Italic">m</Emphasis>-Salesmen Problem

The existence of reliable and flexible FORTRAN programs for integer linear programming has recently enabled the development of very efficient algorithms for the travelling salesman problem. The main characteristic of these algorithms is the relaxation of most of the constraints of the problem during its solution. The same approach can be used for the solution of the m-salesmen problem in which m salesmen starting from the same city must visit only once n cities at minimum cost. The number of salesmen can be fixed in advance or allowed to vary, upper and lower bounds set on the number of salesmen and even fixed costs associated with the salesmen. The results obtained so far are very encouraging. Problems of up to 100 cities have been solved optimally for the m-travelling salesmen case and other more complex problems are currently under study.     

Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points

The problem of scheduling delivery vehicles from a number of depots to customers, subject to constraints on load and distance or time, is considered. A new algorithm is presented; this allows routes from several depots to be constructed simultaneously, subject to restrictions on numbers of vehicles at individual depots. Where too many customers require service, a flexible priority rule will select those to be served. Results for the single depot case are compared with other known algorithms; further results are given and discussed for cases of several depots.     

Sui fasci di cubiche a modulo costante

An improvement of the uniqueness theorem of Wintner for the differential equationx ⁽ⁿ⁾(t)=f(t, x) is given.     

Methods for Determining the Re-order Point of an (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">S</Emphasis>) Ordering Policy when a Service Level is Specified

This paper deals with a periodic review inventory system. Methods are discussed for determining the re-order point s of an (s, S) order policy, when a certain service level is required. The results differ from those presented for a (Q, s) model which is usually considered in literature and implemented in practice. Methods are discussed for determining the re-order point of an (s, S) policy when demand is normal or gamma distributed. A numerical investigation demonstrates the applicability of the described methods. In particular, it is shown that these methods are superior to a formula that is implemented in many inventory control systems.     

A Fair Allocation of County Cricket Opponents

Each team in the English County Cricket Championship plays against some other teams twice a year, and others only once. This paper describes a case study whose aim was to overcome this inherent unfairness by producing a four-year schedule of opponents which was as fair as possible, and could be easily seen to be fair, while still allowing for traditional rivalries. The schedule also needed to be satisfactory in regard to several other constraints and objectives. Various simple heuristics were used; these are described in some detail. Of particular interest is the effectiveness of a ‘local non-worsening’ approach when the objective is to find any feasible solution. This is equivalent to simulated annealing at a constant temperature of absolute zero.