A column generation algorithm for the vehicle routing problem with soft time windows

The Vehicle Routing Problem with Time Windows consists of computing a minimum cost set of routes for a fleet of vehicles of limited capacity visiting a given set of customers with known demand, with the additional constraint that each customer must be visited in a specified time window. We consider the case in which time window constraints are relaxed into “soft” constraints, that is penalty terms are added to the solution cost whenever a vehicle serves a customer outside of his time window. We present a branch-and-price algorithm which is the first exact optimization algorithm for this problem.     

Existence of minimizers for a class of quasi-convex functionals with non-standard growth

We study the lower semicontinuity properties of non-autonomous variational integrals whose energy densities satisfy general growth conditions. We apply these results to solve Dirichlet’s boundary value problems for such functionals. Received: June 14, 2000; in final form: November 25, 2000 Published online: December 19, 2001     

Graphical operations on projective spaces

Motivated by the work of Crapo and Rota [6] on the lifting of a projective complex, we introduce a class of invariant operations associated to integral-weighted graphs, which we call graphical operations. Such operations generalize the sixth harmonic of a quadranguler set on a projective line. We determine the expansion of the graphical operations in terms of multi-linear bracket polynomials in a Grassmann-Cayley algebra. Reducibility and compositions of such invariant operations are also investigated with a number of examples.Supported by Courant Instructorship, New York University.     

Local branching

The availability of effective exact or heuristic solution methods for general Mixed-Integer Programs (MIPs) is of paramount importance for practical applications. In the present paper we investigate the use of a generic MIP solver as a black-box ``tactical' tool to explore effectively suitable solution subspaces defined and controlled at a ``strategic' level by a simple external branching framework. The procedure is in the spirit of well-known local search metaheuristics, but the neighborhoods are obtained through the introduction in the MIP model of completely general linear inequalities called local branching cuts. The new solution strategy is exact in nature, though it is designed to improve the heuristic behavior of the MIP solver at hand. It alternates high-level strategic branchings to define the solution neighborhoods, and low-level tactical branchings to explore them. The result is a completely general scheme aimed at favoring early updatings of the incumbent solution, hence producing high-quality solutions at early stages of the computation. The method is analyzed computationally on a large class of very difficult MIP problems by using the state-of-the-art commercial software ILOG-Cplex 7.0 as the black-box tactical MIP solver. For these instances, most of which cannot be solved to proven optimality in a reasonable time, the new method exhibits consistently an improved heuristic performance: in 23 out of 29 cases, the MIP solver produced significantly better incumbent solutions when driven by the local branching paradigm. Mathematics Subject Classification (2000):90C06, 90C10, 90C11, 90C27, 90C59     

Projected Chvátal–Gomory cuts for mixed integer linear programs

Recent experiments by Fischetti and Lodi show that the first Chvátal closure of a pure integer linear program (ILP) often gives a surprisingly tight approximation of the integer hull. They optimize over the first Chvátal closure by modeling the Chvátal–Gomory (CG) separation problem as a mixed integer linear program (MILP) which is then solved by a general- purpose MILP solver. Unfortunately, this approach does not extend immediately to the Gomory mixed integer (GMI) closure of an MILP, since the GMI separation problem involves the solution of a nonlinear mixed integer program or a parametric MILP. In this paper we introduce a projected version of the CG cuts, and study their practical effectiveness for MILP problems. The idea is to project first the linear programming relaxation of the MILP at hand onto the space of the integer variables, and then to derive Chvátal–Gomory cuts for the projected polyhedron. Though theoretically dominated by GMI cuts, projected CG cuts have the advantage of producing a separation model very similar to the one introduced by Fischetti and Lodi, which can typically be solved in a reasonable amount of computing time. Gérard Cornuéjols was supported in part by NSF grant DMI-0352885, ONR grant N00014-03-1-0188, and ANR grant BLAN 06-1-138894. Matteo Fischetti was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2). Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2).     

Existence of strong minimizers for the Griffith static fracture model in dimension two

We consider the Griffith fracture model in two spatial dimensions, and prove existence of strong minimizers, with closed jump set and continuously differentiable deformation fields. One key ingredient, which is the object of the present paper, is a generalization to the vectorial situation of the decay estimate by De Giorgi, Carriero, and Leaci. This is based on replacing the coarea formula by a method to approximate $SB{D}^p$ functions with small jump set by Sobolev functions, and is restricted to two dimensions. The other two ingredients will appear in companion papers and consist respectively in regularity results for vectorial elliptic problems of the elasticity type and in a method to approximate in energy $GSB{D}^p$ functions by $SB{V}^p$ ones.     

Operator splitting for the numerical solution of free surface flow at low capillary numbers

Free surface flows are pervasive in engineering and biomedical applications. In many interesting cases—particularly when small length scales are involved—surface forces (capillarity) dominate the flow dynamics. In these cases, computing the flow together with the shape of the surfaces, requires specialized solution techniques. This article investigates the capabilities of an operator splitting/finite elements method at handling accurately incompressible viscous flow with free surfaces at low capillary numbers. The test case of flow in the downstream section of a slot coater is used for three reasons: (1) it is an established benchmark; (2) it represents an idealized, yet industrially relevant flow; (3) high-fidelity results obtained with monolithic algorithms are available in literature. The flow and free surface shape attained with the new operator splitting scheme agree very satisfactorily with the results obtained with monolithic solvers. Because of its inherent computational simplicity, the new operator splitting scheme is attractive for large-scale simulations, three-dimensional flows, and flows of complex fluids.     

Bump solutions for the mesoscopic Allen�CCahn equation in periodic media

Given a double-well potential F, a ${\mathbb{Z}^n}$ -periodic function H, small and with zero average, and ???>?0, we find a large R, a small ?? and a function H _?? which is ??-close to H for which the following two problems have solutions:

1. Find a set E _?? ,R whose boundary is uniformly close to ? B _R and has mean curvature equal to ?H _?? at any point,
2. Find u = u _?? ,R,?? solving $$ -\delta\,\Delta u + \frac{F'(u)}{\delta} +\frac{c_0}{2} H_\varepsilon = 0, $$ such that u _??,R,?? goes from a ??-neighborhood of +?1 in B _R to a ??-neighborhood of ?1 outside B _R .