Automatic Dantzig–Wolfe reformulation of mixed integer programs

Mathematical Programming - Dantzig–Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the...     

A branch-and-price algorithm for the two-dimensional level strip packing problem

The two-dimensional level strip packing problem (2LSPP) consists in packing rectangular items of given size into a strip of given width divided into levels. Items packed into the same level cannot be put on top of one another and their overall width cannot exceed the width of the strip. The objective is to accommodate all the items while minimizing the overall height of the strip. The problem is -hard and arises from applications in logistics and transportation. We present a set covering formulation of the 2LSPP suitable for a column generation approach, where each column corresponds to a feasible combination of items inserted into the same level. For the exact optimization of the 2LSPP we present a branch-and-price algorithm, in which the pricing problem is a penalized knapsack problem. Computational results are reported for benchmark instances with some hundreds items.     

Modeling and solving profitable location and distribution problems

In this paper we present a general framework for tackling combined location and routing problems (LRPs), involving both costs and profits at the same time. Our framework is based on an extended model and a unified branch-and-cut-and-price method, using dynamic programming pricing routines, strengthening cuts, primal heuristics, stabilization and ad-hoc branching rules to exactly solve LRPs. First we describe our framework, discussing its algorithmic components. Then, we consider as a test case three problems from the literature, with increasing relative importance of the location decisions over the routing ones, and we analyze the performance of our framework for solving them. The first result of our investigation is to assess the tradeoff between modeling detail and computational effectiveness in tackling LRPs. At the same time, we also show that our integrated exact approach is effective for these problems.     

A molecular dynamics study of structure, stability and fragmentation patterns of sodium bis(2-ethylhexyl)sulfosuccinate positively charged aggregates in vacuo

Positively charged supramolecular aggregates formed in vacuo by n AOTNa (sodium bis(2-ethylhexyl)sulfosuccinate) molecules and n(c) additional sodium ions, i.e. [AOT(n)Na(n+n(c))](n(c)), have been investigated by molecular dynamics (MD) simulations for n = 1-20 and n(c) = 0-5. Statistical analysis of physical quantities like gyration radii, atomic B-factors and moment of inertia tensors provides detailed information on their structural and dynamical properties. Even for n(c) = 5, all stable aggregates show a reverse micelle-like structure with an internal solid-like core including sodium counterions and surfactant polar heads surrounded by an external layer consisting of the surfactant alkyl chains. Moreover, the aggregate shapes may be approximated by rather flat and elongated ellipsoids whose longer axis increases with n and n(c). The fragmentation patterns of a number of these aggregates have also been examined and have been found to markedly depend on the aggregate charge state. In one particular case, for which experimental findings are available in the literature, a good agreement is found with the present fragmentation data.     

A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows

The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongoing industrial project. First we propose an exact branch-and-price algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.     

Molecular dynamics of electrosprayed water nanodroplets containing sodium bis(2‐ethylhexyl)sulfosuccinate

The behavior of aqueous solutions of sodium bis(2‐ethylhexyl)sulfosuccinate (AOTNa) subject to electrospray ionization (ESI) has been investigated by molecular dynamics (MD) simulations at three temperatures (350, 500 and 800 K). We consider several types of water nanodroplets containing AOTNa molecules and composed of a fixed number of water molecules (1000), N⁰_AOT AOT^? anions (N⁰_AOT = 0, 5, 10) and N⁰_Na sodium ions (N⁰_Na = 0, 5, 10, 15, 20): in a short time scale (less than 1 ns), the AOTNa molecules, initially forming direct micelles in the interior of the water nanodroplets, are observed in all cases to diffuse nearby the nanodroplet surface, so that the hydrophilic heads and sodium ions become surrounded by water molecules, whereas the alkyl chains lay at the droplet surface. Meanwhile, evaporation of water molecules and of solvated sodium ions occurs, leading to a decrease of the droplet size and charge. At 350 K, no ejection of neutral or charged surfactant molecules is observed, whereas at 500 K, some fragmentation occurs, and at 800 K, this event becomes more frequent. The interplay of all these processes, which depend on the values of temperature, N⁰_AOT and N⁰_Na eventually leads to anhydrous charged surfactant aggregates with prevalence of monocharged ones, in agreement with experimental results of ESI mass spectrometry. The quantitative analysis of the MD trajectories allows to evidence molecular details potentially useful in designing future ESI experimental conditions. Copyright © 2013 John Wiley & Sons, Ltd.     

