1,721,036 research outputs found
An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
Full text linkWe consider the bilevel knapsack problem with interdiction constraints, an extension of the classic 0–1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower’s total profit. We derive effective lower bounds for the bilevel knapsack problem and present an exact method that exploits the structure of the induced follower’s problem. The approach strongly outperforms the current state-of-the-art algorithms designed for the problem. We extend the same algorithmic framework to the interval min–max regret knapsack problem after providing a novel bilevel programming reformulation. Also for this problem, the proposed approach outperforms the exact algorithms available in the literature
On fairness and diversification in WTA and ATP tennis tournaments generation
Full text linkSingle-elimination (knockout) tournaments are the standard paradigm for both main tennis professional associations, WTA and ATP. Schedules are generated by allocating first seeded and then unseeded players with seeds prevented from encountering each other early in the competition. Besides, the distribution of pairings in the first round between unseeded players and seeds for a yearly season may be strongly unbalanced. This provides often a great disadvantage to some “unlucky” unseeded players in terms of money prizes. Also, a fair distribution of matches during a season would benefit from limiting in first rounds the presence of Head-to-Head (H2H) matches between players that met in the recent past. We propose a tournament generation approach in order to reduce in the first round unlucky pairings and also replays of H2H matches. The approach consists in a clustering optimization problem inducing a consequent draw within each cluster. A Non-Linear Mathematical Programming (NLMP) model is proposed for the clustering problem so as to reach a fair schedule. The solution reached by a commercial NLMP solver on the model is compared to the one reached by a faster hybrid algorithm based on multi-start local search. The approach is successfully tested on historical records from the recent Grand Slams tournaments
On approximating the Incremental Knapsack Problem
No full textWe consider the 0-1 Incremental Knapsack Problem (IKP) where the capacity grows over time periods and if an item is placed in the knapsack in a certain period, it cannot be removed afterwards. The contribution of a packed item in each time period depends on its profit as well as on a time factor which reflects the importance of the period in the objective function. The problem calls for maximizing the weighted sum of the profits over the whole time horizon. In this work, we provide approximation results for IKP and its restricted variants. In some results, we rely on Linear Programming (LP) to derive approximation bounds and show how the proposed LP-based analysis can be seen as a valid alternative to more formal proof systems. We first manage to prove the tightness of some approximation ratios of a general purpose algorithm currently available in the literature and originally applied to a time-invariant version of the problem. We also devise a Polynomial Time Approximation Scheme (PTAS) when the input value indicating the number of periods is considered as a constant. Then, we add the mild and natural assumption that each item can be packed in the first time period. For this variant, we discuss different approximation algorithms suited for any number of time periods and for the special case with two periods
Heuristic solution methods for the selective disassembly sequencing problem under sequence-dependent costs
No full textThe first Waste Framework Directive issued by the European Union dates back to the seventies but was drastically amended in the last decade to reduce environmental impacts of waste by encouraging reuse, recycling and remanufacturing. Product recovery starts with disassembly which results in high labor costs. Disassembly supports environmentally conscious choices like replacement of defective parts to extend the life span of products, removal of suitable components for reuse and extraction of hazardous substances to decontaminate materials for reprocessing. Besides, selective disassembly also accommodates maintenance and repairs. Optimizing the cost of disassembly is crucial to make this process an economically viable option. Due to change tools and parts reorientation, disassembly costs are sequence-dependent. Therefore minimizing the disassembly cost involves the search for an adequate sequence of disassembly tasks. Consequently, this paper addresses the disassembly sequencing problem for selective and sequential disassembly under sequence-dependent costs. As optimal formulations fail to handle real-world cases, we develop a randomized greedy algorithm (needing a very few number of parameters to be set and proving to be robust with respect to their value) and a matheuristic to solve efficiently medium to large-sized instances
Lower Bounds and a New Exact Approach for the Bilevel Knapsack with Interdiction Constraints
No full textWe consider the Bilevel Knapsack with Interdiction Constraints, an extension of the classic 0-1 knapsack problem formulated as a Stackelberg game with two agents, a leader and a follower, that choose items from a common set and hold their own private knapsacks. First, the leader selects some items to be interdicted for the follower while satisfying a capacity constraint. Then the follower packs a set of the remaining items according to his knapsack constraint in order to maximize the profits. The goal of the leader is to minimize the follower's profits. The presence of two decision levels makes this problem very difficult to solve in practice: the current state-of-the-art algorithms can solve to optimality instances with 50-55 items at most. We derive effective lower bounds and present a new exact approach that exploits the structure of the induced follower's problem. The approach successfully solves all benchmark instances within one second in the worst case and larger instances with up to 500 items within 60 s
No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths
No full textMerging combinatorial design and optimization: the Oberwolfach Problem
No full textThe Oberwolfach Problem OP (F)-posed by Gerhard Ringel in 1967-is a paradigmatic Combinatorial Design problem asking whether the complete graph K-v decomposes into edge-disjoint copies of a 2-regular graph F of order v. In this paper we provide all the necessary equipment to generate solutions to OP (F) for relatively small orders by using so-called difference methods. From the theoretical standpoint, we present new insights on the combinatorial structures involved in the solution of the problem. Computationally, we provide a full recipe whose base ingredients are advanced optimization models and tailored algorithms. This algorithmic arsenal can solve the OP (F) for all possible orders up to 60 with the modest computing resources of a personal computer. The 20 new orders, from 41 to 60, encompass 241 200 instances of the Oberwolfach Problem, which is 22 times greater than those solved in previous contributions
A Postsynthetic Exchange/Deprotection Approach to Append Aliphatic Amines in Defective UiO-66
No full textAliphatic amine-functionalized metal–organic frameworks (MOFs) are receiving increasing attention for their potential as adsorbents for CO2. In this work, a two-step postsynthetic approach is presented, applied to defective ZrIV-based MOF UiO-66, which involves the exchange of N-tert-butyloxycarbonyl (Boc) protected ω-amino acids for defect-compensating formate groups, followed by thermal deprotection of the Boc groups to yield free amine groups. The chosen amino acids are glycine, 3-aminopropionic acid (β-alanine), γ-aminobutyric acid, and 5-aminovaleric acid. Postsynthetic exchange of the Boc-protected amino acids is carried out in N,N-dimethylformamide, observing no structural damage and a dependence of the loading of functional groups on the length of the aliphatic chain (the longer the chain, the lower the loading). Deprotection is achieved by heating the solids to 160 °C under a N2 stream, accompanied by the release of CO2 and isobutylene, as confirmed by thermogravimetric analysis coupled with infrared spectroscopy and mass spectrometry. The deprotected MOFs are characterized by their gas sorption properties, finding that functionalization of the defects led to a predictable decrease in porosity, without enhancing the affinity for CO2, suggesting that the amine groups might not be accessible
- …
