The multiperiod two‐dimensional non‐guillotine cutting stock problem with usable leftovers

A mixed integer linear programing model for the two‐dimensional non‐guillotine cutting problem with usable leftovers was recently introduced by Andrade et al. The problem consists in cutting a set of ordered items using a set of objects of minimum cost and, within the set of solutions of minimum cost, maximizing the value of the usable leftovers. Since the concept of usable leftovers assumes they can potentially be used to attend new arriving orders, the problem is extended to the multiperiod framework in this work. In this way, the decision at each instant does not minimize in a myopic way the cost of the objects required to attend the orders of the current instant; but it aims to minimize the overall cost of the objects up to the considered time horizon. Some variants of the proposed model are analyzed and numerical results are presented.     

Hybrid approach for the two‐dimensional bin packing problem with two‐staged patterns

This paper presents a two‐phase heuristic approach for the two‐dimensional bin packing problem with two‐staged patterns and nonoriented items. A solution is generated in each phase and the better one is selected. Residual problems are solved by column generation in the first phase, where a partial admitting procedure is used to admit some of the patterns into the phase‐1 solution. The second solution is obtained from solving an integer linear programming problem over the set of all patterns generated in the first phase, where a time limit is used and subsequently the solution may not be optimal over the pattern set. The computational results indicate that the approach yields the best solution quality among the heuristics that use two‐staged or more complex patterns.     

Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization

In the two‐dimensional (2D) cutting (2DC) problem, a large rectangular sheet has to be dissected into smaller rectangular pieces with the aim of maximizing the total profit associated with the extracted pieces. When the number of copies of each piece to be extracted is bounded, it is referred to as constrained 2DC (C2DC) problem. The C2DC has been widely studied by the operations research community for its applications and theoretical issues. In this work, we recall the best exact and heuristic solving approaches for the C2DC and we provide a review and a categorization of the available upper bounds. We also discuss improvements and combinations of these upper bounds and give directions for their effective exploitation. Finally, we demonstrate the loss of accuracy of several exact methods present in literature because of the effect of the used antiredundancy strategies on the implemented bounding criteria. This work, based on more than 90 contributions, has a twofold target. For researchers working in C2DC, it provides a useful insight on the topic. For expert practitioners, it represents a systematic collection of the main findings and achievements, posing also the basis for future research.     

Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem

In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.     

Formulations for an inventory routing problem

In this paper, we present and compare formulations for the inventory routing problem (IRP) where the demand of customers has to be served, over a discrete time horizon, by capacitated vehicles starting and ending their routes at a depot. The objective of the IRP is the minimization of the sum of inventory and transportation costs. The formulations include known and new mathematical programming formulations. Valid inequalities are also presented. The formulations are tested on a large set of benchmark instances. One of the most significant conclusions is that the formulations that use vehicle‐indexed variables are superior to the more compact, aggregate formulations.     

Algorithms for the circular two‐dimensional open dimension problem

In this paper, we propose three heuristics for the circular two‐dimensional open dimension problem, also known as the circular strip cutting/packing problem. We first propose an open strip generation solution procedure that uses the best local position rule into the open strip. Second, we propose a simple augmented version of the first heuristic by introducing an exchange‐order strategy. Third, we propose a hybrid heuristic that combines beam search and a series of target values belonging to a predetermined interval search. We evaluate the performance of these heuristics on several instances varying from small to large ones. Encouraging results have been obtained.     

An evolutionary algorithm for the one‐dimensional cutting stock problem

This paper deals with the one‐dimensional integer cutting stock problem, which consists of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to minimize the waste of material. The case in which there are various types of objects available in stock in limited quantities is studied. A new heuristic method based on the evolutionary algorithm concept is proposed to solve the problem. This heuristic is empirically analyzed by solving randomly generated instances and the results are compared with other methods from the literature.     

A branch‐and‐cut algorithm for the Team Orienteering Problem

The Team Orienteering Problem aims at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods based on different mathematical formulations were proposed. In this paper, we present a new two‐index formulation with a polynomial number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch‐and‐cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.     

An iterative time‐bucket refinement algorithm for a high‐resolution resource‐constrained project scheduling problem

We consider a resource‐constrained project scheduling problem originating in particle therapy for cancer treatment, in which the scheduling has to be done in high resolution. Traditional mixed integer linear programming techniques such as time‐indexed formulations or discrete‐event formulations are known to have severe limitations in such cases, that is, growing too fast or having weak linear programming relaxations. We suggest a relaxation based on partitioning time into so‐called time‐buckets. This relaxation is iteratively solved and serves as basis for deriving feasible solutions using heuristics. Based on these primal and dual solutions and bounds, the time‐buckets are successively refined. Combining these parts, we obtain an algorithm that provides good approximate solutions soon and eventually converges to an optimal solution. Diverse strategies for performing the time‐bucket refinement are investigated. The approach shows excellent performance in comparison to the traditional formulations and a metaheuristic.     

