Search

In this paper we address the so-called two-dimensional Multiple Strip Packing Problem (MSPP). There is a set of rectangles and a set of strips, where each strip has a pre-defined width. The problem is to find a feasible packing of all the rectangles into the strips so as the maximal height of the packing over all the strips is minimized. A packing is feasible if all the rectangles are placed into the strips and not overlapped. In case of only one strip, the problem is widely known as the Strip Packing Problem (SPP). Many effective constructive heuristics for SPP are based on the so-called skyline representation of a packing pattern. We generalized this approach for the case of multiple strips and developed a randomized local search, which embeds the proposed skyline heuristic to compute the objective value for a packing. We also introduced the two-dimensional level multiple strip packing problem and developed some level-based constructive heuristics. We report computational results on real-life problem instances arisen in an application of MSPP in scheduling computing jobs on multiple Spark computer clusters.

The IO technique to measure impedance of the respiratory system is increasingly being used to assess lung function in patients where spirometry is not feasible. The lung resection effect on IO parameters is not clear. Aim: to evaluate the oscillatory mechanic changes in patients with PT after pneumonectomy (PE). Methods: 22 patients (12M/10F, aged between 21 and 55 years) with multi-drug resistant PT were examined baseline and on the 7-10th day after PE (baseline - IO, Spirometry, Bodyplethysmography, measurement of Diffusion capacity; after PE - IO). Data were expressed as means and standard deviations. Comparisons were estimated using t-test. Results: There was no significant difference in IO results baseline and after surgery (Z at 5 Hz 152±52 and 158±47 %pred. baseline and after PE; R5 0,44±0,16 and 0,47±0,16 kPa/L/s; R20 0,35±0,09 and 0,40±0,08 kPa/L/s; AX 1,24±1,5 and 1,06±1,38 kPa/L; |X5-X5pred.| 0,18±0,12 and 0,15±0,11 kPa/L/s; RF 17,3±7,6 and 18,4±9,1 Hz; p>0,05). In the analysis of functional data in the postoperative period bronchospasm was identified in 3 patients, that was not before the surgery. Conclusion: The total removal of the whole affected lung did not lead to significant changes in the baseline IO parameters. IO method could be applied for evaluating lung function complications in the postoperative period.

Recent advances in high-throughput technologies have given rise to collecting large amounts of multidimensional heterogeneous data that provide diverse information on the same biological samples. Integrative analysis of such multisource datasets may reveal new biological insights into complex biological mechanisms and therefore remains an important research field in systems biology. Most of the modern integrative clustering approaches rely on independent analysis of each dataset and consensus clustering, probabilistic or statistical modeling, while flexible distance-based integrative clustering techniques are sparsely covered. We propose two distance-based integrative clustering frameworks based on bi-level and bi-objective extensions of the p-median problem. A hybrid branch-and-cut method is developed to find global optimal solutions to the bi-level p-median model. As to the bi-objective problem, an $\varepsilon$ -constraint algorithm is proposed to generate an approximation to the Pareto optimal set. Every solution found by any of the frameworks corresponds to an integrative clustering. We present an application of our approaches to integrative analysis of NCI-60 human tumor cell lines characterized by gene expression and drug activity profiles. We demonstrate that the proposed mathematical optimization-based approaches outperform some state-of-the-art and traditional distance-based integrative and non-integrative clustering techniques.

We develop a modified hybrid sequential Lagrangean heuristic for the p-median problem and its shared memory parallel implementation using the OpenMP interface. The algorithm is based on finding the sequences of lower and upper bounds for the optimal value by use of a Lagrangean relaxation method with a subgradient column generation and a core selection approach in combination with a simulated annealing. The parallel algorithm is implemented using the shared memory (OpenMP) technology. The algorithm is then tested and compared with the most effective modern methods on a set of test instances taken from the literature.

International audience; Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated p-median problem and capacitated network location problem to optimality.

