Convex compactness and its applications

The concept of convex compactness, weaker than the classical notion of compactness, is introduced and discussed. It is shown that a large class of convex subsets of topological vector spaces shares this property and that is can be used in lieu of compactness in a variety of cases. Specifically, we establish convex compactness for certain familiar classes of subsets of the set of positive random variables under the topology induced by convergence in probability. Two applications in infinite-dimensional optimization—attainment of infima and a version of the Minimax theorem—are given. Moreover, a new fixed-point theorem of the Knaster-Kuratowski-Mazurkiewicz-type is derived and used to prove a general version of the Walrasian excess-demand theorem.     

Distribution requirements and compactness constraints in school timetabling

This paper provides the following contributions: First, distribution requirements for lessons of different lengths are modelled in a novel way by the use of the so-called multiple mode concept with mode identity constraints. Second, we show that several types of constraints may be modelled using the unifying framework of partially renewable resources. Among these constraints are: No class, subject, room, and teacher overlaps; class, subject, room, and teacher unavailabilities; compactness constraints; preassignment constraints; lectures to be given simultaneously; lunch breaks, etc. Third, we present two-phase parallel greedy randomized and genetic methods. Fourth, we provide an instance generator for the generation of a representative set of instances. Fifth, the generator along with a statistical model is used for a thorough experimental evaluation of the methods. Computational results show that the methods solve the instances investigated close to optimality.     

The knapsack problem with neighbour constraints

We study a constrained version of the knapsack problem in which dependencies between items are given by the adjacencies of a graph. In the 1-neighbour knapsack problem, an item can be selected only if at least one of its neighbours is also selected. In the all-neighbours knapsack problem, an item can be selected only if all its neighbours are also selected.We give approximation algorithms and hardness results when the vertices have both uniform and arbitrary weight and profit functions, and when the dependency graph is directed and undirected.     

The isodiametric problem with lattice-point constraints

In this paper, the isodiametric problem for centrally symmetric convex bodies in the Euclidean d-space \Bbb R^d{\Bbb R}^d containing no interior non-zero point of a lattice L is studied. It is shown that the intersection of a suitable ball with the Dirichlet-Voronoi cell of 2L is extremal, i.e., it has minimum diameter among all bodies with the same volume. It is conjectured that these sets are the only extremal bodies, which is proved for all three dimensional and several prominent lattices.     

The isodiametric problem with lattice-point constraints

In this paper, the isodiametric problem for centrally symmetric convex bodies in the Euclidean d-space containing no interior non-zero point of a lattice L is studied. It is shown that the intersection of a suitable ball with the Dirichlet-Voronoi cell of 2L is extremal, i.e., it has minimum diameter among all bodies with the same volume. It is conjectured that these sets are the only extremal bodies, which is proved for all three dimensional and several prominent lattices. Authors’ addresses: M. A. Hernández Cifre, Departamento de Matemáticas, Universidad de Murcia, Campus de Espinardo, 30100-Murcia, Spain; A. Schürmann, Institut für Algebra und Geometrie, Otto-von-Guericke Universit?t Magdeburg, 39106 Magdeburg, Germany; F. Vallentin, Centrum voor Wiskunde en Informatica (CWI), Kruislaan 413, 1098 SJ Amsterdam, The Netherlands     

The {2}-inverse with applications in statistics

An inverse G of a given matrix A which satisfies the property GAG = G is known as a {2}-inverse. This paper presents a three-phase inversion procedure for which the {2}-inverse is a special case. We present the geometry of {2}-inverses and show that, starting from {2}-inverses, various types of generalized inverses can be derived. Two examples of the occurrence of {2}-inverses in statistics are given: one concerning the constrained least-squares estimator, the other concerning a necessary and sufficient condition for a quadratic form of singular multivariate normal variates to follow a chi-square distribution.     

The transportation problem with exclusionary side constraints

We consider the so-called Transportation Problem with Exclusionary Side Constraints (TPESC), which is a generalization of the ordinary transportation problem. We confirm that the TPESC is NP-hard, and we analyze the complexity of different special cases. For instance, we show that in case of a bounded number of suppliers, a pseudo-polynomial time algorithm exists, whereas the case of two demand nodes is already hard to approximate within a constant factor (unless P = NP). This research was partially supported by FWO Grant No. G.0114.03.     

The quickest path problem with batch constraints

The quickest path problem has been proposed to cope with flow problems through networks whose arcs are characterized by both travel times and flowrate constraints. Basically, it consists in finding a path in a network to transmit a given amount of items from a source node to a sink in as little time as possible, when the transmission time depends on both the traversal times of the arcs and the rates of flow along arcs. This paper is focused on the solution procedure when the items transmission must be partitioned into batches with size limits. For this problem we determine how many batches must be made and what the sizes should be.     

