1,720,981 research outputs found
Pricing-based primal and dual bounds for selected packing problems
No full textUn ampio insieme di problemi di ottimizzazione richiedono l’individuazione di soluzioni che definiscono un packing di elementi, al fine di massimizzare (minimizzare) la relativa funzione obiettivo. Risolvere all’ottimo alcuni di questi problemi può essere estremamente oneroso a causa della loro complessità innata e le corrispondenti formulazioni intere possono non essere appropriate
per approcciare istanze di dimensioni rilevanti. Pertanto, il calcolo di bound primali e duali qualitativamente validi necessita della definizione di tecniche ingegnose ed efficaci. Una metodologia valevole consiste nell’impiego di algoritmi basati su pricing, in cui le componenti delle soluzioni sono generate tramite la risoluzione di sottoproblemi di ottimizzazione specifici. Due
principali esponenti di questa famiglia sono la procedura delayed column generation (CG) e l’euristica sequential value correction (SVC): la prima fornisce un bound duale basato sulla generazione delle colonne implicite tramite la valutazione dei prezzi ombra di variabili nascoste; la seconda esplora lo spazio delle soluzioni primali seguendo la dinamica di prezzi approssimati.
In questa tesi ci concentriamo sull’applicazione di tecniche SVC e CG per l’individuazione di bound primali e duali per problemi di packing selezionati. In particolare, studiamo i problemi appartenenti alla famiglia del cutting e packing, dove i ben noti BIN PACKING e CUTTING STOCK sono arricchiti con caratteristiche derivanti dagli ambienti produttivi reali. Inoltre, studiamo il problema della MAXIMUM γ-QUASI-CLIQUE in cui si cerca la γ-quasi-clique indotta che massimizzi il numero di vertici selezionati. Risultati computazionali sono presentati al fine di validare le performance degli algoritmi implementati.Several optimization problems ask for finding solutions which define packing of elements while maximizing (minimizing) the objective function. Solving some of these problems can be extremely challenging due to their innate complexity and the corresponding integer formulations can be not suitable to be solved on instances of relevant size. Thus, clever techniques must be devised to achieve good primal and dual bounds. A valid way is to rely on pricing-based algorithms, in which solution components are generated by calling and
solving appropriate optimization subproblems. Two main exponents of this group are the delayed column generation (CG) procedure and the sequential value correction (SVC) heuristic: the former provides a dual bound based on the generation of implicit columns by examining the shadow prices of hidden variables; the latter explores the primal solution space by following the dynamic of approximate prices.
In this thesis we focus on the application of SVC and CG techniques to find primal and dual bounds for selected packing problems. In particular, we study problems belonging to the family of cutting and packing, where the classical BIN PACKING and CUTTING STOCK are enriched with features derived from the real manufacturing environment. Moreover, the MAXIMUM γ-QUASI-CLIQUE problem is taken into account, in which we seek for the induced γ-quasi-clique with the maximum number of vertices. Computational results are given to assess the performance of the implemented algorithms
Robust scheduling for minimizing maximum lateness on a serial-batch processing machine
Full text linkWe study a robust single-machine scheduling problem with uncertain processing times on a serial-batch processing machine to minimize maximum lateness. The problem can model many practical production and logistics applications which involve uncertain factors such as defect rates. A solution to a batch scheduling problem can be represented as a combination of a job-processing sequence and a partition of this sequence (batch sizing). To solve the problem, we prove that the job ordering rule for the earliest due date is optimal for any uncertainty set. For the batch sizing problem, we propose an exact algorithm based on dynamic programming with the same time complexity as solving the nominal problem
Number of bins and maximum lateness minimization in two-dimensional bin packing
No full textIn this work we address an orthogonal non-oriented two-dimensional bin packing problem where items are associated with due-dates. Two objectives are considered: minimize (i) the number of bins and (ii) the maximum lateness of the items. We discuss basic properties of non-dominated solutions and propose a sequential value correction heuristic that outperforms two benchmark algorithms specifically designed for this problem. We also extend the benchmark dataset for this problem with new and larger industrial instances obtained from a major manufacturer of cutting machines. Finally, we give some insights into the structure of Pareto-optimal sets in the classes of instances here considered
A Sequential Value Correction heuristic for a bi-objective two-dimensional bin-packing
No full textIn this work we address the orthogonal non-oriented two-dimensional bin packing problem where items are equipped with due-dates and the bi-objective function takes into account both the number of used bins and the maximum lateness of items. We propose a sequential value correction heuristic that outperforms the benchmark algorithm specifically designed for the same problem, and we finally give some insight on the structure of the Pareto-optimal sets of the considered classes of instances
Bin Packing Problems with Variable Pattern Processing Times: A Proof-of-concept
No full textIn several real-world applications the time required to accomplish a job generally depends on the number of tasks that compose it. Although the same also holds for packing (or cutting) problems when the processing time of a bin depends by the number of its items, the approaches proposed in the literature usually do not consider variable bin processing times and therefore become inaccurate when time costs are worth more than raw material costs. In this paper we discuss this issue by considering a variant of the one-dimensional bin packing problem in which items are due by given dates and a convex combination of number of used bins and maximum lateness has to be minimized. An integer linear program that takes into account variable pattern processing times is proposed and used as proof-of-concept
A pattern-based reformulation for the one-dimensional bin packing with variabile pattern processing time
No full textIn the one-dimensional packing problem with variable pattern processing time, we extend the classical packing definition by introducing a scheduling perspective: each item is provided with a due date, and a pattern-dependent time to process each bin is taken into account. In order to concurrently reduce the material waste and the delay costs, both not negligible in several real contexts, we require the minimization of a convex combination of the number of used bins and maximum lateness. In this paper we present a new extended pattern-based reformulation for this problem and a dynamic programming algorithm to solve the corresponding quadratic pricing problem. Preliminary computational results are given to analyze the quality of the continuous relaxation
One-dimensional bin packing with pattern-dependent processing time
No full textIn this paper the classical one-dimensional bin packing problem is integrated with scheduling elements: a due date is assigned to each item and the time required to process each bin depends on the pattern being used. The objective is to minimize a convex combination of the material waste and the delay costs, both significant in many real-world contexts. We present a novel pattern-based mixed integer linear formulation suitable for different classical scheduling objective functions, and focus on the specific case where the delay cost corresponds to the maximum tardiness. The formulation is tackled by a branch-and-price algorithm where the pricing of the column generation scheme is a quadratic problem solved by dynamic programming. A sequential value correction heuristic (SVC) is used to feed with warm starting solutions the column generation which, in turn, feeds the SVC with optimal prices so as to compute refined feasible solutions during the enumeration. Computational tests show that both column generation and branch-and-price substantially outperform standard methods in computing dual bounds and exact solutions. Additional tests are presented to analyze the sensitivity to parameters’ changes
A Model-Based Approach for the Long Term Planning of Distributed Energy Systems in the Energy Transition
No full textEnergy system models need to adapt to better represent the new challenges brought by a changing scenario regarding technologies development and policy making. The mixed integer linear programming based approach proposed in this study wishes to handle the impacts of these changes on potential investments in distributed energy systems, whose design is to be determined for a time horizon lasting several years with parameters that might change even substantially in such timespan. In order to test the approach, a scenario representing a residential district with high penetration of electricity production from non controllable sources (photovoltaic panels) is used as a test case. The investment decision under examination is when to possibly deploy a battery system to deal with the production surplus generated during the day by the mismatch in production and demand. While electricity can be fed into the grid by taking advantage of a feed-in tariff scheme, this could not be the most economically favorable approach due to the dropping costs of the Lithium-ion battery systems in the near future. Results show that for the case study under analysis investing into batteries appears not convenient in terms of overall costs, although the best alternative solution provided with storage systems is only slightly more expensive
A Matheuristic for the Design and Management of Multi-energy Systems
No full textNew technologies and emerging challenges are drastically changing how the energy needs of our society have to be met. By consequence, energy models have to adapt by taking into account such new aspects while aiding in decision making processes of the design of energy systems. In this work the problem of the design and operation of a multi-energy system is tackled by means of a mixed integer linear programming (MILP) formulation. Given the large size of the problem to be solved, a matheuristic approach based on constraint relaxations and variable fixing is proposed in order to not restrict the applicability to small cases. Two variable fixing policies are presented and performance analysis comparison on them has been done. Tests have been performed on small and realistic instances and results show the correctness of the approach and the quality of the heuristic proposed in term of solution quality and computational time
A Heuristic for a Rich and Real Two-dimensional Woodboard Cutting Problem
No full textCutting operations in manufacturing are characterized by practical requirements and utility criteria that usually increase the complexity of formulations or, even worse, are difficult to be modeled in terms of mathematical programming. However, disregarding or just simplifying those requirements often leads to solutions considered not attractive or even useless by the manufacturer. In this paper we consider a rich two-dimensional cutting stock problem that covers the whole specification of a family of wood cutting machines produced by a worldwide leader in industrial machinery manufacturing. A sequential value correction heuristic is implemented to minimize the employed stock area while reducing additional objective functions
- …