Numerical study is provided of the methods for solving the facility location problem when the clients choose some suppliers by their own preferences. Various formulations of this problem as an integer linear programming problem are considered. The authors implement a cutting plane method based on the earlier proposed family of valid inequalities which arises from connection with the problem for a pair of matrices. The results of numerical experiment are presented for testing this method. An optimal solution is obtained by the two versions of the branch and cut method with the suggested cutting plane method. The simulated annealing method is proposed for obtaining the upper bounds of the optimal solution used in exact methods. Numerical experiment approves the efficiency of the implemented approach in comparison with the previously available methods.

This paper presents a grid-enabled system for solving large-scale mixed integer programming (MIP) problems. The system has been developed using Globus and MPICH-G2, and consists of two solvers and an interface portal. After a brief introduction to Branch, Cut and Price optimization algorithms, the paper focuses on the system architecture, solvers and portal user interface. The performance of the system is measured and analysed on a small-scale grid environment consisting of three clusters on a campus LAN.

The paper is focused on one of the major air traffic management problem that consists in sequencing and scheduling airplanes landing and taking off on a runway. This difficult practical task is still carried out by flight controllers manually with little help from decision support systems. In this paper we propose an approach based on a time indexed integer programming formulation. The formulation is solved with a branch and cut method combined with some heuristic rules for dimension reduction. The effectiveness of the proposed approach is illustrated by computational experiments on real-life problem instances for the Milano Linate airport.

The capacitated p-median problem (CPMP) consists of finding p nodes (the median nodes) minimizing the total distance to the other nodes of the graph, with the constraint that the total demand of the nodes assigned to each median does not exceed its given capacity. In this paper we propose a cutting plane algorithm, based on Fenchel cuts, which allows us to considerably reduce the integrality gap of hard CPMP instances. The formulation strengthened with Fenchel cuts is solved by a commercial MIP solver. Computational results show that this approach is effective in solving hard instances or considerably reducing their integrality gap.

