Nr. doc. | Classificazioni |
34 | 4 Contributo in Atti di Convegno (Proceeding) |
27 | 1 Contributo su Rivista |
11 | 2 Contributo in Volume |
3 | 5 Altro |
Anno | Risorsa |
---|---|
2018 |
The Electric Vehicle Relocation Problem in Carsharing Systems with Collaborative Operators
Proceedings of 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2018) Autore/i: Bruglieri, Maurizio; Marinelli, Fabrizio; Pisacane, Ornella Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: We address the problem of balancing the demand and the availability of vehicles between stations in urban one-way electric carsharing systems through operator relocations. Unlike the previous papers, we assume that the operators can collaborate among them through the carpooling, i.e., giving a lift to the others when moving an EV from a pick-up request station to one of delivery. For this new problem, we propose a Mixed Integer Linear Programming formulation and a column generation based heuristic solution approach. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/258944 |
2018 |
Optimizing vehicle relocations in one-way electric carsharing systems
Book of Abstracts of 29th European Conference on Operational Research (EURO2018) Autore/i: Bruglieri, M; Marinelli, F.; Pisacane, O. Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/259387 |
2018 |
A Sequential Value Correction heuristic for a bi-objective two-dimensional bin-packing
ELECTRONIC NOTES IN DISCRETE MATHEMATICS Autore/i: Marinelli, Fabrizio; Pizzuti, Andrea Classificazione: 1 Contributo su Rivista Abstract: In 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. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/255399 |
2018 |
A Heuristic for a Rich and Real Two-dimensional Woodboard Cutting Problem
Proceedings of the 7th International Conference on Operations Research and Enterprise Systems - Volume 1: ICORES Autore/i: Rosetti, Roberto; Pizzuti, Andrea; Marinelli, Fabrizio; Arbib, Claudio Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: Cutting 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. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/255404 |
2018 |
Exploiting star inequalities for the maximum quasi-clique problem
Book of Abstracts of the 23rd International Symposium on Mathematical Programming (ISMP 2018) Autore/i: Marinelli, Fabrizio; Pizzuti, Andrea; Rossi, Fabrizio Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: Mining of dense subgraphs is of substantial interest in graphbased applications where the interactions between elements encode meaningful properties of the solutions. Cohesive structures are well described by several clique relaxations. The maximum γ quasi-clique problem ask to find an induced γ quasi-clique of maximum order, i.e., the largest subgraph whose edge density is at least γ. We present a new MILP formulation obtained by the integer decomposition of star inequalities, and a surrogate relaxation whose number of constraints is linear in the number of vertices of the graph. The former provides a dual bound potentially better than that obtained by the MILP formulations available in the literature; the latter can be exploited to handle dense graphs of large size. The practicability and usefulness of the proposed mathematical programs have been assessed through extensive computational experiments. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/265507 |
2018 |
A star-based reformulation for the maximum quasi-clique problem
Proceedings of 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2018) Autore/i: Marinelli, Fabrizio; Pizzuti, Andrea; Rossi, Fabrizio Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: Given a simple and undirected graph, the maximum γ-quasi-clique problem consists in identifying the induced subgraph of maximum order and edge density of at least γ. In this paper we propose a new extended formulation for such a problem obtained by decomposing star inequalities. Preliminary computational results assess the quality of the continuous relaxation with respect to the tightest formulation available in the literature. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/265505 |
2018 |
A pattern-based reformulation for the one-dimensional bin packing with variabile pattern processing time
Proceedings of the Scheduling Symposium 2018 Autore/i: Pizzuti, Andrea; Wei, W.; Marinelli, Fabrizio; Yagiura, M.; Hu, Y. Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: In 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. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/265756 |
2017 |
Maximum lateness minimization in one-dimensional bin packing
OMEGA Autore/i: Arbib, Claudio; Marinelli, Fabrizio Classificazione: 1 Contributo su Rivista Abstract: In the One-dimensional Bin Packing problem (1-BP) items of different lengths must be assigned to a minimum number of bins of unit length. Regarding each item as a job that requires unit time and some resource amount, and each bin as the total (discrete) resource available per time unit, the 1-BP objective is the minimization of the makespan C-max = max(j)(C-j). We here generalize the problem to the case in which each item j is due by some date d(j): our objective is to minimize a convex combination of C-max and L-max = max(j){C-j-d(j)}. For this problem we propose a time-indexed Mixed Integer Linear Programming formulation. The formulation can be decomposed and solved by column generation relegating single-bin packing to a pricing problem to be solved dynamically. We use bounds to (individual terms of) the objective function to address the oddity of activation constraints. In this way, we get very good gaps for instances that are considered difficult for the 1-BP. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/245819 |
2017 |
Shelf space re-allocation for out of stock reduction
COMPUTERS & INDUSTRIAL ENGINEERING Autore/i: Frontoni, E.; Marinelli, F.; Rosetti, R; Zingaretti, P. Classificazione: 1 Contributo su Rivista Abstract: An ILP formulation is proposed for Shelf space re-allocation problem.Out-of-stock data are collected from the Shelf Detector System in real time.Space elastic demand function is linked with real-time statistical data.Tests performed on real, random and large instances. A planogram is a detailed visual map that establishes product positions over a shelf in a retail store. It is designed to support an innovative merchandising approach, to increase sales and profits, to supply the best location of a product for suppliers and to better manage the shelves. Product selection and the shelf space reserved to each product is a central activity for retailers and Shelf Out of Stock (SOOS) events are often strongly related to planogram design. In this paper we present a solution to optimally re-allocate shelf space to minimize Out of Stock (OOS) events. The approach uses SOOS data coming in real time from a sensor network technology, named Shelf Detector System, and an Integer Linear Programming model that integrates a space elastic demand function. Experimental results, based on a real scenario in the diaper category in Belgium, have proved that the system can efficiently calculate a proper solution able to re-allocate space and reduce OOS events. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/246103 |
2017 |
Bin Packing Problems with Variable Pattern Processing Times: A Proof-of-concept
Springer Proceedings in Mathematics and Statistics Autore/i: Marinelli, Fabrizio; Pizzuti, Andrea Editore: Springer New York LLC Classificazione: 2 Contributo in Volume Abstract: In 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. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/255407 |
2017 |
Optimization Models for Cut Sequencing
Springer Proceedings in Mathematics and Statistics Autore/i: Arbib, Claudio; Avella, Pasquale; Boccia, Maurizio; Marinelli, Fabrizio; Mattia, Sara Editore: Springer New York LLC Classificazione: 2 Contributo in Volume Abstract: The paper describes models for scheduling the patterns that form a solution of a cutting stock problem. We highlight the problem of providing the required final products with the necessary items obtained from the cut, choosing which pattern feeds which lot of parts. This problem can be solved prior to schedule cuts, or in an integrated way. We present integer programming models for both approaches. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/255409 |
2016 |
Software architecture quality of service analysis based on optimization models
Intelligent Systems Reference Library Autore/i: Potena, Pasqualina; Crnkovic, Ivica; Marinelli, Fabrizio; Cortellessa, Vittorio Editore: Springer Science and Business Media Deutschland GmbH Classificazione: 2 Contributo in Volume Abstract: The ability to predict Quality of Service (QoS) of a software architecture supports a large set of decisions across multiple lifecycle phases that span from design through implementation-integration to adaptation phase. However, due to the different amount and type of information available, different prediction approaches can be introduced in each phase. A major issue in this direction is that QoS attribute cannot be analyzed separately, because they (sometime adversely) affect each other. Therefore, approaches aimed at the tradeoff analysis of different attributes have been recently introduced (e.g., reliability versus cost, security versus performance). In this chapter we focus on modeling and analysis of QoS tradeoffs of a software architecture based on optimization models. A particular emphasis will be given to two aspects of this problem: (i) the mathematical foundations of QoS tradeoffs and their dependencies on the static and dynamic aspects of a software architecture, and (ii) the automation of architectural decisions driven by optimization models for QoS tradeoffs. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/245816 |
2016 |
Optimal production planning by reusing components
24th Mediterranean Conference on Control and Automation, MED 2016 Autore/i: Frontoni, Emanuele; Marinelli, Fabrizio; Paolanti, Marina; Rosetti, Roberto; Zingaretti, Primo Editore: Institute of Electrical and Electronics Engineers Inc. Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/240003 |
2016 |
Optimization of obsolete part reusing: a case-study
Emerging Advances in Logistics Systems Autore/i: Rosetti, R.; Frontoni, E.; Marinelli, F.; Zingaretti, P. Editore: EUT EDIZIONI UNIVERSITÀ DI TRIESTE Luogo di pubblicazione: Trieste Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/245821 |
2016 |
One-dimensional cutting stock with a limited number of open stacks: bounds and solutions from a new integer linear programming model
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH Autore/i: Claudio Arbib; Fabrizio Marinelli; Paolo Ventura Classificazione: 1 Contributo su Rivista Abstract: We address a one-dimensional cutting stock problem where, in addition to trim-loss minimization, cutting patterns must be sequenced so that no more than s different part types are in production at any time. We propose a new integer linear programming formulation whose constraints grow quadratically with the number of distinct part types and whose linear relaxation can be solved by a standard column generation procedure. The formulation allowed us to solve problems with 20 part types for which an optimal solution was unknown. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/223315 |
2016 |
A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem
COMPUTERS & OPERATIONS RESEARCH Autore/i: Marinelli, Fabrizio; Parente, Angelo Classificazione: 1 Contributo su Rivista Abstract: A signed graph, i.e., an undirected graph whose edges have labels in {-1,+1}, is balanced if it has no negative cycles. Given a signed graph, we are interested in a balanced induced subgraph of maximum order (the MBIS problem). In the present work, we propose a greedy approach for the MBIS problem that is based on the progressive shortening of negative cycles, and that generalizes the well-known minimum-degree greedy heuristic for the maximum independent set problem. An extensive computational study on three classes of instances shows that the new algorithm outperforms the reference heuristics proposed in the literature. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/245818 |
2015 |
Maximum lateness minimization in one-dimensional Bin Packing problems
Optimization for Energy, Environment and Sustainability: BOOK OF ABSTRACTS Autore/i: Arbib, Claudio; Marinelli, Fabrizio Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: In the One-dimensional Bin Packing problem (1-BP) items of different lengths must be assigned to a minimum number of bins of unit length. Regarding each item as a job that requires unit time and some resource amount, and each bin as the total (discrete) resource available per time unit, the minimization of the number of bins corresponds to the minimization of the makespan. We here generalize the problem to the case in which each item is due by some date: our objective is to minimize a convex combination of makespan and maximum lateness. We propose a time indexed ILP formulation to solve the problem. The formulation can be decomposed and solved by column generation, in which case single-bin packing is relegated to a pricing problem: therefore, extensions to s-dimensional problems can be dealt with independently. We show how to couple the formulation with quite simple bounds to (individual terms of) the objective function, so as to get very good gaps with instances that are considered difficult for the 1-BP. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/229498 |
2015 |
An improvement on "Integrated production strategy and reuse scenario: A CoFAQ model and case study of mail server system development"
OMEGA Autore/i: Wu, Zhiqiao; Tang, Jiafu; Kwong, C.K.; Marinelli, F. Classificazione: 1 Contributo su Rivista Abstract: The authors (Tang et al. (2013) [1] developed a CoFAQ model to formulate a solution for the problem of production strategy decision and reuse scenario selection for a software product family. In the previous research, we stated that the CoFAQ model was a 0-1 mixed integer nonlinear program, where only a local optimal solution might be found. In a recent study, we found that the CoFAQ could be transformed into a 0-1 mixed integer linear programming model. By solving the model, a global optimal solution can be obtained. In this paper, we present the improved formulation and the optimal solution for the case study. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/229494 |
2015 |
Bin Packing with due dates
12th ESICUP Meeting booklet Autore/i: Arbib, Claudio; Marinelli, Fabrizio Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: In the Bin Packing problem (BP), items of different sizes must be assigned to a minimum number of bins. In the k-dimensional problem (kBP), items and bins are closed k-intervals. Regarding each item as a job that requires unit time and some resource amount, and each bin as the total (discrete) resource available per time unit, the kBP objective is the minimization of the makespan. We generalize the kBP problem to Bin Packing and Scheduling (kBPS) by changing the objective to any (even non-regular) function of the completion time of the jobs. Interesting applications are those in which each part (= job) is to be produced within a specific due date. Typical examples of regular functions are maximum lateness, weighted sum of jobs tardiness, etc. In practice, a convex combination of such functions is often considered. When the scheduling term in the objective function is the weighted sum of jobs tardiness or of tardy jobs, one can specialize an exact formulation for the Cutting Stock Problem with Due Dates (Arbib and Marinelli, 2014). An alternative, more general and perhaps more effective approach is to use an ad-hoc time-indexed formulation. This approach, which can encompass Dantzig-Wolfe decomposition and, consequently, column generation, is close to that described by van den Akker et al. (2005) for general time-indexed formulations applied to parallel scheduling. When column generation is used, the difficulty of k-dimensional packing is relegated to the pricing problem. To find a lower bound for the 2BPS one can then solve a relaxed 2-dimensional pricing problem by the arc-flow formulation (Macedo, Alves and V. de Carvalho, 2010). In alternative, one can implement conservative scales (Belov et al., 2013) via a time-indexed formulation for 1BPS. In this talk we just discuss a preliminary computational experience carried out for 1BPS with Lmax as scheduling term of the objective function. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/229507 |
2014 |
Mathematical programming: Turing completeness and applications to software analysis
JOURNAL OF COMBINATORIAL OPTIMIZATION Autore/i: Leo Liberti; Fabrizio Marinelli Classificazione: 1 Contributo su Rivista Abstract: Mathematical programming is Turing complete, and can be used as a general-purpose declarative language. We present a new constructive proof of this fact, and showcase its usefulness by discussing an application to finding the hardest input of any given program running on a Minsky Register Machine. We also discuss an application of mathematical programming to software verification obtained by relaxing one of the properties of Turing complete languages. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/154732 |
2014 |
On cutting stock with due dates
OMEGA Autore/i: C. Arbib; F. Marinelli Classificazione: 1 Contributo su Rivista Abstract: Classical stock cutting calls for fulfilling a given demand of parts, minimizing raw material needs. With the production of each part type regarded as a job due within a specific date, a problem arises of scheduling cutting operations. We here propose an exact integer linear programming formulation, and develop primal heuristics, upper bounds and an implicit enumeration scheme. A computational experience carried out for the one-dimensional problem shows that our primal heuristics outperform known ones, and that the formulation has good features for finding exact solutions of non-trivial instances. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/154302 |
2013 |
Quantifying the Influence of Failure Repair/Mitigation Costs on Service-Based Systems
2013 IEEE 24th International Symposium on Software Reliability Engineering (ISSRE) Autore/i: V. Cortellessa; F. Marinelli; R. Mirandola; P. Potena Editore: IEEE Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: The analysis of non-functional properties of Service-Based Systems (SBSs) is a complex task, mostly because it requires models that encompass the composition of service properties into architectural properties. For example, the reliability of a SBS is given by the composition of service and interconnection reliabilities. Although several approaches have been introduced in the last few years to address these issues, the tradeoff analysis among non-functional properties of software services has not yet been studied enough. The goal of this paper is to introduce a set of optimization models that allow quantifying the costs of service failure repair/mitigation actions aimed at keeping the whole SBS reliability over a certain threshold. On the basis of our previous work in this area, we first introduce an optimization model aimed at selecting either in-house built or provided services with the goal of minimizing the SBS cost while guaranteeing a certain level of reliability. Thereafter we strengthen the reliability constraints, and we build two different optimization models that aim to solve the same problem under new constraints, where one model starts from the solution obtained in the original model and tries to improve it, while the other one looks for an optimal solution in the whole search space. Finally, we introduce a fourth model, based on stochastic optimization, with the goal of rather searching for solutions that explicitly take into account the stochastic nature of the problem and search for new repair/mitigation actions cheaper than the ones identified by the other models. Each optimization model has been experimented on about 300 variations of a nominal model. The experimental results show the efficacy of our optimization models to quantify the costs of different failure repairing/mitigation actions in different contexts. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/154730 |
2013 |
Mathematical Programming: Turing-completeness and Applications to Algorithmic Analysis
Minneapolis 2013 - INFORMS annual meeting Autore/i: Leo Liberti; Fabrizio Marinelli Editore: INFORMS:901 Elkridge Landing Road, Suite 400:Linthicum, MD 21090:(800)446-3676, (410)850-0300, EMAIL: informs@informs.org, INTERNET: http://www.informs.org, http://pubsonline.informs.org, Fax: (410)684-2963 Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: We provide a new proof of the fact that Mathematical Programming is Turing-complete, and show how it can be useful in algorithmic analysis. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/154735 |
2012 |
Mixed integer programs for cutting and scheduling optimization
Proceedings of the 9th ESICUP meeting Autore/i: Arbib C.; Marinelli F. Editore: ESICUP Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79566 |
2012 |
An LP-based tabu search for batch scheduling in a cutting process with finite buffers
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS Autore/i: C. Arbib; F. Marinelli; F. Pezzella Classificazione: 1 Contributo su Rivista Abstract: This paper addresses a cutting stock problem under typical resource constraints that arise when working centres with nesting capabilities are associated with automatic feeders/stackers. The critical resource is the number of buffers available to host the batches built up by the centre. To cope with it, pattern and batch sequencing problems must be addressed simultaneously. A tabu-search algorithm exploring batch output sequences is proposed. The algorithm never opens more stacks than buffers, respects batch compatibility/precedence constraints, and keeps the maximum order spread under control. To demonstrate its effectiveness and efficiency, a computational study was set up, solving 920 test problems derived from the literature. The study enabled a proper tuning of the method and offered encouraging results: in 228 cases an optimum was found; in nearly all, the gap from the optimum was below 1%. Computation times range from fractions of seconds to a couple of minutes in the worst cases. Compared to existing methods, the algorithm provides on average the same solution quality, with the advantage of solving a problem which is more general and hence closer to application. The paper includes a discussion on the method extensions required to deal with asynchronous stacking and heterogeneous batches. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/55585 |
2011 |
On one-dimensional cutting stock with due dates
Operational Research in Transportation and Logistics Autore/i: Arbib C.; Marinelli F. Editore: AIRO (Italian Operational Research Society) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69844 |
2011 |
A cycle-contraction heuristic for detecting an embedded reflected network matrix of maximum size
Operational Research in Transportation and Logistics Autore/i: Parente A.; Marinelli F. Editore: AIRO (Italian Operational Research Society) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69845 |
2011 |
On LP Relaxations for the Pattern Minimization Problem
NETWORKS Autore/i: Aloisio A.; C. Arbib; F. Marinelli Classificazione: 1 Contributo su Rivista Abstract: We discuss two formulations of the pattern minimization problem: (1) introduced by Vanderbeck, and (2) obtained adding setup variables to the cutting stock formulation by Gilmore-Gomory. Let z_i^{LP}(u) be the bound given by the linear relaxation of (i) under a given vector u of parameters. We show that z_2^{LP}(u) >= z_1^{LP}(u) and provide a class of instances for which the inequality holds strict. We observe that the linear relaxation of both formulations can be solved by the same column generation procedure and discuss the critical role of parameter u. The article is completed by a numerical test comparing the lower bounds obtained through (1) and (2) for different values of u. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/55579 |
2011 |
Cutting Stock with No Three Parts per Pattern: Work-in-process and Pattern Minimization
DISCRETE OPTIMIZATION Autore/i: Aloisio A.; C. Arbib; F. Marinelli Classificazione: 1 Contributo su Rivista Abstract: The Pattern Minimization Problem (PMP) consists in finding, among the optimal solutions of a cutting stock problem, one that minimizes the number of distinct cutting patterns activated. The Work-in-process Minimization Problem (WMP) calls for scheduling the patterns so as to maintain as few open stacks as possible. This paper addresses a particular class of problems, where no more than two parts can be cut from any stock item, hence the feasible cutting patterns form the arc set of an undirected graph G. The paper extends the case G=K^n introduced in 1999 by McDiarmid. We show that some properties holding for G=K^n are no longer valid for the general case; however, for special cases of practical relevance, properly including G=K^n, quasi-exact solutions for the PMP and the WMP can be found: the latter in polynomial time, the former via a set-packing formulation providing very good lower bounds. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/55580 |
2011 |
A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints
COMPUTERS & OPERATIONS RESEARCH Autore/i: Marinelli F.; S. Nocella; F. Rossi; S. Smriglio Classificazione: 1 Contributo su Rivista Abstract: The data exchange between ground stations and satellite constellations is becoming a challenging task, as more and more communication requests must be daily scheduled on a few, expensive stations located all around the Earth. Most of the scheduling procedures adopted in practice cannot cope with such complexity, and the development of optimization-based tools is strongly spurred. We show that the problem can be formulated as a multiprocessor task scheduling problem in which each job (communication) requires a time dependent pair of resources (ground station and satellite) to be processed, and the objective consists of maximizing the total revenue of on-time jobs. A time-indexed 0,1-linear programming formulation is then introduced able to include all the complex technological constraints of current constellations. Unfortunately, relevant real-world scenarios yield integer programs with hundreds of thousands variables and a few million constraints, which cannot be tackled by standard integer programming (either exact or heuristic) techniques. To overcome this difficulty, we developed a Lagrangian version of the Fix-and-Relax MIP heuristic. It is based on a Lagrangian relaxation of the problem which is shown to be equivalent to a sequence of maximum weighted independent set problems on interval graphs. The heuristic has been implemented in a tool used by the Italian reference operator for the GALILEO constellation, providing near optimal solutions to relevant large scale test problems. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/55581 |
2010 |
A computational study on the duty generation for the multi-depot bus driver scheduling problem
Proceeding of the XVIII EURO Working Group on Locational Analisys Autore/i: Marinelli F.; Pezzella F.; Rosetti R. Editore: Fridericiana Editrice Universitaria Luogo di pubblicazione: NAPOLI Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/54637 |
2010 |
Cutting stock with part-type scheduling
Proceedings of the ALIO-INFORMS Joint International Meeting Autore/i: Arbib C.; Marinelli F. Editore: ALIO-INFORMS Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69846 |
2010 |
Batch scheduling in a cutting process with finite buffers
Autore/i: Arbib C.; Marinelli F.; Pezzella F. Luogo di pubblicazione: L'Aquila Classificazione: 5 Altro Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79564 |
2010 |
Cutting stock with bounded open stacks: a new integer linear programming model
Autore/i: Arbib C.; Marinelli F.; Ventura P. Luogo di pubblicazione: L’Aquila Classificazione: 5 Altro Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79563 |
2010 |
Mathematical programming based debugging
ELECTRONIC NOTES IN DISCRETE MATHEMATICS Autore/i: Liberti L.; Le Roux S.; Leconte J.; Marinelli F. Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/49588 |
2010 |
Static analysis by abstract interpretation: a mathematical programming approach
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE Autore/i: Goubault E.; Le Roux S.; Leconte J.; Liberti L.; Marinelli F. Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/46531 |
2009 |
A branch-and-price algorithm for multicommodity facility location
Decision and optimization model for evaluation and optimization Autore/i: Arbib C.; Marinelli F.; Rosetti R.; Servilio M. Editore: AIRO (Italian Operational Research Society) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69847 |
2009 |
A lower bound for the cutting stock problem with a limited number of open stacks
Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization Autore/i: Arbib C.; Marinelli F.; Scoppola C.M. Editore: Ecole Polytechnique Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/47857 |
2009 |
Cutting stock with bounded open stacks
Proceedings of the 5th International Winter Conference of AIRO Autore/i: Arbib C.; Marinelli F.; Scoppola C.M. Editore: AIRO (Italian Operational Research Society) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69848 |
2009 |
A general framework for combined module- and scale-based product platform design
Engineering Systems: Achievements and Challenges Autore/i: Marinelli F.; De Weck O.; Krob D.; Liberti L.; Mucherino A.; Editore: M.I.T. ESD Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/49587 |
2009 |
Exact and Asymptotically Exact Solutions for a Class of Assortment Problems
INFORMS JOURNAL ON COMPUTING Autore/i: ARBIB C; F. MARINELLI Editore: INFORMS:901 Elkridge Landing Road, Suite 400:Linthicum, MD 21090:(800)446-3676, (410)850-0300, EMAIL: informs@informs.org, INTERNET: http://www.informs.org, http://pubsonline.informs.org, Fax: (410)684-2963 Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39853 |
2009 |
Double Variable Neighbourhood Search with Smoothing for the Molecular Distance Geometry Problem
JOURNAL OF GLOBAL OPTIMIZATION Autore/i: LIBERTI L; C. LAVOR; N. MACULAN; F. MARINELLI Classificazione: 1 Contributo su Rivista Abstract: We discuss the geometrical interpretation of a well-known smoothing operator applied to the Molecular Distance Geometry Problem (MDGP), and we then describe a heuristic approach based on Variable Neighbourhood Search on the smoothed and original problem. This algorithm often manages to find solutions having higher accuracy than other methods. This is important as small differences in the objective function value may point to completely different 3D molecular structures. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39385 |
2009 |
Controlling open stacks and flow time in a cutting process
6th ESICUP Meeting Autore/i: ARBIB C; MARINELLI F; F. PEZZELLA Editore: Universitat de València Luogo di pubblicazione: València Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/44145 |
2008 |
A column generation approach for the multiple depot crew scheduling problem: a case study
Optimization and Logistics in Transportation and Communication Networks Autore/i: Marinelli F.; Pezzella F.; Rosetti R. Editore: Fridericiana Editrice Universitaria Luogo di pubblicazione: Napoli Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/55637 |
2008 |
Trim loss minimization under a given number of open stacks
Optimisation and Logistics in Transportation and Communication Networks Autore/i: Arbib C.; Marinelli F.; Pezzella F. Editore: Fridericiana Editrice Universitaria Luogo di pubblicazione: Napoli Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/55636 |
2008 |
A note on LP relaxations for the 1D cutting stock problem with setup costs
Proceedings of the 7th Cologne-Twente Workshop on Graph and Combinatorial Optimization Autore/i: Aloisio A.; Arbib C.; Marinelli F. Editore: Università degli Studi di Milano Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/47856 |
2008 |
Cutting stock with no three parts per patterns: work-in-process and pattern minimization
Optimization and Logistics in Transportation and Communication Networks Autore/i: Arbib C.; Aloisio A.; Marinelli F. Editore: Fridericiana Editrice Universitaria Luogo di pubblicazione: Napoli Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69849 |
2008 |
Riduzione degli Sfridi da Operazioni di Taglio: Modelli di Ottimizzazione e Applicazioni Industriali
Scienze delle Decisioni in Italia: applicazioni della ricerca operativa a problemi aziendali Autore/i: ARBIB C; F. MARINELLI Editore: ECIG Luogo di pubblicazione: GENOVA Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/42300 |
2008 |
Uno schedulatore multimissione per la costellazione GALILEO
MATEMATICA E IMPRESA Autore/i: Lagrasta S.; Nocella S.; Salonico A.; Rossi F.; Marinelli F.; Smriglio S. Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69838 |
2008 |
Modelli matematici per ridurre gli sfridi da operazioni di taglio e razionalizzare i formati nell’industria del vetro
MATEMATICA E IMPRESA Autore/i: Michetti M.; Arbib C.; Marinelli F.; Alfieri F. Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/69837 |
2008 |
Experimenting the Automated Selection of COTS Components Based on Cost and System Requirements
JOURNAL OF UNIVERSAL COMPUTER SCIENCE Autore/i: CORTELLESSA V; I CRNKOVIC; F. MARINELLI; P POTENA Editore: Graz: Know-Center. Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39642 |
2008 |
An Optimization Framework for “Build-or-Buy” Decisions in Software Architecture
COMPUTERS & OPERATIONS RESEARCH Autore/i: CORTELLESSA V; F. MARINELLI; P. POTENA Classificazione: 1 Contributo su Rivista Abstract: Building a software architecture that meets functional requirements is a quite consolidated activity, whereas keeping high quality attributes is still an open challenge. In this paper we introduce an optimization framework that supports the decision whether to buy software components or to build them in-house upon designing a software architecture. We devise a non-linear cost/quality optimization model based on decision variables indicating the set of architectural components to buy and to build in order to minimize the software cost while keeping satisfactory values of quality attributes. From this point of view, our tool can be ideally embedded into a Cost Beneﬁt Analysis Method to provide decision support to software architects. The novelty of our approach consists in building costs and quality attributes on a common set of decision variables related to software development.We start from a special case of the framework where the quality constraints are related to the delivery time and the product reliability, and the model solution also devises the amount of unit testing to be performed on built components. We generalize the framework formulation to represent a broader class of architectural cost-minimization problems under quality constraints, and discuss advantages and limitations of such approach. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39635 |
2007 |
A tight reformulation of the power-and-frequency assignment problem in wireless networks
Autore/i: Mannino C.; Marinelli F.; Rossi F.; Smriglio S. Luogo di pubblicazione: L'Aquila Classificazione: 5 Altro Abstract: One major task in wireless network planning is to assign emission powers and frequencies to transmitters so as to maximize the customers coverage (Power and Frequency Assignment Problem, PFAP). We present an optimization model which can be applied whenever the coverage is evaluated through a ¯nite set of testpoints, and the coverage condition of one testpoint can be cast into a linear function of the wanted and interfering signals. This happens, for instance, in mobile telephony and audio/video broadcasting. Natural compact integer programming formulations for PFAP often show large integrality gap and cannot be used to solve instances of practical interest. We present a non-compact Set Packing formulation for PFAP obtained by applying the Dantzig-Wolfe decomposition to the natural formulation. The pricing problem consists in optimizing the emission powers in a single frequency network, for which effective algorithms are available. Experiments show that the non-compact formulation is very tight and the resulting branch-and-price algorithm solves to optimality practically relevant instances of the Italian broadcasting system. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79565 |
2007 |
Driving the selection of COTS on the basis of system requirements
ASE '07 Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering Autore/i: Cortellessa V.; Crnkovic I.; Marinelli F.; Potena P. Editore: ACM Luogo di pubblicazione: New York Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/49583 |
2007 |
A mathematical programming model for computing fixed points in static program analysis
Complex Industrial Systems: Modelling, Verification and Optimization Autore/i: Marinelli F. Editore: LIX - Laboratoire d'Informatique de L'Ecole Polytechnique Luogo di pubblicazione: Palaiseau Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79567 |
2007 |
An Optimization Model for Trim Loss Minimization in an Automotive Glass Plant
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH Autore/i: ARBIB C; F. MARINELLI Editore: Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39636 |
2007 |
Capacitated Lot Sizing and Scheduling with Parallel Machines and Shared Buffers: a Case Study in a Packaging Company
ANNALS OF OPERATIONS RESEARCH Autore/i: F. MARINELLI; M.E. NENNI; A. SFORZA Editore: Dordrecht: Kluwer Academic Publishers. Amsterdam; Bussum: Baltzer Science Publishers. Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39637 |
2006 |
On hierarchical waste-and-pattern minimization with two part types per stock item
Proceedings of the 3rd ESICUP meeting Autore/i: Aloisio A.; Arbib C.; Marinelli F. Editore: ESICUP Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79571 |
2006 |
A branch-and-price algorithm for a class of assortment problems
OR for Better Management of Sustainable Development Autore/i: Arbib C.; Marinelli F. Editore: EURO (the Association of European Operational Research Societies) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: In the Cutting Stock Problem, one calls for an efficient way to cut a given demand of small parts from a given collection of large parts. Many cutting processes, however, must also face the problem of determining a restricted subset of large sizes to be stocked. In this work we deal with the special case where just one part type can be cut from each large size. We describe a PLI formulation obtained by convexifying a straightforward big-M formulation. A pricing problem is indicated and Ryan-Foster's branching rule adapted with a view to implement a branch-and-price exact algorithm. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79570 |
2006 |
A branch-and-price framework to solve a class of assortment problems
Proceedings of the 3rd ESICUP meeting Autore/i: Arbib C.; Marinelli F. Editore: ESICUP Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79572 |
2006 |
Automated selection of software components based on cost/reliability tradeoff
Software Architecture - Third European Workshop, EWSA 2006, Nantes, France, September 4-5, 2006 Autore/i: Cortellessa V.; Marinelli F.; Potena P. Editore: Springer-Verlag Luogo di pubblicazione: Berlin, Heidelberg Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/49581 |
2005 |
Power and frequency assignment in broadcasting networks by branch-and-price
Proceedings of the XXXVI Annual Conference Italian Operational Research Society Autore/i: Rossi F.; Mannino C.; Marinelli F.; Smriglio S. Editore: AIRO (Italian Operational Research Society) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79889 |
2005 |
A Lagrangean-based heuristic for a multimission automatic scheduler
Proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA) Autore/i: Marinelli F.; Nocella S.; Rossi F.; Smriglio S. Editore: MISTA Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/49585 |
2005 |
An optimization model for the short-term hydrothermal unit commitment problem
Proceedings of XXXVI Annual Conference Italian Operational Research Society Autore/i: Arbib C.; Lizzi M.; Marinelli F. Editore: AIRO (Italian Operational Research Society) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79890 |
2005 |
Integrating Process Optimization and Inventory Planning in Cutting-Stock with Skiving Option: an Optimization Model and its Application
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH Autore/i: ARBIB; C; F. MARINELLI Editore: Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598 Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39638 |
2004 |
A p-median model for waste minimization in the glass industry
Proceedings of the 1st ESICUP Meeting Autore/i: Arbib C.; Marinelli F. Editore: ESICUP Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79891 |
2003 |
Analisi delle criticità e razionalizzazione delle decisioni nella lavorazione del vetro: il caso Pilkington
Proceedings of the XXXIV Annual Conference of the Italian Operational Research Society Autore/i: Alfieri F.; Marinelli F.; Michetti M. Editore: AIRO (Italian Operational Research Society) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79892 |
2003 |
Mean completion time minimization as a graph ordering problem
New opportunities for operations research Autore/i: Arbib C.; Flammini M.; Marinelli F. Editore: EURO (the Association of European Operational Research Societies) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79893 |
2003 |
Integrating cutting and inventory planning: an optimization model
New opportunities for operations research Autore/i: Arbib C.; Marinelli F. Editore: EURO (the Association of European Operational Research Societies) Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Scheda della pubblicazione: https://iris.univpm.it/handle/11566/79894 |
2003 |
Scheduling commands on a satellite constellation
Proceedings of the 1st Multidisciplinary International Scheduling Conference: Theory & Applications Autore/i: Marinelli F.; Nocella S.; Rossi F.; Smriglio S. Editore: MISTA Classificazione: 4 Contributo in Atti di Convegno (Proceeding) Abstract: In this paper we describe a space application concerning the scheduling of command transmissions on a satellite constellation. The problem is modeled as a variant of the Parallel Multiprocessor Task Scheduling Problem. A computational experiment on a real data set compares an ILP formulation to a combinatorial branch-and-bound scheme. Scheda della pubblicazione: https://iris.univpm.it/handle/11566/49586 |
2003 |
The Lazy Cook Problem, or Scheduling Two Parallel Machines to Optimize Vehicle Utilization
INTERNATIONAL JOURNAL OF FLEXIBLE MANUFACTURING SYSTEMS Autore/i: ARBIB; C; F. MARINELLI Editore: Kluwer Academic Publishers / Massachusetts:PO Box 358, Accord Station:Hingham, MA 02018:(617)871-6600 Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39639 |
2003 |
Minimum flow time graph ordering
Graph-Theoretic Concepts in Computer Science - 29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003 Autore/i: Arbib C.; Flammini M.; Marinelli F. Editore: Springer-Verlag Luogo di pubblicazione: Berlin, Heidelberg, New York Classificazione: 2 Contributo in Volume Scheda della pubblicazione: https://iris.univpm.it/handle/11566/49582 |
2003 |
Applicazione di modelli di cutting e packing a sistemi manifatturieri
BOLLETTINO DELL'UNIONE MATEMATICA ITALIANA. A Autore/i: Marinelli F. Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/80806 |
2002 |
Scheduling and Control of Material Handling in a Flexible Manufacturing Cell
RICERCA OPERATIVA Autore/i: ARBIB C; F. MARINELLI Editore: Franco Angeli Riviste SRL:viale Monza 106, I 20127 Milan Italy:011 39 02 2895762, 011 39 02 289562, EMAIL: riviste@francoangeli.it, INTERNET: http://www.francoangeli.it, Fax: 011 39 02 2891515 Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39641 |
2002 |
Cutting and Reusing: an Application from Automobile Component Manufacturing
OPERATIONS RESEARCH Autore/i: ARBIB C; F. DI IORIO; F. MARINELLI; F. ROSSI Editore: INFORMS:901 Elkridge Landing Road, Suite 400:Linthicum, MD 21090:(800)446-3676, (410)850-0300, EMAIL: informs@informs.org, INTERNET: http://www.informs.org, http://pubsonline.informs.org, Fax: (410)684-2963 Classificazione: 1 Contributo su Rivista Scheda della pubblicazione: https://iris.univpm.it/handle/11566/39640 |
P.zza Roma 22, 60121 Ancona
Tel (+39) 071.220.1, Fax (+39) 071.220.2324
P.I. 00382520427