China
Africa
Explore chapters and articles related to this topic
Policy-Based Distributed Spectrum Allocation
Published in Anna Maria Vegni, Dharma P. Agrawal, Cognitive Vehicular Networks, 2018
Flavio Esposito, Donato Di Paola
Being a combination of other NP-hard problems, it is trivial to show that the cognitive vehicular network spectrum allocation problem is NP-hard. We omit the formal proof but we give a general intuition. Let us consider the multi-commodity flow constraints of the problem. In its decision version, the problem of producing an integer flow satisfying all demands has been shown to be NP-complete [11], even when only two flow commodities and their capacities are unitary, making the problem strongly NP-complete in this case. If fractional flows are allowed, i.e., if a flow can be split among multiple “virtual channels” among vehicles, the problem can be solved in polynomial time through linear programming [6] or via fully polynomial time approximation schemes [19], typically much faster. Aside from the multi-commodity flow constraints, we note how few of the other constraints are equivalent to the set packing problem (known to be an NP-hard problem [16]). An optimal algorithm able to determine the capacity and the interference free constraints would have to try all possible combinations of assignments to decide which is the candidate that maximizes the network utility.
A learning-based solution method for practical slab allocation problem in multiple hot rolling lines
Published in IISE Transactions, 2023
Ying Meng, Qingxin Guo, Qingyang Wang, Haichao Wang
In the set-packing model mentioned above, the number of variables grows exponentially with the growth of the problem scale. Column generation is an effective method to solve LP problems with a very large number of variables. It is often used within the B&B framework to solve large integer programs (Barnhart et al.,1998; Tang et al.,2016). The idea of the column generation algorithm is as follows. A restricted master problem, including only a subset of the columns of the LP relaxation, is solved first. The values of the dual variables of the restricted master problem are used to update the pricing subproblems, which are then solved to find columns with a negative reduced cost in the minimization problem. If such columns exist, they are added to the restricted master problem. The procedure is repeated until there is no column with a negative reduced cost. The obtained solution is the optimal solution for the LP relaxation.
Iterative combinatorial auctions for managing product transitions in semiconductor manufacturing
Published in IISE Transactions, 2020
Ankit Bansal, Reha Uzsoy, Karl Kempf
The WDP can be formulated as a weighted set packing problem, which is known to be NP-hard (De Vries and Vohra, 2003). Various exact and heuristic approaches for the WDP have been proposed (Andersson et al., 2000; Sandholm, 2002; Jones and Koehler, 2005; Lehmann et al., 2006). If there is no integrality gap between the WDP and its Linear Programming (LP) relaxation (i.e., the WDP has the integrality property), the primal and dual solutions to the LP relaxation of the WDP represent a Walrasian equilibrium of the allocation problem (Abrache et al., 2007). Bikhchandani and Ostroy (2002) provide two extended formulations for the WDP that satisfy the integrality property. However, these formulations require exponentially many variables and constraints, rendering them impractical for combinatorial auctions involving divisible goods. O’Neill et al. (2005) present an approach for calculating Competitive Equilibrium prices for a general WDP formulation that may not satisfy the integrality property, assuming complete sharing of information between the bidding agents and the auctioneer.