The multi-drug resistant pulmonary tuberculosis (PT) increased in recent years. Prognostic factors and functional status in estimating risk of lung resection for patients with PT is not definitely. Aim of study was to elucidate the prognostic factors for pneumonectomy in patients with PT. Methods: We analysed preoperative clinical and pulmonary function status and 30-day period after pneumonectomy in 56 patients with PT. All patients were performed Spirometry, Bodyplethysmography, measurement of Diffusion capacity for carbon monoxide (DLCO) on MasterScreen Body Diffusion (VIASYS Healthcare), Computed tomography on AQUILION PRIME (TOSHIBA) before surgery. We used descriptive statistics and Mann-Whitney U Test. Data are presented as mean±SD. Statistical significance was determined at a p-value Results: There was not registered 30-day postoperative mortality in all surveyed patients. The complications following surgery were in 13 patients. Those patients were older (45,2±12,4 years vs 36,5±10,8, p Conclusion: The possible poor prognostic factors were age after 45, COPD as comorbidity, mixed ventilation disorders, bronchospasm and significant decrease of diffusion capacity. The meaning of pulmonary function testing as criterion of functional operability for patients with PT demands the further analysis.

The two best studied facility location problems are the \(p\)-median problem and the uncapacitated facility location problem (Daskin, Network and discrete location: models, algorithms, and applications. Wiley, New York, 1995; Mirchandani and Francis, Discrete location theory. Wiley, New York, 1990). Both seek the location of the facilities minimizing the total cost, assuming no uncertainty in costs exists, and thus all parameters are known. In most real-world location problems the demand is not certain, because it is a long-term planning decision, and thus, together with the minimization of costs, optimizing some robustness measure is sound. In this paper we address bi-objective versions of such location problems, in which the total cost, as well as the robustness associated with the demand, are optimized. A dominating set is constructed for these bi-objective nonlinear integer problems via the \(\varepsilon \)-constraint method. Computational results on test instances are presented, showing the feasibility of our approach to approximate the Pareto-optimal set.

In this paper we report new computational results with an approach based on the generation of general cutting planes for several classes of Binary Integer Programming (BIP) Problems such as Generalized Assignment, Multi-Dimensional Knapsack, Capacitated P-median and Capacitated Network Location. These problems are characterized by a formulation including a great number of knapsack constraints, which, in general make these problems very hard to solve. The state of the art on these problems requires to use approaches based on Lagrangean Relaxation or decomposition approaches like Dantzig-Wolfe and Column Generation techniques. In this paper we present an approach based on the generation of general cutting planes of the polytope associated with each knapsack constraints. Computational experience on a wide set of benchamrk instances is carried out.

The multilevel generalized assignment problem (MGAP) consists of minimizing the assignment cost of a set of jobs to machines, each having associated therewith a capacity constraint. Each machine can perform a job with different efficiency levels that entail different costs and amount of resources required. The MGAP was introduced in the context of large manufacturing systems as a more general variant of the well-known generalized assignment problem, where a single efficiency level is associated with each machine. In this paper, we propose a branch-and-cut algorithm whose core is an exact separation procedure for the multiple-choice knapsack polytope induced by the capacity constraints and single-level execution constraints. A computational experience on a set of benchmark instances is reported, showing the effectiveness of the proposed approach.

The Vehicle Routing Problem with Time Windows (VRPTW) requires to design minimum cost routes for a fleet of vehicles with identical capacities to serve a set of customers within given time windows. Each customer must be visited exactly once and the load of a vehicle must not exceed its capacity. In this paper we introduce two new basic families of valid inequalities, called Lifted and Local Reachability Cuts, respectively, which extend the Reachability Cuts introduced by J. Lysgaard. Separation procedures for Lifted and Local Reachability Cuts have been implemented and embedded into a Branch-and-Cut framework to validate their computational effectiveness. They were tested on the Solomon and on the Gehring-Homberger benchmark instances (also known as the ''Extended Solomon'' instances) with 200 customers. Computational experiments show that the new cutting plane families can substantially improve the lower bounds returned by Lysgaard's Reachability Cuts. The Branch-and-Cut algorithm could also provide the optimal solution of three previously unsolved instances - C222, C225 and C226 - with large capacities and wide time windows and therefore difficult for exact algorithms.

A discrete location problem with nonlinear objective is addressed. A set of p plants is to be open to serve a given set of clients. Together with the locations, the number p of facilities is also a decision variable. The objective is to minimize the total cost, represented as the transportation cost between clients and plants, plus an increasing nonlinear function of p. Two Lagrangean relaxations are considered to derive lower bounds. Dual information is also used to design acore heuristic. Computational results are given, showing that nearly optimal solutions are obtained in short running times.

We study an exact separation procedure—SEP-MK—for the knapsack set with a single continuous variable XMK. Then, we address the question of whether SEP-MK can be of practical use in tightening mixed-integer programming (MIP) formulations when using standard (floating-point) MIP solvers. To this purpose, we present a separation procedure for MIP problems—SEP-MIPMK—where we derive knapsack sets of the form XMK by aggregating the continuous variables in the mixed knapsack inequalities of the formulation. Then, we use SEP-MK to generate cutting planes. Before the continuous variables are aggregated, the mixed knapsack inequalities are modified through the use of a bound substitution procedure to take into account fixed and variable bounds on the continuous variables. Bound substitution is made according to some heuristic rules, so even if its basic component SEP-MK is “exact,” the overall separation procedure for MIP problems, SEP-MIPMK, is heuristic. We perform a computational study on a wide set of mixed-integer programming instances from the MIPLIB 2003 [Achterberg, T., T. Koch, A. Martin. 2006. Mixed Integer Problem Library (MIPLIB) 2003. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Berlin. http://miplib.zib.de] and Mittelmann [Mittelmann, H. 2010. MILP testcases. http://plato.asu.edu/ftp/milp] benchmark sets. Computational experiments confirm that lifted cover and mixed-integer rounding (MIR) inequalities are effective from a computational viewpoint. Nevertheless, there are several instances where SEP-MIPMK is able to significantly raise the lower bounds given by lifted cover and MIR inequalities.