1,721,001 research outputs found
Location-Routing models and methods for Freight Distribution and Infomobility in City Logistics
No full text
Improved dynamic programming algorithms for unconstrained two-dimensional guillotine cutting
No full textIn the unconstrained two-dimensional cutting problem (U2DCP), we are given a large rectangular sheet to be cut in order to extract small rectangular pieces, with no limits on the number (demand) of desired pieces. We face the variant with guillotine constraint, requiring to cut any rectangle in two parts through vertical/horizontal cuts with end points on the rectangle boundaries. For a given U2DCP instance, the dynamic programming approach can be used either to optimally solve it, or to obtain a full matrix of upper bounds suitable for the constrained variant of the problem where limits exist on the piece demands. The elements of the full matrix are also usable as partial solutions to build lower bounds for the non-guillotine variant. In this paper, we propose two major improvements to a dynamic programming procedure previously shown to be capable of solving very large size instances. First, we introduce a new option for one of the three conditions used for the anti-redundancy strategies on cut coordinates. Second, following the effort of the Operations Research community to exploit the feature of modern CPUs containing multi-core processors, we provide a parallelization scheme. An extended computational campaign is presented. We compare the upgraded procedure with its previous version on a single thread and with the currently state-of-the-art algorithm for multi-thread platforms, outperforming both in terms of execution time on average by a factor of 1.7 and 12, respectively, or for some problem instances up to 4.5 and 50, respectively. Moreover, the new procedure can solve two very large instances previously unsolved, as well as the new huge instances proposed in this paper
Simple pattern minimality problems: Integer linear programming formulations and covering-based heuristic solving approaches
No full textThe simple pattern minimality problem (SPMP) represents a central problem in the logical analysis of data and association rules mining, and it finds applications in several fields as logic synthesis, reliability analysis, and automated reasoning. It consists of determining the minimum number of patterns explaining all the observations of a data set, that is, a Boolean logic formula that is true for all the elements of the data set and false for all the unseen observations. We refer to this problem as covering SPMP (C-SPMP), because each observation can be explained (covered) by more than one pattern. Starting from a real industrial application, we also define a new version of the problem, and we refer to it as partitioning SPMP (P-SPMP), because each observation has to be covered just once. Given a propositional formula or a truth table, C-SPMP and P-SPMP coincide exactly with the problem of determining the minimum disjunctive and minimum exclusive disjunctive normal form, respectively. Both problems are known to be NP-hard and have been generally tackled by heuristic methods. In this context, the contribution of this work is twofold. On one side, it provides two original integer linear programming formulations for the two variants of the SPMP. These formulations exploit the concept of Boolean hypercube to build a graph representation of the problems and allow to exactly solve instances with more than 1,000 observations by using an MIP solver. On the other side, two effective and fast heuristics are proposed to solve relevant size instances taken from literature (SeattleSNPs) and from the industrial database. The proposed methods do not suffer from the same dimensional drawbacks of the methods present in the literature and outperform either existing commercial and freeware logic tools or the available industrial solutions in the number of generated patterns and/or in the computational burden
Upper Bounds Categorization for Constrained Two-Dimensional Guillotine Cutting
No full textIn the two-dimensional cutting problem, a large rectangular sheet has to be dissected into smaller rectangular desired pieces. If limits exist on the number of extracted pieces, the problem is classified as constrained, with a wide range of applications. Most literature solving methods are based on ad hoc tree search strategies, with top-down or bottom-up approach. In both cases, lower and upper bounds are exploited, leading to branch and bound algorithms. We present a review of the upper bounds and identify a set of features for their categorization
A MILP Formulation for the Reorganization of the Blood Supply Chain in Italian Regions
No full textBlood is a vital resource for human being since its unavailability may cause deaths and complications for patients. For this reason, in the last 20 years great interest has been addressed worldwide to the blood supply chain management, in terms of efficient and effective policy making and system design.
In answer to this raising need, the Italian Healthcare Ministry issued a decree aimed at improving the blood supply chain at regional level in terms of costs, accessibility and shortage, providing also several indications and restrictions to be accounted for. In this context, this chapter presents a mixed-integer linear programming formulation to determine the optimal location and the number of blood facilities at regional scale, with the aim of minimizing system costs meanwhile guaranteeing good standard service level requirements.
The proposed formulation tackles the problem in a multi-echelon and multi-objective perspective. It has been solved by Gurobi 9.0.1 solver and validated on real like test cases related to Campania and Puglia regions. Finally, the impacts of the different parameters involved in the formulation are analyzed in order to provide managerial insights to decision makers and healthcare stakeholders
A three-stage p-median based exact method for the Optimal Diversity Management Problem
No full textThe optimal diversity management problem (ODMP) arises in many application fields when a company, producing a good and/or a service customizable with options, has to satisfy many different client demands with various subset of options, but only a limited number of option combinations can be produced. ODMP can be represented by a disconnected network and formulated as a large-scale p-median problem (PMP). In this paper we improve a known decomposition approach where smaller PMPs, related to the network components, can be solved instead of the initial large problem. The proposed method is structured in three stages and it combines Lagrangian relaxation-based techniques, variable fixing and reduction tests, and a dynamic programming algorithm. It drastically reduces the number and the dimensions of the p-median subproblems to be solved to optimality by a MIP solver and to be combined to determine the optimal solution of the original PMP by a multiple choice knapsack problem. A sequential and a parallel implementation of the method are provided and tested. Obtained results on known and new test instances show that our approach considerably outperforms state-of-the-art algorithms for large-scale ODMPs
Swap Minimization in Nearest Neighbour Quantum Circuits: An ILP Formulation
No full textQuantum computing (QC) represents a great challenge for both academia and private companies and it is currently pursuing the development of quantum algorithms and physical realizations of quantum computers. Quantum algorithms exploit the concept of quantum bit (qubit). They are implemented by designing circuits which consider an ideal quantum computer where no interaction restriction between qubits is imposed. However, physical realizations of quantum computers are subject to several technological constraints and adjacency between interacting qubits is one of the most common one. To this end, additional gates, referred to as swap, can be added to a quantum circuit to make it nearest neighbour compliant. These additional gates have a cost in terms of reliability of the quantum system, hence their number should be minimized. In this paper we first give some hints about this cutting edge topic. Then we provide a review of the literature solving approaches for the swap minimization problem in quantum circuits and propose an integer linear programming formulation for it. We conclude with some preliminary results on small test instances and future work perspectives
A column-and-row generation approach for the flying sidekick travelling salesman problem
No full textThe flying sidekick traveling salesman problem (FS-TSP) is a parcel delivery problem arising in the last-mile logistics, where the distribution plan of a driver-operated truck assisted by a drone (unmanned aerial vehicle, UAV) has to be defined. The FS-TSP is a variant of the TSP where routing decisions are integrated with customer-to-drone and customer-to-truck assignment decisions and truck-and-drone synchronization constraints. The objective is the minimization of the time required to serve all the customers, taking into account drone payload capacity and battery power constraints. In this work we provide a new representation of the FS-TSP based on the definition of an extended graph. This representation allows to model the problem by a new and compact integer linear programming formulation, where the synchronization issue is tackled in a column generation fashion, thus avoiding the usage of big-M constraints, representing one of the main drawbacks of the models present in literature. The proposed formulation has been solved by an exact approach which combines a Branch-and-Cut algorithm and a column generation procedure, strengthened by variable fixing strategies and new valid inequalities specifically defined for the problem. The proposed method has been experienced on a large set of benchmark instances. Computational results show that the proposed approach either is competitive or outperforms the best exact approach present in literature for the FS-TSP. Indeed, it is able to provide the optimal solution for all small size instances with 10 customers and for several medium size instances with 20 customers, some of them never solved before
- …
