Search

We show how the performance of general purpose Mixed Integer Programming (MIP) solvers, can be enhanced by using the Semi-Lagrangian Relaxation (SLR) method. To illustrate this procedure we perform computational experiments on large-scale instances of the Uncapacitated Facility Location (UFL) problems with unknown optimal values. CPLEX solves 3 out of the 36 instances. By combining CPLEX with SLR, we manage to solve 18 out of the 36 instances and improve the best known lower bound for the other instances. The key point has been that, on average, the SLR approach, has reduced by more than 90% the total number of relevant UFL variables.

We evaluated reticulocyte counting and measurement of immature reticulocyte fraction (IRF) with the ABX PENTRA 120 Retic blood analyzer on 300 blood samples. Reticulocyte counts were compared with those obtained by visual counting of 2,000 RBCs, by the TOA (Kobe, Japan) Sysmex R-2000 and a flow cytometry method. The parameters analyzed were the percentages of reticulocytes on all analyzers and the IRF with different modalities. The Retic Count kit (Becton Dickinson, San Jose, CA) was used with the Coulter (Hialech, FL) XL, and a mean channel of fluorescence (MCF) was calculated to fit the reticulocyte maturation. Reticulocyte counting with the ABX (Montpellier, France) PENTRA 120 Retic showed excellent precision and linearity with no significant carryover. Reticulocyte counts were stable after blood storage for 72 hours at 4 degrees C but not at room temperature (RT). IRF parameters values were stable for only 8 hours at 4 degrees C and 6 hours at RT. Comparisons of the methods showed good intraclass correlation (RI) for reticulocyte percentages between ABX PENTRA 120 Retic and Sysmex R-2000, ABX PENTRA 120 Retic and flow cytometry, Sysmex R-2000 and flow cytometry, and ABX PENTRA 120 Retic and manual counting. IRF values were correlated between fluorescence rates and RNA content, but in each case, low RI values were found, showing that Sysmex and ABX IRF values were not concordant. We obtained a significant correlation between mean fluorescence index and the MCF measured by flow cytometry, but the 2 methods were not concordant using the RI. The ABX PENTRA 120 Retic is a good instrument for analyzing reticulocyte count and percentage and allows a good analysis of IRF with several modalities.

This paper addresses the issues involved with an interior point-based decomposition applied to the solution of linear programs with a block-angular structure. Unlike classical decomposition schemes that use the simplex method to solve subproblems, the approach presented in this paper employs a primal-dual infeasible interior point method. The above-mentioned algorithm offers a perfect measure of the distance to optimality, which is exploited to terminate the algorithm earlier (with a rather loose optimality tolerance) and to generate e-subgradients. In the decomposition scheme, subproblems are sequentially solved for varying objective functions. It is essential to be able to exploit the optimal solution of the previous problem when solving a subsequent one (with a modified objective). A warm start routine is described that deals with this problem. The proposed approach has been implemented within the context of two optimization codes freely available for research use: the Analytic Center Cutting Plane Method (ACCPM)—interior point based decomposition algorithm and the Higher Order Primal-Dual Method (HOPDM)—general purpose interior point LP solver. Computational results are given to illustrate the potential advantages of the approach applied to the solution of very large structured linear programs.

In this paper, we explore a weakness of a specific implementation of the analytic center cutting plane method applied to convex optimization problems, which may lead to weaker results than Kelley‘s cutting plane method. Improvements to the analytic center cutting plane method are suggested, and tested on some example problems.

In telecommunications network design, one of the key parameter is the set of requirements which in the past, were demands based on historical data and/or demographic predictions. Because of new technologies development and customers movement due to competitiveness, the requirements present considerable uncertainty. We propose a model for network design taking into account this uncertainty, which can be solved using linear programming techniques.

The aim of this tutorial paper is to present the relationship that exists between the control of singularly perturbed hybrid stochastic systems and the decomposition approach in structured linear programs The mathematical sophistication is voluntarily kept at a low level byavoiding the full development of the theorems demonstrations that can be found in papers already published or to appear shortly. On another hand, since it corresponds to a new application of a convex optimization method that has been successfully applied in other contexts, we give a rather detailed account of the decomposition technique used in the numerical approximation method and of the comparison with a direct linear programming method.

Publisher Summary Flow cytometry (FCM) is widely used to phenotype cases of acute leukemia and is important in their classification. When bone marrow (BM) is largely infiltrated by blasts, there is generally no problem to determine the phenotype of leukemic cells. However, in some cases of acute leukemia (especially most of acute myeloid leukemia, AML), a high degree of heterogeneity is the rule because both leukemic and normal cells are simultaneously present and blast cells themselves can be heterogeneous. The systematic use of leukocyte common antigen (LCA, CD45) marker in a multiple (≥3) immunofluorescence (IF) combination is demonstrated in this chapter to achieve a reliable and highly reproducible discrimination between the blast cell populations and the normal cells, showing that CD45/ side scatter (SSC) gating is a simple method to detect blast cells in large series of acute leukemia. CD45/SSC gating may provide a common platform for uniform data processing during the immunophenotyping of AML at diagnosis because it is considered as a useful bridge between cytology and immunophenotyping of leukemic diseases.