The financial equilibrium problem with implicit budget constraints

This paper presents the time-dependent, multi-agent and multi-activity financial equilibrium problem when budget constraints are implicitly defined. Specifically, we assume that total wealth is elastic with respect to the optimal investment. Such a problem is formulated as an infinite dimensional quasi-variational inequality for which an existence result is given.     

The problem of conflicting control with mixed constraints

The control problem for a linear dynamical system is considered at a minimax of the terminal quality index. Feasible controls are simultaneously restricted by geometrical constraints and by integrated momentum constraints, the latter being thought of as a store of control resources. The problem is formalized as a differential game [1–4] using concepts [5–8] developed at Ekaterinburg. Here, because of the geometrical constraints, the momentum formulation and its associated difficulties [2–4] do not appear. On the other hand the presence of the integral restrictions leads to the appearance of additional variables whose evolution describes the dynamics of the expenditure of the control resources. These variables are subject to phase restrictions, which is a peculiarity of the problem. A reasonably informative picture and a class of strategies for which the given game has a value and a saddle point are given. A constructive method for computing the value function of the game and constructing optimal strategies is presented. This method is conceptually related to the construction of a stochastic programming synthesis [5] and is based on the recursive construction of upper-convex envelopes for certain auxiliary functions. The possibility of exchanging the minimum and maximum operations over the resource parameters when calculating the value of the game using these procedure is established.     

The N-membrane problem with nonlocal constraints

In this paper, we study a nonlocal variational inequality. The nonlocality appears both in the coefficients of the operator, through an integral representing some elastic energy, and in the constraints, which are of the type called soft in the literature.     

Knapsack problem with probability constraints

This paper is dedicated to a study of different extensions of the classical knapsack problem to the case when different elements of the problem formulation are subject to a degree of uncertainty described by random variables. This brings the knapsack problem into the realm of stochastic programming. Two different model formulations are proposed, based on the introduction of probability constraints. The first one is a static quadratic knapsack with a probability constraint on the capacity of the knapsack. The second one is a two-stage quadratic knapsack model, with recourse, where we introduce a probability constraint on the capacity of the knapsack in the second stage. As far as we know, this is the first time such a constraint has been used in a two-stage model. The solution techniques are based on the semidefinite relaxations. This allows for solving large instances, for which exact methods cannot be used. Numerical experiments on a set of randomly generated instances are discussed below.     

The optimal portfolio problem with coherent risk measure constraints

One of the basic problems of applied finance is the optimal selection of stocks, with the aim of maximizing future returns and constraining risks by an appropriate measure. Here, the problem is formulated by finding the portfolio that maximizes the expected return, with risks constrained by the worst conditional expectation. This model is a straightforward extension of the classic Markovitz mean–variance approach, where the original risk measure, variance, is replaced by the worst conditional expectation.The worst conditional expectation with a threshold α of a risk X, in brief WCE_α(X), is a function that belongs to the class of coherent risk measures. These are measures that satisfy a set of properties, such as subadditivity and monotonicity, that are introduced to prevent some of the drawbacks that affect some other common measures.This paper shows that the optimal portfolio selection problem can be formulated as a linear programming instance, but with an exponential number of constraints. It can be solved efficiently by an appropriate generation constraint subroutine, so that only a small number of inequalities are actually needed.This method is applied to the optimal selection of stocks in the Italian financial market and some computational results suggest that the optimal portfolios are better than the market index.     

Compensated compactness for differential forms in Carnot groups and applications

In this paper we prove a compensated compactness theorem for differential forms of the intrinsic complex of a Carnot group. The proof relies on an Ls-Hodge decomposition for these forms. Because of the lack of homogeneity of the intrinsic exterior differential, Hodge decomposition is proved using the parametrix of a suitable 0-order Laplacian on forms.     

The transportation problem with exclusionary side constraints and two branch-and-bound algorithms

The transportation problem with exclusionary side constraints, a practical distribution and logistics problem, is formulated as a 0–1 mixed integer programming model. Two branch-and-bound (B&B) algorithms are developed and implemented in this study to solve this problem. Both algorithms use the Driebeek penalties to strengthen the lower bounds so as to fathom some of the subproblems, to peg variables, and to guide the selection of separation variables. One algorithm also strongly exploits the problem structure in selecting separation variables in order to find feasible solutions sooner. To take advantage of the underlying network structure of the problem, the algorithms employ the primal network simplex method to solve network relaxations of the problem. A computational experiment was conducted to test the performance of the algorithms and to characterize the problem difficulty. The commercial mixed integer programming software CPLEX and an existing special purpose algorithm specifically designed for this problem were used as benchmarks to measure the performance of the algorithms. Computational results show that the new algorithms completely dominate the existing special purpose algorithm and run from two to three orders of magnitude faster than CPLEX.