IRIS Pol. Torinohttps://iris.polito.itIl sistema di repository digitale IRIS acquisisce, archivia, indicizza, conserva e rende accessibili prodotti digitali della ricerca.Sun, 29 May 2022 01:38:16 GMT2022-05-29T01:38:16Z10261An effective approach for the Knapsack problem with
setuphttp://hdl.handle.net/11583/2574545Titolo: An effective approach for the Knapsack problem with
setup
Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/11583/25745452014-01-01T00:00:00ZA review of recent heuristic algorithms for the Critical Node Problemhttp://hdl.handle.net/11583/2639594Titolo: A review of recent heuristic algorithms for the Critical Node Problem
Abstract: We will review several heuristic algorithms we proposed recently to solve different versions of the Critical Node Problem (CNP), i.e. the maximal fragmentation of a graph G given
a connectivity measure, that improve the solution quality greatly over existing competitors.
Thu, 01 Jan 2015 00:00:00 GMThttp://hdl.handle.net/11583/26395942015-01-01T00:00:00ZNew exact approaches and approximation results for the Penalized Knapsack Problemhttp://hdl.handle.net/11583/2698735Titolo: New exact approaches and approximation results for the Penalized Knapsack Problem
Abstract: We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range of penalties, on the identification of a core problem and on dynamic programming. The proposed approach turns out to be very effective in solving hard instances of PKP and compares favorably both to commercial solver CPLEX 12.5 applied to the ILP formulation of the problem and to the best available exact algorithm in the literature. Then we present a general inapproximability result and investigate several relevant special cases which permit fully polynomial time approximation schemes (FPTASs).
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11583/26987352019-01-01T00:00:00ZPolynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problemhttp://hdl.handle.net/11583/2698736Titolo: Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem
Abstract: We study the Distance Critical Node Problem, a generalisation of the Critical Node Problem
where the distances between node pairs impact on the objective function. We establish
complexity results for the problem according to specific distance functions and provide
polynomial and pseudo-polynomial algorithms for special graph classes such as paths, trees
and series–parallel graphs. We also provide additional insights about special cases of the
Critical Node Problem variants already tackled in the literature.
Tue, 01 Jan 2019 00:00:00 GMThttp://hdl.handle.net/11583/26987362019-01-01T00:00:00ZKnapsack Problems with Side Constraintshttp://hdl.handle.net/11583/2667802Titolo: Knapsack Problems with Side Constraints
Abstract: The thesis considers a specific class of resource allocation problems in Combinatorial Optimization: the Knapsack Problems. These are paradigmatic NP-hard problems where a set of items with given profits and weights is available. The aim is to select a subset of the items in order to maximize the total profit without exceeding a known knapsack capacity. In the classical 0-1 Knapsack Problem (KP), each item can be picked at most once.
The focus of the thesis is on four generalizations of KP involving side constraints beyond the capacity bound. More precisely, we provide solution approaches and insights for the following problems: The Knapsack Problem with Setups; the Collapsing Knapsack Problem; the Penalized Knapsack Problem; the Incremental Knapsack Problem.
These problems reveal challenging research topics with many real-life applications. The scientific contributions we provide are both from a theoretical and a practical perspective. On the one hand, we give insights into structural elements and properties of the problems and derive a series of approximation results for some of them. On the other hand, we offer valuable solution approaches for direct applications of practical interest or when the problems considered arise as sub-problems in broader contexts.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11583/26678022017-01-01T00:00:00ZThe stochastic critical node problem over treeshttp://hdl.handle.net/11583/2841409Titolo: The stochastic critical node problem over trees
Abstract: We tackle a stochastic version of the critical node problem (CNP) where the goal is to minimize the pairwise connectivity of a graph by attacking a subset of its nodes. In the stochastic setting considered, the outcome of attacks on nodes is uncertain. In our work, we focus on trees and demonstrate that over trees the stochastic CNP actually generalizes to the stochastic critical element detection problem where the outcome of attacks on edges is also uncertain. We prove the NP-completeness of the decision version of the problem when connection costs are one, while its deterministic counterpart was proved to be polynomial. We then derive a nonlinear model for the considered CNP version over trees and provide a corresponding linearization based on the concept of probability chains. Moreover, given the features of the derived linear model, we devise an exact Benders decomposition (BD) approach where we solve the slave subproblems analytically. A strength of our approach is that it does not rely on any statistical approximation such as the sample average approximation, which is commonly employed in stochastic optimization. We also introduce an approximation algorithm for the problem variant with unit connection costs and unit attack costs, and a specific integer linear model for the case where all the survival probabilities of the nodes in case of an attack are equal. Our methods are capable of solving relevant instances of the problem with hundreds of nodes within 1 hour of computational time. With this work, we aim to foster research on stochastic versions of the CNP, a problem tackled mainly in deterministic contexts so far. Interestingly, we also show a successful application of the concept of probability chains for problem linearizations significantly improved by decomposition methods such as the BD.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11583/28414092020-01-01T00:00:00ZAn exact approach for the bilevel knapsack problem with interdiction constraints and extensionshttp://hdl.handle.net/11583/2876215Titolo: An exact approach for the bilevel knapsack problem with interdiction constraints and extensions
Abstract: We 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.
Wed, 01 Jan 2020 00:00:00 GMThttp://hdl.handle.net/11583/28762152020-01-01T00:00:00ZA general Evolutionary Framework for different classes of Critical Node Problemshttp://hdl.handle.net/11583/2644883Titolo: A general Evolutionary Framework for different classes of Critical Node Problems
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11583/26448832016-01-01T00:00:00ZA preliminary analysis of the Distance Based Critical Node Problemhttp://hdl.handle.net/11583/2656884Titolo: A preliminary analysis of the Distance Based Critical Node Problem
Abstract: We discuss how to develop efficient heuristics for the distance based critical node problem, that is the problem of deleting a subset of nodes from a graph G in such a way that the distance between each pair of nodes is as large as possible.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/11583/26568842016-01-01T00:00:00ZA new exact approach for the 0–1 Collapsing Knapsack Problemhttp://hdl.handle.net/11583/2659040Titolo: A new exact approach for the 0–1 Collapsing Knapsack Problem
Abstract: We consider the 0/1 Collapsing Knapsack Problem (CKP) and a generalization involving more than a capacity constraint (M-CKP). We propose a novel ILP formulation and a problem reduction procedure together with an exact approach. The proposed approach compares favorably to the methods available in the literature and manages to solve to optimality very large size instances particularly for CKP and 2-CKP.
Sun, 01 Jan 2017 00:00:00 GMThttp://hdl.handle.net/11583/26590402017-01-01T00:00:00Z