Optimization of modular machining lines

The paper summarizes the main results of the author’s Ph.D. thesis presented in December 2006 at the école des Mines de Saint étienne. The work was supervised by Alexandre Dolgui and Xavier Delorme. The thesis is written in French and is available upon request from the author. Its purpose is to provide decision support in the design and reconfiguration of modular machining lines with multi-spindle units. This design problem is defined as the selection of spindle units to perform a set of operations needed to produce the parts and subsequently their assignment to workstations. The corresponding optimization problem is solved using different models based on integer and constraint programming.      

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.     

MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry

An efficient systematic iterative solution strategy for solving real-world scheduling problems in multiproduct multistage batch plants is presented. Since the proposed method has its core a mathematical model, two alternative MIP scheduling formulations are suggested. The MIP-based solution strategy consists of a constructive step, wherein a feasible and initial solution is rapidly generated by following an iterative insertion procedure, and an improvement step, wherein the initial solution is systematically enhanced by implementing iteratively several rescheduling techniques, based on the mathematical model. A salient feature of our approach is that the scheduler can maintain the number of decisions at a reasonable level thus reducing appropriately the search space. A fact that usually results in manageable model sizes that often guarantees a more stable and predictable optimization model behavior. The proposed strategy performance is tested on several complicated problem instances of a multiproduct multistage pharmaceuticals scheduling problem. On average, high quality solutions are reported with relatively low computational effort. Authors encourage other researchers to adopt the large-scale pharmaceutical scheduling problem to test on it their solution techniques, and use it as a challenging comparison reference.     

MILP approach to pattern generation in logical analysis of data

Pattern generation methods for the Logical Analysis of Data (LAD) have been term-enumerative in nature. In this paper, we present a Mixed 0-1 Integer and Linear Programming (MILP) approach that can identify LAD patterns that are optimal with respect to various previously studied and new pattern selection preferences. Via art of formulation, the MILP-based method can generate optimal patterns that also satisfy user-specified requirements on prevalence, homogeneity and complexity. Considering that MILP problems with hundreds of 0-1 variables are easily solved nowadays, the proposed method presents an efficient way of generating useful patterns for LAD. With extensive experiments on benchmark datasets, we demonstrate the utility of the MILP-based pattern generation.     

A new mixed integer programming formulation for facility layout design using flexible bays

This paper presents a mixed-integer programming formulation to find optimal solutions for the block layout problem with unequal departmental areas arranged in flexible bays. The nonlinear department area constraints are modeled in a continuous plane without using any surrogate constraints. The formulation is extensively tested on problems from the literature.     

A simulated annealing algorithm for transient optimization in gas networks

In this paper we present a simulated annealing approach for the gas network optimization problem. A gas network consists of a set of pipes to transport the gas from the sources to the sinks whereby gas pressure gets lost due to friction. Further on there are compressors, which increase gas pressure, and valves. The aim is to minimize fuel gas consumption of the compressors whereas demands of consumers have to be satisfied. The problem of transient (time-dependent) optimization of gas networks results in a highly complex mixed integer nonlinear program. We relax the equations describing the gas dynamic in pipes by adding these constraints combined with appropriate penalty factors to the objective function. A suitable neighborhood structure is developed for the relaxed problem where time steps as well as pressure and flow of the gas are decoupled. Our approach convinces with flexibility and very good computational results.     

An epsilon-free approach for finding the most efficient unit in DEA

Data envelopment analysis (DEA), considering the best condition for each decision making unit (DMU), assesses the relative efficiency and partitions DMUs into two sets: efficient and inefficient. Practically, in traditional DEA models more than one efficient DMU are recognized and these models cannot rank efficient DMUs. Some studies have been carried out aiming at ranking efficient DMUs, although in some cases only discrimination of the most efficient unit is desirable. Furthermore, several investigations have been done for finding the most CCR-efficient DMU. The basic idea of the majority of them is to introduce an integrated model which achieves an optimal common set of weights (CSW). These weights help us identify the most efficient unit in an identical condition.     

A hybrid approach for optimal design of signalized road network

For a signalized road network with expansions of link capacity, the maximum possible increase in travel demands is considered while total delays for travelers are minimized. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum possible increase in travel demand and determining optimal link capacity expansions can be formulated as optimization programs. In this paper, we present a new solution approach for simultaneously solving the maximum increase in travel demands and minimizing total delays of travelers. A projected Quasi-Newton method is proposed to effectively solve this problem to the KKT points. Numerical computations and comparisons are made on real data signal-controlled networks where obtained results outperform traditional methods.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.