Non-existence of extremals for the Adimurthi–Druet inequality

The Adimurthi–Druet [1] inequality is an improvement of the standard Moser–Trudinger inequality by adding a $L^2$-type perturbation, quantified by $\alpha \in [0,{\lambda }_1)$, where ${\lambda }_1$ is the first Dirichlet eigenvalue of Δ on a smooth bounded domain. It is known [3], [10], [14], [19] that this inequality admits extremal functions, when the perturbation parameter α is small. By contrast, we prove here that the Adimurthi–Druet inequality does not admit any extremal, when the perturbation parameter α approaches ${\lambda }_1$. Our result is based on sharp expansions of the Dirichlet energy for blowing sequences of solutions of the corresponding Euler–Lagrange equation, which take into account the fact that the problem becomes singular as $\alpha \to {\lambda }_1$.     

Some facets of the simple plant location polytope

We relate the simple plant location problem to the vertex packing problem and derive several classes of facets of their associated integer polytopes.This work was supported by NSF Grant ENG 79-02506.     

Analysis of relaxations for the multi-item capacitated lot-sizing problem

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP-hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items.Supported by NSF Grant ECS-8518970 and NSERC Grant OGP 0042197.