Bilevel multiplicative problems: A penalty approach to optimality and a cutting plane based algorithm

Bilevel programming has been proposed for dealing with decision processes involving two decision makers with a hierarchical structure. They are characterised by the existence of two optimisation problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimisation problem. In this paper we focus on the class of bilevel problems in which the upper level objective function is linear multiplicative, the lower level one is linear and the common constraint region is a bounded polyhedron. After replacing the lower level problem by its Karush–Kuhn–Tucker conditions, the existence of an extreme point which solves the problem is proved by using a penalty function approach. Besides, an algorithm based on the successive introduction of valid cutting planes is developed obtaining a global optimal solution. Finally, we generalise the problem by including upper level constraints which involve both level variables.     

The classical decision problem and partial functions

We consider the decision problem for sets of sentences of first-order logic when instead of interpreting function symbols as total functions over the universe of a model (henceforth referred to as the usual interpretation) we interpret them as partial functions.We consider only standard classes, which are certain sets of prenex sentences specified by restrictions on the prefix and on the numbers ofk-place predicate and function symbols for eachk1. Standard classes are introduced in [1] and it is proved there that the decision problem for any set of prenex sentences specified by such restrictions reduces to that for the standard classes.We solve the decision problem completely for standard classes with at least one function symbol and both with and without equality.This problem was suggested to me by my supervisor, Professor Yuri Gurevich who was confident that the results would be very similar to those for the usual interpretation and could be achieved by similar techniques.     

An inner amenable group whose von Neumann algebra does not have property Gamma

We construct inner amenable groups G with infinite conjugacy classes and such that the associated II₁ factor has no non-trivial asymptotically central elements, i.e. does not have property Gamma of Murray and von Neumann. This solves a problem posed by Effros in 1975.     

Scheduling for Known but Irregular Batch-Wise Demand

The paper deals with the batch size problem, given that demand is batch-wise and the times and quantities of the first n demands are known. This is found to be a problem in dynamic programming.A treatment is devised which may often enable that part of the demand to be scheduled optimally which must be procured before further information becomes available; which solves the problem in such cases. In other cases the final decision between the surviving possibilities may have to be based on possibly non-optimal criteria. Where it is known that the nth demand is the last, the problem can be solved completely.Details of computational methods are given, including worked examples. The methods appear suitable for computer programming, but are in any case (relatively) fast by hand; a solution may normally be obtained in, say, 5n minutes or less, except where the individual demands are much smaller than the optimum batch size (in which case other—approximate—methods may be preferred and would be unlikely to incur much penalty).     

A decision procedure using discrete geometry

A decision procedure is given which makes essential use of concepts in discrete geometry. The procedure decides for any one-state Turing machine with three-dimensional tape, whether or not it has an immortal configuration, i.e., it solves the uniform halting problem for such devices. The history and significance of the problem is examined. The solution is given with the main motivation of showing how traditional mathematical concepts can be used in decision procedures. The paper is introductory in the sense that all notions are carefully defined.     

Counting unrooted maps on the plane

A planar map is a 2-cell embedding of a connected planar graph, loops and parallel edges allowed, on the sphere. A plane map is a planar map with a distinguished outside (“infinite”) face. An unrooted map is an equivalence class of maps under orientation-preserving homeomorphism, and a rooted map is a map with a distinguished oriented edge. Previously we obtained formulae for the number of unrooted planar n-edge maps of various classes, including all maps, non-separable maps, eulerian maps and loopless maps. In this article, using the same technique we obtain closed formulae for counting unrooted plane maps of all these classes and their duals. The corresponding formulae for rooted maps are known to be all sum-free; the formulae that we obtain for unrooted maps contain only a sum over the divisors of n. We count also unrooted two-vertex plane maps.     

Disjoint congruence classes and a timetabling application

We consider a combinatorial problem motivated by a special simplified timetabling problem for subway networks. Mathematically the problem is to find (pairwise) disjoint congruence classes modulo certain given integers; each such class corresponds to the arrival times of a subway line of a given frequency. For a large class of instances we characterize when such disjoint congruence classes exist and how they may be determined. We also study a generalization involving a minimum distance requirement between congruence classes, and a comparison of different frequency families in terms of their “efficiency”. Finally, a general method based on integer programming is also discussed.     

THE DECISION PROBLEM FOR RESTRICTED UNIVERSAL QUANTIFICATION IN SET THEORY AND THE AXIOM OF FOUNDATION

The still unsettled decision problem for the restricted purely universal formulae ((?)₀-formulae) of the first order set-theoretic language based over =, ∈ is discussed in relation with the adoption or rejection of the axiom of foundation. Assuming the axiom of foundation, the related finite set-satisfiability problem for the very significant subclass of the (?)₀-formulae consisting of the formulae involving only nested variables of level 1 is proved to be semidecidable on the ground of a reflection property over the hereditarily finite sets, and various extensions of this result are obtained. When variables are restricted to range only over sets, in universes with infinitely many urelements the set-satisfiability problem is shown to be solvable provided the axiom of foundation is assumed; if it is not, then the decidability of a related derivability problem still holds. That, in turn, suggests the alternative adoption of an antifoundation axiom under which the set-satisfiability problem is also solvable (of course with different answers). Turning to set theory without urelements, assuming a form of Boffa's antifoundation axiom, the complement of the set-satisfiability problem for the full class of Δ₀-formulae is shown to be semidecidable; a result that is known not to hold, for the set-satisfiability problem itself, even for a very restricted subclass of the Δ₀-formulae.     

