Search results for "Exact algorithm"
showing 6 items of 16 documents
The Multiple Multidimensional Knapsack with Family-Split Penalties
2021
Abstract The Multiple Multidimensional Knapsack Problem with Family-Split Penalties (MMdKFSP) is introduced as a new variant of both the more classical Multi-Knapsack and Multidimensional Knapsack Problems. It reckons with items categorized into families and where if an individual item is selected to maximize the profit, all the items of the same family must be selected as well. Items belonging to the same family can be assigned to different knapsacks; however, in this case, split penalties are incurred. This problem arises in resource management of distributed computing contexts and Service Oriented Architecture environments. An exact algorithm based on the exploitation of a specific combi…
An exact algorithm for the min-cost network containment problem
2004
A network design problem which arises in the distribution of a public utility provided by several competitive suppliers is studied. The problem addressed is that of determining minimum-cost (generalized) arc capacities in order to accommodate any demand between given source–sink pairs of nodes, where demands are assumed to fall within predetermined ranges. Feasible flows are initially considered as simply bounded by the usual arc capacity constraints. Then, more general linear constraints are introduced which may limit the weighted sum of the flows on some subsets of arcs. An exact cutting plane algorithm is presented for solving both of the above cases and some computational results are re…
A new branch-and-price algorithm for the traveling tournament problem
2010
Abstract The traveling tournament problem ( ttp ) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. For solving the problem exactly, we propose a new branch-and-price approach. The starting point is a new compact formulation for the ttp . The corresponding extensive formulation resulting from a Dantzig-Wolfe decomposition is identical to one given by Easton, K., Nemhauser, G., Trick, M., 2003. Solving the traveling tournament problem: a combined interger programming and constraint programming approach. In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of Automated Timetabling IV, Volume 2740 of Lecture Notes i…
A Fast and Very Accurate Approach to the Computation of Microlensing Magnification Patterns Based on Inverse Polygon Mapping
2006
A new method of calculating microlensing magnification patterns is proposed that is based on the properties of the backward gravitational lens mapping of a lattice of polygonal cells defined at the image plane. To a first-order approximation, the local linearity of the transformation allows us to compute the contribution of each image-plane cell to the magnification by apportioning the area of the inverse image of the cell (transformed cell) among the source-plane pixels covered by it. Numerical studies in the κ = 0.1-0.8 range of mass surface densities demonstrate that this method (provided with an exact algorithm for distributing the area of the transformed cells among the source-plane pi…
An exact algorithm for preventive maintenance planning of series-parallel systems
2009
Reliability is a meaningful parameter in assessing the performance of systems such as chemical processing facilities, power plant, aircrafts, ships, etc. In the literature, reliability optimization is widely considered during the system design phase and it is carried out by an opportune selection of both system components and redundancy. On the other hand, the problem of maintaining a required level of reliability by an opportune maintenance policy has been poorly examined. The paper tackles this problem for a system whose major components can be maintained only during a planned system downtime. An exact algorithm is proposed in order to single out the set of components that must be maintai…
Selection of Series System Components to Maximize Reliability
2010
The paper tackles the problem of maximizing the reliability of a series system by an opportune choice of components. Each type of component must be selected among the available alternatives for that component whereas a fixed amount of budget can not be overcome. The problem can be formulated by a binary non linear programming model and it is equivalent to a knapsack problem with multiple-choice constraints, well known to be NP-hard. An exact algorithm is proposed for solving large dimension problems to the optimum in a short time. The algorithm efficiency is finally compared with the recent heuristics proposed in literature to approach the same problem.