The capacitated multi-item lot sizing problem consists of finding a production schedule that minimizes over a finite number of periods the total production, holding inventory, and setup costs subject to demand and capacity constraints. The CLSP problem is NP-hard, while the problem of finding a feasible solution, which is polynomial if there are no set-up times, becomes NP-complete when set-up times are included. Approximate solutions can be obtained by heuristics. In this paper we consider an approach based on a Lagrangian relaxation of the capacity constraints. The relaxation is used in two ways. First, it generates a lower bound for the optimal value. Second, the primal and dual solutions of the relaxation (if available) are used to generate integer feasible solutions by primal or dual heuristics. We compare three methods of solving the Lagrangian relaxation: subgradient method, Kelley’s cutting plane method — also known as Dantzig-Wolfe decomposition — and the analytic center cutting plane method. We conclude that the analytic center cutting plane method performs as well, and sometimes better than subgradient optimization or Kelley’s cutting plane method.

The aim of this paper is to present the first experiments in using a new mathematical programming decomposition technique for solving multi-regional energy-environment planning models. The paper shows that: (i) the approach can be efficiently implemented for coupling several large-scale energy models; and (ii) the consideration of several European countries together indicates the benefits to be gained from an harmonization of a possible C02 tax.

This note is an erratum to Babonneau et al. (2006) in which some data were incorrectly described. In Babonneau et al. (2006), the ACCPM method is used to solve the linear multicommodity flow problem on four sets of instances, i.e., the planar and the grid instances, some telecommunication problems, and some transportation problems, from Bar-Gera (2007), http://www.bgu.ac.il/~bargera/tntp/ (Sioux Falls, Winnipeg, Barcelona, Chicago region, and Philadelphia). The mistakes concern the last category of instances. The new data and the associated results can now be found in the electronic companion at http://or.journal.informs.org/. This site also provides the full information on test instances in the multicommodity flow problem (MCF) and the traffic assignment problem to facilitate benchmarking. It gives the data and the results using three specific objective functions used in the literature, e.g., Bureau of Public Roads (BPR), Kleinrock, or linear. For more details on the optimization problem, we refer the reader to Babonneau et al. (2006) and Babonneau and Vial (2007).

In this paper we propose a new class of games, the “strategically zero-sum games,” which are characterized by a special payoff structure. We show that for a large body of correlation schemes which includes the correlated strategies “a la Aumann”, strategically zero-sum games are exactly these games for which no completely mixed Nash equilibrium can be improved upon.

This paper reports on a study undertaken to demonstrate the usefulness of optimization techniques to improve the performance of a plant for separation of natural gas.

This paper deals with the computation of the interior point cutting plane algorithm of Goffin, Haurie and Vial, with a special application to the solution of convex differentiable programming problems. The interior point cutting plane algorithm is closely related to the classical method of Cheney and Goldstein, and Kelley, but the cuts are generated from different, more central, points in order to achieve deeper cuts and thereby accelerate convergence. The method is quite general in purpose as it can be applied to a large class of convex differentiable and nondifferentiable optimization problems. The paper focuses on the different stages of a MATLAB implementation and the overall performance of the algorithm. The test problems come from a set of convex geometric programming problems.

The key issue in implementing a projective method is the projection operation. In order to cut down computations, several authors have suggested using approximations instead of the projection itself. However, these approximations are not directly compatible with the standard proofs of polynomial complexity. In this chapter we present a relaxation of the main convergence lemma which makes it possible to accommodate approximate projections. We propose several types of approximations that preserve polynomial complexity for the version of Karmarkar’s algorithm presented by de Ghellinck and Vial.

Continuity and Differentiability Properties of Monotone Real Functions of Several Real Variables (Y. Chabrillac, J.-P. Crouzeix). Regularity Properties of Open Tangent Cones (B. Cornet). The Role of Tangent and Normal Cones in the Viability Theory of Differential Inclusions (G. Haddad). Local Structure of Feasible Sets in Nonlinear Programming, Part III: Stability and Sensitivity (S.M. Robinson). Eigenvalue Perturbations and Nonlinear Parametric Optimization (B. Gollan). Curvilinear Path and Trust Region in Unconstrained Optimization: A Convergence Analysis (J.P. Bulteau and J.P. Vial). Numerical Methods for Nondifferentiable Convex Optimization (A. Auslender). A Reduced Subgradient Algorithm (A. Bihain, V.H. Nguyen, J.-J. Strodiot). Global Minimization of a Difference of Two Convex Functions (H. Tuy).

This paper reports on a study undertaken to demonstrate the usefulness of optimization techniques to improve the performance of a plant for separation of natural g?3.

International audience