A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

In this paper we consider a variation of the bin packing problem in which bins of different types have different costs and capacities. Furthermore, each bin has to be filled at least to a certain level, which depends on its type. We present a set partitioning formulation and an exact optimization algorithm which exploits column generation and specialized heuristics. We compare our algorithm with the general purpose solver ILOG CPLEX, running on two compact ILP formulations and we report on experimental results on instances we have generated from data-sets for the variable size bin packing problem.     

Structure,Stability, and Fragmentation of Sodium bis(2-ethylhexyl)Sulfosuccinate Negatively Charged Aggregates In Vacuo by MD Simulations

Negatively charged supramolecular aggregates formed in vacuo by n bis(2-ethylhexyl)sulfosuccinate (AOT^–) anions and n + n _c sodium counterions (i.e., [AOT _n Na _n+nc ] ^nc ) have been investigated by molecular dynamics (MD) simulations for n = 1 to 20 and n _c = –1 to –5. By comparing the maximum excess charge values of negatively and positively charged AOTNa aggregates, it is found that the charge storage capability is higher for the latter systems, the difference decreasing as the aggregation number increases. Statistical analysis of physical properties like gyration radii and moment of inertia tensors of aggregates provides detailed information on their structural properties. Even for n _c = –5, all stable aggregates show a reverse micelle-like structure with an internal core, including sodium counterions and surfactant polar heads, surrounded by an external layer consisting of the surfactant alkyl chains. Interestingly, the reverse micelle-like structure is retained also in proximity of fragmentation. Moreover, the aggregate shapes may be approximated by elongated ellipsoids whose longer axis increases with n and |n _c |. The fragmentation patterns of a number of these aggregates have also been examined and have been found to markedly depend on the aggregate charge state. The simulated fragmentation patterns of a representative aggregate show good agreement with experimental data obtained using low collision voltages. Figure

?     

A computational evaluation of a general branch-and-price framework for capacitated network location problems

The purpose of this paper is to illustrate a general framework for network location problems, based on column generation and branch-and-price. In particular we consider capacitated network location problems with single-source constraints. We consider several different network location models, by combining cardinality constraints, fixed costs, concentrator restrictions and regional constraints. Our general branch-and-price-based approach can be seen as a natural counterpart of the branch-and-cut-based commercial ILP solvers, with the advantage of exploiting the tightness of the lower bound provided by the set partitioning reformulation of network location problems. Branch-and-price and branch-and-cut are compared through an extensive set of experimental tests.     

Combining very large scale and ILP based neighborhoods for a two-level location problem

In this paper we tackle a generalization of the Single Source Capacitated Facility Location Problem in which two sets of facilities, called intermediate level and upper level facilities, have to be located; the dimensioning of the intermediate set, the assignment of clients to intermediate level facilities, and of intermediate level facilities to upper level facilities, must be optimized, as well. Such problem arises, for instance, in telecommunication network design: in fact, in hierarchical networks the traffic arising at client nodes often have to be routed through different kinds of facility nodes, which provide different services. We propose a heuristic approach, based on very large scale neighborhood search to tackle the problem, in which both ad hoc algorithms and general purpose solvers are applied to explore the search space. We report on experimental results using datasets from the capacitated location literature. Such results show that the approach is promising and that Integer Linear Programming based neighborhoods are significantly effective.