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...     

An approximation scheme for the two-stage,two-dimensional knapsack problem

We present an approximation scheme for the two-dimensional version of the knapsack problem which requires packing a maximum-area set of rectangles in a unit square bin, with the further restrictions that packing must be orthogonal without rotations and done in two stages. Achieving a solution which is close to the optimum modulo a small additive constant can be done by taking wide inspiration from an existing asymptotic approximation scheme for two-stage two-dimensional bin packing. On the other hand, getting rid of the additive constant to achieve a canonical approximation scheme appears to be widely nontrivial.     

Optimal linear arrangements using betweenness variables

We solve for the first time to proven optimality the small instances in the classical literature benchmark of Minimum Linear Arrangement. This is achieved by formulating the problem as an ILP in a somehow unintuitive way, using variables expressing the fact that a vertex is between two other adjacent vertices in the arrangement. Using (only) these variables appears to be the key idea of the approach. Indeed, with these variables already the use of very simple constraints leads to good results, which can however be improved with a more detailed study of the underlying polytope.     

Packing into the smallest square: Worst-case analysis of lower bounds

We address the problem of packing a given set of rectangles into the minimum size square. We consider three versions of the problem, arising when the rectangles (i) are squares; (ii) have a fixed orientation; (iii) can be rotated by 90. For each case we study lower bounds, and analyze their worst-case performance ratio. In addition, we evaluate through computational experiments their average performance on instances from the literature.     

{0, 1/2}-Chvátal-Gomory cuts

Given the integer polyhedronP _t := conv{x ∈ℤ ⁿ :Ax⩽b}, whereA ∈ℤ ^{m × n} andb ∈ℤ ^m , aChvátal-Gomory (CG)cut is a valid inequality forP ₁ of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ ₊ ^m such that λτA∈ℤ ⁿ . In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2} ^m . We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of strong inequalities forP ₁. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.     

Spin-fluctuation mediated high-temperature ferromagnetism in Si:Mn dilute magnetic semiconductors

We discuss a possible route to explain high-temperature ferromagnetism in Si:Mn dilute magnetic semiconductors. We argue that most Mn atoms are segregated within nanometer-sized regions of magnetic precipitate and form the alloy, or compound, MnSi_{2 -z} with z ≈ (0.25?\div0.30), whereas a small minority of Mn atoms forms ?ngstr?m-sized magnetic defects embedded in the host. Assuming that MnSi_{2 -z} is a weak itinerant ferromagnet which supports sizable spin fluctuations (paramagnons) far above the intrinsic Curie temperature, we show that the Stoner enhancement of the exchange interaction between the local magnetic moments of the defects occurs. As a result, a significant increase of the temperature of global ferromagnetic order in the system is achieved. We develop a phenomenological approach, to qualitatively describe this effect.     

Charge-fluctuation contribution to the Raman response in superconducting cuprates

We calculate the Raman response contribution due to soft collective modes, finding a strong dependence on the photon polarizations and on the characteristic wave vectors of the modes. We compare our results with recent Raman spectroscopy experiments in underdoped cuprates, La2-xSrxCuO4 and (Y1.97Ca0.3)Ba2CuO6.05, where anomalous low-energy peaks are observed, which soften upon lowering the temperature. We show that the specific dependence on doping and on photon polarizations of these peaks can naturally arise from charge collective excitations at finite wavelength.     

Gap and pseudogap evolution within the charge-ordering scenario for superconducting cuprates

We describe the spectral properties of underdoped cuprates as resulting from a momentum-dependent pseudogap in the normal-state spectrum. Such a model accounts, within a BCS approach, for the doping dependence of the critical temperature and for the two-parameter leading-edge shift observed in the cuprates. By introducing a phenomenological temperature dependence of the pseudogap, which finds a natural interpretation within the stripe quantum-critical-point scenario for high- superconductors, we reproduce also the bifurcation near optimum doping. Finally, we briefly discuss the different role of the gap and the pseudogap in determining the spectral and thermodynamical properties of the model at low temperatures. Received 17 February 2000     

New techniques for cost sharing in combinatorial optimization games

Combinatorial optimization games form an important subclass of cooperative games. In recent years, increased attention has been given to the issue of finding good cost shares for such games. In this paper, we define a very general class of games, called integer minimization games, which includes the combinatorial optimization games in the literature as special cases. We then present new techniques, based on row and column generation, for computing good cost shares for these games. To illustrate the power of these techniques, we apply them to traveling salesman and vehicle routing games. Our results generalize and unify several results in the literature. The main underlying idea is that suitable valid inequalities for the associated combinatorial optimization problems can be used to derive improved cost shares.