A cache‐efficient implementation of the lattice Boltzmann method for the two‐dimensional diffusion equation

The lattice Boltzmann method is an important technique for the numerical solution of partial differential equations because it has nearly ideal scalability on parallel computers for many applications. However, to achieve the scalability and speed potential of the lattice Boltzmann technique, the issues of data reusability in cache‐based computer architectures must be addressed. Utilizing the two‐dimensional diffusion equation, , this paper examines cache optimization for the lattice Boltzmann method in both serial and parallel implementations. In this study, speedups due to cache optimization were found to be 1.9–2.5 for the serial implementation and 3.6–3.8 for the parallel case in which the domain decomposition was optimized for stride‐one access. In the parallel non‐cached implementation, the method of domain decomposition (horizontal or vertical) used for parallelization did not significantly affect the compute time. In contrast, the cache‐based implementation of the lattice Boltzmann method was significantly faster when the domain decomposition was optimized for stride‐one access. Additionally, the cache‐optimized lattice Boltzmann method in which the domain decomposition was optimized for stride‐one access displayed superlinear scalability on all problem sizes as the number of processors was increased. Copyright © 2004 John Wiley & Sons, Ltd.     

A biased‐randomized algorithm for the two‐dimensional vehicle routing problem with and without item rotations

This paper proposes an efficient algorithm, with a reduced number of parameters, for solving the two‐dimensional loading‐capacitated vehicle routing problem (2L‐CVRP). This problem combines two of the most important issues in logistics, that is, vehicle routing and packing problems. Our approach contemplates unrestricted loading including the possibility of applying 90° rotations to each rectangular‐shaped item while loading it into the vehicle, which is a realistic assumption seldom considered in the existing literature. The algorithm uses a multistart approach that is designed to avoid local minima and also to make the algorithm an easily parallelizable one. At each restart, a biased randomization of a savings‐based routing algorithm is combined with an enhanced version of a classical packing heuristic to produce feasible good solutions for the 2L‐CVRP. The proposed algorithm has been compared with the classical benchmarks for two different 2L‐CVRP variants, that is, with and without item rotations. Experimental results show that our approach outperforms several best‐known solutions from previous work, both in terms of quality and the computational time needed to obtain them.     

GPU implementation of a parallel two‐list algorithm for the subset‐sum problem

The subset‐sum problem is a well‐known non‐deterministic polynomial‐time complete (NP‐complete) decision problem. This paper proposes a novel and efficient implementation of a parallel two‐list algorithm for solving the problem on a graphics processing unit (GPU) using Compute Unified Device Architecture (CUDA). The algorithm is composed of a generation stage, a pruning stage, and a search stage. It is not easy to effectively implement the three stages of the algorithm on a GPU. Ways to achieve better performance, reasonable task distribution between CPU and GPU, effective GPU memory management, and CPU–GPU communication cost minimization are discussed. The generation stage of the algorithm adopts a typical recursive divide‐and‐conquer strategy. Because recursion cannot be well supported by current GPUs with compute capability less than 3.5, a new vector‐based iterative implementation mechanism is designed to replace the explicit recursion. Furthermore, to optimize the performance of the GPU implementation, this paper improves the three stages of the algorithm. The experimental results show that the GPU implementation has much better performance than the CPU implementation and can achieve high speedup on different GPU cards. The experimental results also illustrate that the improved algorithm can bring significant performance benefits for the GPU implementation. Copyright © 2014 John Wiley & Sons, Ltd.     

On the use of mixed‐integer linear programming for predictive control with avoidance constraints

This technical note concerns the predictive control of discrete‐time linear models subject to state, input and avoidance polyhedral constraints. Owing to the presence of avoidance constraints, the optimization associated with the predictive control law is non‐convex, even though the constraints themselves are convex. The inclusion of the avoidance constraints in the predictive control law is achieved by the use of a modified version of a mixed‐integer programming approach previously derived in the literature. The proposed modification consists of adding constraints to ensure that linear segments of the system trajectories between consecutive sampling times do not cross existing obstacles. This avoids the significant extra computation that would be incurred if the sampling time was reduced to prevent these crossings. Simulation results show that the inclusion of these additional constraints successfully prevents obstacle collisions that would otherwise occur. Copyright © 2008 John Wiley & Sons, Ltd.     

Asynchronous control for two‐dimensional hidden Markovian jump systems with partly known mode observation conditional probabilities

This study focuses on the asynchronous control problem for two‐dimensional discrete‐time hidden Markovian jump systems where the mode observation conditional probability matrix is partly known. Considering the original system modes are invisible, the observed modes emitted from an observer serve as an alternative for stability analysis and controller design where a mode observation conditional probability matrix is constructed to characterize the emission between system modes and observed modes. Specially, only partly known information of the mode observation conditional probability matrix is accessible. With the introduction of the free‐connection weighting matrices, the asymptotic mean square stability criterion is firstly derived based on Lyapunov method. This introduction provides a further degree of relaxation and less conservatism is therefore achieved. Secondly, we present synthesis conditions for asynchronous state feedback controller design given in terms of a set of interconnected linear matrix inequalities. Moreover, cluster concept based on the partitions of observed modes is adopted which helps to decrease the number of controllers and simplify the design complexity. A numerical example, regarding the cases with and without clustering of the observed modes, is presented to illustrate the effectiveness of the proposed method.     