Budgeting with bounded multiple-choice constraints

We consider a budgeting problem where a specified number of projects from some disjoint classes has to be selected such that the overall gain is largest possible, and such that the costs of the chosen projects do not exceed a fixed upper limit. The problem has several application in government budgeting, planning, and as relaxation from other combinatorial problems. It is demonstrated that the problem can be transformed to an equivalent multiple-choice knapsack problem through dynamic programming. A naive transformation however leads to a drastic increase in the number of variables, thus we propose an algorithm for the continuous problem based on Dantzig–Wolfe decomposition. A master problem solves a continuous multiple-choice knapsack problem knowing only some extreme points in each of the transformed classes. The individual subproblems find extreme points for each given direction, using a median search algorithm. An integer optimal solution is then derived by using the dynamic programming transformation to a multiple-choice knapsack problem for an expanding core. The individual classes are considered in an order given by their gradients, and the transformation to a multiple-choice knapsack problem is performed when needed. In this way, only a dozen of classes need to be transformed for standard instances from the literature. Computational experiments are presented, showing that the developed algorithm is orders of magnitude faster than a general LP/MIP algorithm.     

The computable embedding problem

Calvert calculated the complexity of the computable isomorphism problem for a number of familiar classes of structures. Rosendal suggested that it might be interesting to do the same for the computable embedding problem. By the computable isomorphism problem and (computable embedding problem) we mean the difficulty of determining whether there exists an isomorphism (embedding) between two members of a class of computable structures. For some classes, such as the class of \mathbbQ \mathbb{Q} -vector spaces and the class of linear orderings, it turns out that the two problems have the same complexity. Moreover, calculations are essentially the same. For other classes, there are differences. We present examples in which the embedding problem is trivial (within the class) and the computable isomorphism problem is more complicated. We also give an example in which the embedding problem is more complicated than the isomorphism problem.     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.     

Theory and use of functionals on the class of nonnegative polynomials and quadrature formulae

A functional of special type on classes of nonnegative polynomials is studied, which is helpful for the investigation of packings and cubature formulae. This functional in the classical case plays a very important role in analysis. The corresponding extremal problem is solved with the help of Legendre and Jacobi polynomials. Also, a new set of Gaussian quadrature formulae is obtained and used for two-dimensional integrals with circular symmetry.     

On Romanovski–Jacobi polynomials and their related approximation results

The aim of this article is to present the essential properties of a finite class of orthogonal polynomials related to the probability density function of the F -distribution over the positive real line. We introduce some basic properties of the Romanovski–Jacobi polynomials, the Romanovski–Jacobi–Gauss type quadrature formulae and the associated interpolation, discrete transforms, spectral differentiation and integration techniques in the physical and frequency spaces, and basic approximation results for the weighted projection operator in the nonuniformly weighted Sobolev space. We discuss the relationship between such kinds of finite orthogonal polynomials and other classes of infinite orthogonal polynomials. Moreover, we derive spectral Galerkin schemes based on a Romanovski–Jacobi expansion in space and time to solve the Cauchy problem for a scalar linear hyperbolic equation in one and two space dimensions posed in the positive real line. Two numerical examples demonstrate the robustness and accuracy of the schemes.     

Extreme points in polyhedral Banach spaces

We show that there exists a polyhedral Banach space X such that the closed unit ball of X is the closed convex hull of its extreme points. This solves a problem posed by J. Lindenstrauss in 1966.     

A local search heuristic for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity $k$ -splittable Maximum Flow Problem consists of maximizing the amount of flow routed through a network such that each commodity uses at most $k$ paths and such that edge capacities are satisfied. The problem is $\mathcal NP $ -hard and has application in a.o. telecommunications. In this paper, a local search heuristic for solving the problem is proposed. The heuristic is an iterative shortest path procedure on a reduced graph combined with a local search procedure to modify certain path flows and prioritize the different commodities. The heuristic is tested on benchmark instances from the literature and solves 83 % of the instances to optimality. For the remaining instances, the heuristic finds good solution values which on average are 1.04 % from the optimal. The heuristic solves all instances in less than a second. Compared to other heuristics, the proposed heuristic again shows superior performance with respect to solution quality.     

A black-box scatter search for optimization problems with integer variables

The goal of this work is the development of a black-box solver based on the scatter search methodology. In particular, we seek a solver capable of obtaining high quality outcomes to optimization problems for which solutions are represented as a vector of integer values. We refer to these problems as integer optimization problems. We assume that the decision variables are bounded and that there may be constraints that require that the black-box evaluator is called in order to know whether they are satisfied. Problems of this type are common in operational research areas of applications such as telecommunications, project management, engineering design and the like.Our experimental testing includes 171 instances within four classes of problems taken from the literature. The experiments compare the performance of the proposed method with both the best context-specific procedures designed for each class of problem as well as context-independent commercial software. The experiments show that the proposed solution method competes well against commercial software and that can be competitive with specialized procedures in some problem classes.     

Existence of Polyhedral Embeddings of Graphs

It is proved that the decision problem about the existence of an embedding of face-width 3 of a given graph is NP-complete. A similar result is proved for some related decision problems. This solves a problem raised by Neil Robertson. Received July 6, 1998 RID="*" ID="*" Supported in part by the Ministry of Science and Technology of Slovenia, Research Project J1–0502–0101–98.