221 research outputs found
Replication Data for "Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation"
No full textThis repository contains the tested instances and code for all algorithms discussed in the paper "Bounds and Heuristic Algorithms for the Bin Packing Problem with Minimum Color Fragmentation" by Mathijs Barkel, Maxence Delorme, Enrico Malaguti and Michele Monaci
Arcflow formulations and constraint generation frameworks for the two-bar charts packing problem
Full text linkWe consider the two-bar charts packing (2-BCPP), a recent combinatorial optimization problem whose aim is to pack a set of one-dimensional items into the minimum number of bins. As opposed to the well-known bin packing problem, pairs of items are grouped to form bar charts, and a solution is only feasible if the first and second items of every bar chart are packed in consecutive bins. After providing a complete picture of the connections between the 2-BCPP and other relevant packing problems, we show how we can use these connections to derive valid lower and upper bounds for the problem. We then introduce two new integer linear programming (ILP) models to solve the 2-BCPP based on a non-trivial extension of the arcflow formulation. Even though both models involve an exponential number of constraints, we show that they can be solved within a constraint generation framework. We then empirically evaluate the performance of our bounds and exact approaches against an ILP model from the literature and demonstrate the effectiveness of our techniques, both on benchmarks inspired by the literature and on new classes of instances that are specifically designed to be hard to solve. The outcomes of our experiments are important for the packing community because they indicate that arcflow formulations can be used to solve targeted packing problems with precedence constraints and also that some of these formulations can be solved with constraint generation
Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation
Full text linkIn this paper, we consider a recently introduced packing problem in which a given set of weighted items with colors has to be packed into a set of identical bins, while respecting capacity constraints and the number of available bins, and minimizing the total number of times that colors appear in the bins. We review exact methods from the literature and present a fast lower bounding procedure that, in some cases, can also provide an optimal solution. We theoretically study the worst-case performance of the lower bound and the effect of the number of available bins on the solution cost. Then, we computationally test our solution method on a large benchmark of instances from the literature: quite surprisingly, all of them are optimally solved by our procedure in a few seconds, including those for which the optimal solution value was still unknown. Thus, we introduce additional harder instances, which are used to evaluate the performance of a constructive heuristic method and of a tabu search algorithm. Results on the new instances show that the tabu search produces considerable improvements over the heuristic solution, with a limited computational effort
Are EU spatial ex ante coexistence regulations proportional?
Full text linkThe EU is currently struggling to implement coherent coexistence regulations on genetically modified (GM) and non-GM crops in all member states. While it stresses that any approach needs to be “proportionate to the aim of achieving coexistence”, very few studies have actually attempted to assess whether the proposed spatial ex ante coexistence regulations (SEACERs) satisfy this proportionality condition. In this article, we define proportionality as a functional relationship which is weakly increasing in the incentives for coexistence. We propose a spatial framework based on an existing landscape and introduce the new concept of shadow factor as a measure for the opportunity costs induced by SEACERs. This enables comparing the proportionality of (i) rigid SEACERs which are based on large isolation distances imposed on GM farmers versus (ii) flexible SEACERs based on pollen barrier agreements between neighboring farmers. Our theoretical and empirical findings argue for flexibility as rigid SEACERs violate the proportionality condition and, hence, are not consistent with the objectives of the EU.policy analysis, GIS, shadow factor, Agricultural and Food Policy, Crop Production/Industries,
Risk and De-Collectivisation: Evidence from the Czech Republic
Full text linkThe replacement of wage-labour farms by family farms in Central and Eastern Europe during the transformation has been more limited than was initially expected. In this paper a formal framework is developed in order to analyse the behaviour of family farms and socialist-style farms in the presence of risk, given the typical post-socialist environment. Management incentives, ownership structure, lump-sum transfers and consumption choices are shown to have the potential to limit the size of family farms relative to socialist-style farms. The hypotheses are tested with survey data collected by the author in the Czech Republic.transition, agriculture, structural change, risk, survey data, Risk and Uncertainty, D21, D81, O18, Q12,
To be awarded, or Not to Be Awarded. Is that the Question?:Theoretical and Methodological Aspects of the Study of Literary and Translation Prizes in the Context of Cultural Transfer
Full text linkTo be awarded the Nobel Prize in Literature or not to be awarded. Is that the question? Is not every author overwhelmed by the mere thought of being awarded the Noble Prize in Literature? After all, it means more translations, a broader audience, honour, money and fame. One good example of a writer who benefitted from the prize is the Icelandic author Halldór Laxness (1902-1998). A hitherto unknown poet and novelist, he became world famous after receiving the award in 1955, after which his works were translated into more than 25 languages.1 There have also been authors, however, who were anything but honoured to be nominated. Undoubtedly, the most famous example is Jean-Paul Sartre (1905-1980), who refused the Nobel Prize in 1964 to maintain his intellectual credibility as an anti-bourgeois philosopher and activist
Economics of spatial coexistence of genetically modified and conventional crops: Oilseed rape in Central France
Full text linkEurope is currently struggling to implement coherent coexistence regulations on genetically modified (GM) and non-GM crops in all EU Member States. We conduct simulations with the software ArcView® on a GIS dataset of a hypothetical case of GM herbicide tolerant oilseed rape cultivation in Central France. Our findings show that rigid coexistence rules, such as large distance requirements, may impose a severe burden on GM crop production in Europe. These rules are not proportional to the farmers’ basic incentives for coexistence and hence not consistent with the objectives of the European Commission. More alarming, we show that in densely planted areas a domino-effect may occur. This effect raises coexistence costs and even adds to the non-proportionality of rigid coexistence regulations. Instead, we show that flexible measures would be preferable since they are proportional to the incentives for coexistence and, hence, less counterproductive for European agriculture.regulation, GIS modelling, domino-effect, Crop Production/Industries,
Operational research approaches and mathematical models for kidney exchange: a literature survey and empirical evaluation
Full text linkKidney exchange is a transplant modality that has provided new opportunities for living kidney donation in many countries around the world since 1991. It has been extensively studied from an Operational Research (OR) perspective since 2004. This article provides a comprehensive literature survey on OR approaches to fundamental computational problems associated with kidney exchange over the last two decades. We also summarise the key integer linear programming (ILP) models for kidney exchange, showing how to model optimisation problems involving only cycles and chains separately. This allows new combined ILP models, not previously presented, to be obtained by amalgamating cycle and chain models. We present a comprehensive empirical evaluation involving all combined models from this paper in addition to bespoke software packages from the literature involving advanced techniques. This focuses primarily on computation times for 49 methods applied to 4,320 problem instances of varying sizes that reflect the characteristics of real kidney exchange datasets, corresponding to over 200,000 algorithm executions. We have made our implementations of all cycle and chain models described in this paper, together with all instances used for the experiments, and a web application to visualise our experimental results, publicly available
Intention-Aware Routing to Minimise Delays at Electric Vehicle Charging Stations
No full textEn-route charging stations allow electric vehicles to greatly extend their range. However, as a full charge takes a considerable amount of time, there may be significant waiting times at peak hours. To address this problem, we propose a novel navigation system, which communicates its intentions (i.e., routing policies) to other drivers. Using these intentions, our system accurately predicts congestion at charging stations and suggests the most efficient route to its user. We achieve this by extending existing time-dependent stochastic routing algorithms to include the battery's state of charge and charging stations. Furthermore, we describe a novel technique for combining historical information with agent intentions to predict the queues at charging stations. Through simulations we show that our system leads to a significant increase in utility compared to existing approaches that do not explicitly model waiting times or use intentions, in some cases reducing waiting times by over 80% and achieving near-optimal overall journey times.Software and Computer TechnologyElectrical Engineering, Mathematics and Computer Scienc
Wat moet eruit komen? Reactie op de kritische bijdrage van Kalmijn en De Graaf
No full textThe article focuses on the views of the author regarding the evaluation of his test book by Mathijs Kalmijn and Paul M. De Graaf meant for measuring professional status. Both Kalmijn and Graff have compared the scales proposed by the author and other scales for measuring professional status. They have claimed that GK-schaal is more effective than that of the author. According to the author, they have based their theoretical foundation of objective scales on training and profession
- …