New lower bounds based on column generation and constraint programming for the pattern minimization problem

The pattern minimization problem is a cutting and packing problem that consists in finding a cutting plan with the minimum number of different patterns. This objective may be relevant when changing from one pattern to another involves a cost for setting up the cutting machine. When the minimization of the number of different patterns is done by assuming that no more than the minimum number of rolls can be used, the problem is also referred to as the cutting stock problem with setup costs.     

State estimation for two‐dimensional complex networks with randomly occurring nonlinearities and randomly varying sensor delays

This paper is concerned with the state estimation problem for two‐dimensional (2D) complex networks with randomly occurring nonlinearities and randomly varying sensor delays. To describe the fact that measurement delays may occur in a probabilistic way, the randomly varying sensor delays are introduced in the delayed sensor measurements. The randomly occurring nonlinearity, on the other hand, is included to account for the phenomenon of nonlinear disturbances appearing in a random fashion that is governed by a Bernoulli distributed white sequence with known conditional probability. The stochastic Brownian motions are also considered, which enter into not only the coupling terms of the complex networks but also the measurements of the output systems. Through available actual network measurements, a state estimator is designed to estimate the true states of the considered 2D complex networks. By utilizing an energy‐like function, the Kronecker product and some stochastic analysis techniques, several sufficient criteria are established in terms of matrix inequalities under which the 2D estimation error dynamics is globally asymptotically stable in the mean square. Furthermore, the explicit expression of the estimator gains is also characterized. Finally, a numerical example is provided to demonstrate the effectiveness of the design method proposed in this paper. Copyright © 2012 John Wiley & Sons, Ltd.     

ℋ︁∞ and l2–l∞ filtering for two‐dimensional linear parameter‐varying systems

In this paper, the ??_∞ and l₂–l_∞ filtering problem is investigated for two‐dimensional (2‐D) discrete‐time linear parameter‐varying (LPV) systems. Based on the well‐known Fornasini–Marchesini local state‐space (FMLSS) model, the mathematical model of 2‐D systems under consideration is established by incorporating the parameter‐varying phenomenon. The purpose of the problem addressed is to design full‐order ??_∞ and l₂–l_∞ filters such that the filtering error dynamics is asymptotic stable and the prescribed noise attenuation levels in ??_∞ and l₂–l_∞ senses can be achieved, respectively. Sufficient conditions are derived for existence of such filters in terms of parameterized linear matrix inequalities (PLMIs), and the corresponding filter synthesis problem is then transformed into a convex optimization problem that can be efficiently solved by using standard software packages. A simulation example is exploited to demonstrate the usefulness and effectiveness of the proposed design method. Copyright © 2007 John Wiley & Sons, Ltd.     

Parallel matheuristics for the discrete unit commitment problem with min‐stop ramping constraints

The discrete unit commitment problem with min‐stop ramping constraints optimizes the daily production of thermal power plants, subject to an operational reactivity of thermal units in a 30‐minute delay. Previously, mixed integer programming (MIP) formulations aimed at an exact optimization approach. This paper derives matheuristics to face the short time limit imposed by the operational constraints. Continuous relaxations guide the search for feasible solutions exploiting tailored variable fixing strategies. Parallel matheuristics are derived considering complementary strategies in parallel. Tests were performed on more than 600 real‐life instances. Our parallel matheuristic provides high‐quality solutions and outperforms the MIP approach in the time limits imposed by the industrial application. This paper illustrates a special interest for matheuristics in industrial highly constrained problems: many tailored neighborhood searches can be derived from an MIP formulation, and their combination in a parallel scheme improves the solution quality as well as the consistency of the heuristic.     

Two dimensional gel electrophoresis of apolipoprotein C‐III and MALDI‐TOF MS are complementary techniques for the study of combined defects in N‐ and mucin type O‐glycan biosynthesis

In the field of diseases related to glycosylation disorders, congenital defects associated with abnormalities in both O‐ and N‐glycosylation of proteins constitute arising novel entities. Defects in subunits of the conserved oligomeric Golgi protein complex have been shown to be involved in an important part of previously unsolved CDG type II combining abnormalities in both mucin type core1 O‐ and N‐glycans; furthermore, recent studies revealed that autosomal recessive cutis laxa type II could also be associated with such combined glycosylation defects. Based on the studies of serum samples from three patients including a case of cutis laxa, we present here evidence that 2‐DE of apolipoprotein C‐III in combination with MALDI‐TOF‐MS analysis of serum O‐ and N‐glycans allow the detection and the biochemical characterization of these newly recognized glycosylation disorders.