Search

Copyright of Retos: Nuevas Perspectivas de Educación Física, Deporte y Recreación is the property of Federacion Espanola de Asociaciones de Docentes de Educacion Fisica and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

System autonomy plays a critical role in the success of next generation Distributed Satellite Systems (DSS) mission architectures, enabling the inference of external and internal environment conditions to support system adaptation in unexpected and unfamiliar situations. Artificial Intelligence (AI) based techniques show promise in achieving this desired self-adaptive capability by offering on-board predictive real time analytics, supporting an evolution towards Trusted Autonomous Satellite Operations (TASO). In parallel, TASO requires an evolution of the control and coordination of increasingly autonomous large scale DSS, achieved in the design and operation of intelligent Mission Planning Systems (MPS). In this paper, we focus on intelligent mission planning functionality problem utilising a distributed ant colony optimisation approach to achieve local task allocation and platform coordination. The approach is implemented in the context of a Space-Based Space Surveillance (SBSS) mission architecture that considers self-adaptive capabilities, global coordination and supervisory control aspects. The effectiveness of the approach is shown, demonstrating that the proposed solution based on metaheuristics supports an efficient and pervasive SBSS capability. • The following are the main contributions of the work presented in the manuscript. • Addressing the dynamic task allocation problem for Resident Space Objects (RSO) surveillance by a Distributed Satellite System (DSS) for Space-Based Space Surveillance (SBSS) by formulating it as a dynamic knapsack problem, which is then trascribed mathematically in a constrained nonlinear optimisation problem; • Introducing an intelligent mission planning functionality, which utilises a distributed ant colony optimisation method to achieve local task allocation and multi-platform coordination across the SBSS DSS. This approach overcomes the limitation of legacy methods by granting to the system the ability to make inferences and decisions in the highly nonlinear solution space as well as under unexpected and unfamiliar situations; • Application of the proposed solution method under situations that might be anticipated in a realistic space surveillance network, opening the way for an efficient and pervasive SBSS which, in conjunction with ground-based observation facilities, can enable a seamless, reliable and effective Space Domain Awareness (SDA) [ABSTRACT FROM AUTHOR]

In this paper, we present a solution method for the multidimensional knapsack problem (MKP) and the knapsack problem with forfeit sets (KPFS) using a population-based matheuristic approach. Specifically, the learning mechanism of the fixed set search (FSS) metaheuristic is combined with the use of integer programming for solving subproblems. This is achieved by introducing a new ground set of elements that can be used for both the MKP and the KPFS that aim to maximize the information provided by the fixed set. The method for creating fixed sets is also adjusted to enhance the diversity of generated solutions. Compared to state-of-the-art methods for the MKP and the KPFS, the proposed approach offers an implementation that can be easily extended to other variants of the knapsack problem. Computational experiments indicate that the matheuristic FSS is highly competitive to best-performing methods from the literature. The proposed approach is robust in the sense of having a good performance for a wide range of parameter values of the method. [ABSTRACT FROM AUTHOR]

In this paper, an entirely novel discrete probabilistic model is presented to generate 0-1 Knapsack Problem instances. We analyze the expected behavior of the greedy algorithm, the eligible-first algorithm and the linear relaxation algorithm for these instances; all used to bound the solution of the 0-1 Knapsack Problem (0-1 KP) and/or its approximation. The probabilistic setting is given and the main random variables are identified. The expected performance for each of the aforementioned algorithms is analytically established in closed forms in an unprecedented way. [ABSTRACT FROM AUTHOR]

This work address a variant of the knapsack problem, known as the knapsack problem with forfeits, which has numerous applications. In this variant, a set of items and a conflict graph are given, and the objective is to identify a collection of items that adhere to the knapsack's capacity while maximizing the total value of the items minus the penalties for conflicting items. We propose a novel heuristic for this problem based on the concepts of iterated local search, variable neighborhood descent, and tabu search. Our heuristic takes into account four neighborhood structures, and we introduce efficient data structures to explore them. Experimental results demonstrate that our approach outperforms the state-of-the-art algorithms in the literature. In particular, it delivers superior solutions within significantly shorter computation times across all benchmark instances. Additionally, this study includes an analysis of how the proposed data structures have influenced both the quality of the solutions and the execution time of the method. [ABSTRACT FROM AUTHOR]

Heuristics aim to provide approximate solutions for NP-hard combinatorial optimization (CO) problems in a reasonable time. They are faster than deterministic methods, where the solving process may take days. This paper presents an attempt to combine a heuristic algorithm and some machine learning (ML) methods for solving the Multidimensional Knapsack Problem (MKP), which is a well-known CO case. The approach named Genetic Algorithm and Machine Learning (GAML) is a two-step algorithm that first uses four machine methods to produce four solutions and then integrates the best one within the GA. For this purpose, (1) This approach builds models by training four machine learning (ML) methods using the decision variables obtained from the optimal solutions of simple MKP instances. The decision variable of an item is equal to one if it is selected in the knapsack and zero otherwise. (2) The four models are applied to predict the decision variables for complex MKP instances. (3) A dummy algorithm constructs feasible solutions from the predictions by adding the selected items randomly while the constraints are not violated. (4) For each MKP instance, the best feasible solution among the four built is integrated with the initialization and the crossing operators of a genetic algorithm. An experiment has been conducted on well-known complex MKP benchmarks. The results proved that the models were able to provide high-quality solutions. Also, the proposed algorithm was faster than other approaches in the literature. [ABSTRACT FROM AUTHOR]

Arithmetic optimization algorithm (AOA) is a recently proposed algorithm inspired by mathematical operations. It has been used to solve a variety of optimization problems due to its simplicity of parameters and ease of implementation. However, it has been found that AOA encounters challenges such as poor exploration and premature convergence. To solve these issues, this paper proposes a self-adaptive AOA with hybrid search modes, named AOAHSM. In this algorithm, two hybrid search modes, i.e., the parallel search mode and the serial search mode, are established by combining AOA and differential evolution (DE) in different ways to enhance the exploration and exploitation abilities, respectively. In the parallel search mode, AOA and DE independently implement on their respective subpopulations to maintain a high distribution of the population. In the serial search mode, DE is embedded into AOA to provide more diversified solutions and thereby help the population jump out of local optima. Then, a self-adaptive conversion strategy is employed to dynamically switch between the two modes so as to achieve a better balance between exploration and exploitation. Additionally, a Levy flight strategy is used to perturb and update the best solution obtained in each iteration to further prevent premature convergence. Lastly, a binary version of AOAHSM is proposed to tackle the 0–1 knapsack problem. The proposed algorithms are evaluated on CEC2019, CEC2020 test functions, two typical engineering design problems and 45 instances of the 0–1 knapsack problem and compared with a number of state-of-the-art meta-heuristic algorithms. The obtained results demonstrate that AOAHSM and its binary version not only significantly outperform the original AOA but also achieve superior performance to the comparison algorithms in most cases. [ABSTRACT FROM AUTHOR]

The knapsack problem is a typical bi-objective combinatorial optimization issue, wherein maximizing the value of the packed items is achieved concurrently with minimizing the weight of the load. Due to the conflicting objectives of the knapsack problem and the typical discrete property of the items involved, swarm intelligence algorithms are commonly employed. The diversity of optimal combinations in the knapsack problem has become a focal point, which involves finding multiple packing solutions at the same value and weight. For this purpose, this paper proposes a Multi-Objective Equilibrium Optimizer Algorithm based on Weighted Congestion Distance (MOEO_WCD). The algorithm employs a non-dominated sorting method to find a set of Pareto front solutions rather than a single optimal solution, offering multiple decision-making options based on the varying needs of the decision-makers. Additionally, MOEO_WCD improves the balance pool generation mechanism and incorporates a weighted congestion incentive, emphasizing the diversity of packing combination solutions under the objectives of value and weight to explore more Pareto front solutions. Considering the discrete characteristics of the knapsack combination optimization problem, our algorithm also incorporates appropriate discrete constraint handling. This paper designs multiple sets of multi-objective knapsack combinatorial optimization problems based on the number of knapsacks, the number of items, and the weights and values of the items. This article compares five algorithms suitable for solving multi-objective problems: MODE, MO-PSO-MM, MO-Ring-PSO-SCD, NSGA-II, and DN-NSGAII. In order to evaluate the performance of the algorithm, this paper proposes a new solution set coverage index for evaluation. We also used the hypervolume indicator to evaluate the diversity of algorithms. The results show that our MOEO-WCD algorithm achieves optimal coverage of the reference composite Pareto front in the decision space of four knapsack problems. The experimental results indicate that our MOEO_WCD algorithm achieves the optimal coverage of the reference composite Pareto front in the decision space for four sets of knapsack problems. Although our MOEO_WCD algorithm covers less of the composite front in the objective space compared with the MODE algorithm for knapsack problem 1, its coverage of the integrated reference solutions in the decision space is greater than that of the MODE algorithm. The experiments demonstrate the superior performance of the MOEO_WCD algorithm on bi-objective knapsack combinatorial optimization problem instances, which provides an important solution to the search for diversity in multi-objective combinatorial optimization solutions. [ABSTRACT FROM AUTHOR]

The list-based threshold accepting (LBTA) algorithm is a sophisticated local search method that utilizes a threshold list to streamline the parameter tuning process in the traditional threshold accepting (TA) algorithm. This paper proposes an enhanced local search version of the LBTA algorithm specifically tailored for solving the 0–1 knapsack problem (0–1 KP). To maintain a dynamic threshold list, a feasible threshold updating strategy is designed to accept adaptive modifications during the search process. In addition, the algorithm incorporates an improved bit-flip operator designed to generate a neighboring solution with a controlled level of disturbance, thereby fostering exploration within the solution space. Each trial solution produced by this operator undergoes a repair phase using a hybrid greedy repair operator that incorporates both density-based and value-based add operator to facilitate optimization. The LBTA algorithm's performance was evaluated against several state-of-the-art metaheuristic approaches on a series of large-scale instances. The simulation results demonstrate that the LBTA algorithm outperforms or is competitive with other leading metaheuristics in the field. [ABSTRACT FROM AUTHOR]

Coatis optimization algorithm (COA) has recently emerged as an innovative meta-heuristic algorithm (MA) for global optimization, garnering considerable attention from scholars and researchers. In this paper, we introduce three techniques to enhance COA: (1) the cooperative mechanism, (2) the fitness-based division, and (3) the optional base vector strategy. Collectively, we refer to our improved method as cooperative COA (CCOA). In addition, we introduce the incorporation of the S-shaped Sigmoid transfer function and the V-shaped Tanh transfer function into CCOA, leading to the development of SCCOA and VCCOA. These adaptations effectively address the challenges posed by feature selection tasks and the 0/1 knapsack problem. To comprehensively evaluate the performance of the continuous version of CCOA, as well as the binary versions of SCCOA and VCCOA, we conducted two distinct categories of numerical experiments. Firstly, we compared CCOA with nine representative MAs, including the original COA, on CEC2020 benchmark functions and six engineering optimization problems. Secondly, SCCOA and VCCOA are compared with six famous binary MAs on 13 feature selection datasets and 18 standard 0/1 knapsack problems. Experimental and statistical results show the competitiveness of CCOA and its binary versions, and it is promising to extend CCOA to various real-world application scenarios. [ABSTRACT FROM AUTHOR]

The complementarity knapsack problem (CKP) is a knapsack problem with real-valued variables and complementarity conditions between pairs of variables. We extend the polyhedral studies of de Farias et al. for CKP, by proposing three new families of cutting-planes that are obtained from a combinatorial concept known as pack. Sufficient conditions for these inequalities to be facet-defining, based on the new concept of a maximal switching pack , are also provided. Moreover, we answer positively a conjecture by de Farias et al. about the separation complexity of the inequalities introduced in their work, and propose efficient separation algorithms for our newly defined cutting-planes. [ABSTRACT FROM AUTHOR]

This work addresses the Knapsack Problem with Forfeit Sets, a recently introduced variant of the 0/1 Knapsack Problem considering subsets of items associated with contrasting choices. Some penalty costs need to be paid whenever the number of items in the solution belonging to a forfeit set exceeds a predefined allowance threshold. We propose an effective metaheuristic to solve the problem, based on the Biased Random-Key Genetic Algorithm paradigm. An appropriately designed decoder function assigns a feasible solution to each chromosome, and improves it using some additional heuristic procedures. We show experimentally that the algorithm outperforms significantly a previously introduced metaheuristic for the problem. [ABSTRACT FROM AUTHOR]

In this paper, we address the aspect of knapsack balancing in the classic knapsack problem. Recognizing that excessive dispersion in the objective function or constraint coefficients of the optimal solution can be undesirable, we propose, when appropriate, to control this effect through problem multiobjectivization. By multiobjectivization, we mean the addition of one or more objective functions that aim to shift the original problem's optimal solutions towards Pareto optimal solutions of the multiobjectivized problem, reducing the dispersion of the respective coefficients. We detail how the knapsack balance aspect can be incorporated into the standard knapsack problem model and demonstrate the functionality of this enriched model through illustrative examples. [ABSTRACT FROM AUTHOR]

The growing adoption of electric vehicles (EVs) has resulted in an increased demand for public EV charging infrastructure. Currently, the collaboration between these stations has become vital for efficient charging scheduling and cost reduction. However, most existing scheduling methods primarily focus on recommending charging stations without considering users' charging preferences. Adopting these strategies may require considerable modifications to how people charge their EVs, which could lead to a reluctance to follow the scheduling plan from charging services in real-world situations. To address these challenges, we propose the POSKID framework in this article. It focuses on spatial-temporal charging scheduling, aiming to recommend a feasible charging arrangement, including a charging station and a charging time slot, to each EV user while minimizing overall operating costs and ensuring users' charging satisfaction. The framework adopts an online charging mechanism that provides recommendations without prior knowledge of future electricity information or charging requests. To enhance users' willingness to accept the recommendations, POSKID incorporates an incentive strategy and a novel embedding method combined with Bayesian personalized analysis. These techniques reveal users' implicit charging preferences, enhancing the success probability of the charging scheduling task. Furthermore, POSKID integrates an online candidate arrangement selection and an explore-exploit strategy to improve the charging arrangement recommendations based on users' feedback. Experimental results using real-world datasets validate the effectiveness of POSKID in optimizing charging management, surpassing other strategies. The results demonstrate that POSKID benefits each charging station while ensuring user charging satisfaction. [ABSTRACT FROM AUTHOR]

A classical result by Myerson (Math. Oper. Res. 6(1), 58-73, 1981) gives a characterization of an optimal auction for any given distribution of valuations of the bidders. We consider the situation where the distribution is not explicitly given but can be observed in a sample of auction results from the same distribution. A seminal paper by Morgenstern and Roughgarden (Adv.Neural Inf. Process. Syst. 28, 2015) proposes to learn a near-optimal auction from the hypothesis class of t-level auctions. They prove a bound on the sample complexity, i.e., the function f (ε , δ) of required samples to guarantee a certain level of precision (1 - ε) with a probability of at least (1 - δ) , for the general single-parameter case and a tighter bound for the very restricted matroid case. We show a new bound for the case of independence systems, that widely generalizes matroids and contains several important combinatorial optimization problems. This bound of O ~ H 2 n 4 ε 3 falls neatly between those known for the general and the matroid case. The class of independence systems contains several well known NP-hard problems such as knapsack. Therefore, the allocation itself might in practice be limited to α -approximate solutions. In a second result we show that an approximation algorithm can be used without compromising the sample complexity. Also, the precision is affected only mildly, resulting in a factor of α · (1 - ε) . [ABSTRACT FROM AUTHOR]

The development of transport infrastructure is crucial for economic growth, social connectivity, and sustainable development. Many countries have historically underinvested in transport infrastructure, necessitating more efficient strategic planning in the implementation of transport infrastructure investment projects. This article addresses the selection and scheduling of transport infrastructure projects, specifically within the context of utilizing pre-allocated funds within a multi-annual budget investment program. The current decision-making process relies heavily on expert judgment and lacks quantitative decision support methods. We propose a genetic algorithm as a decision-support tool, framing the problem as an NP-hard 0–1 multiple knapsack problem. The proposed genetic algorithm (GA) is unique for its matrix-encoded chromosomes, specially designed genetic operators, and a customized repair operator to address the large number of invalid chromosomes generated during the GA computation. In computational experiments, the proposed GA is compared to an exact solution and proves to be efficient in terms of quality of obtained solutions and computational time, with an average computational time of 108 s and the quality of obtained solutions typically ranging between 85% and 95% of the optimal solution. These results highlight the potential of the proposed GA to enhance strategic decision-making in transport infrastructure development. [ABSTRACT FROM AUTHOR]

The widespread adoption of Internet of Things (IoT) applications has driven the demand for obtaining sensor data. Using unmanned aerial vehicles (UAVs) to collect sensor data is an effective means in scenarios with no ground communication facilities. In this paper, we innovatively consider an indeterministic data collection task in a UAV-assisted wide and sparse wireless sensor network, where the wireless sensor nodes (SNs) obtain effective data randomly, and the UAV has no pre-knowledge about which sensor has effective data. The UAV trajectories, SN serve scheduling and UAV-SN association are jointly optimized to maximize the amount of collected effective sensing data. We model the optimization problem and address the indeterministic effective indicator by introducing an effectiveness probability prediction model. The reformulated problem remains challenging to solve due to the number of constraints varying with the variable, i.e., the serve scheduling strategy. To tackle this issue, we propose a two-layer modified knapsack algorithm, within which a feasibility problem is resolved iteratively to find the optimal packing strategy. Numerical results demonstrate that the proposed scheme has remarkable advantages in the sum of effective data blocks, reducing the completion time for collecting the same ratio of effective data by nearly 30%. [ABSTRACT FROM AUTHOR]

Science Centers carry out their missions through the exhibits and exhibitions they have. The selection of the exhibits is made under the space limitations and budget constraints, taking into account the center's goals and the visitor profile. However, there is no mathematical approach in the literature for the selection of exhibits in order to create exhibitions for the determined objective. It is seen that intuitive methods are applied and especially the experiences of the curators are used to create the exhibition for science centers. Creating a new exhibition for a science center can be taken as the process of bringing together a portfolio of various exhibits to optimize certain objectives and can be modeled as a knapsack problem. In this study, a mathematical programming-based multiobjective method is proposed for the selection of the most suitable exhibits in science centers. The problem is considered as a multiobjective, multidimensional knapsack problem. It is modeled and solved as a 0-1 integer programming model. Suggested model selects the exhibits that supports the mission of the science center at a high level, has a high instructional level and attractiveness under the constraints of the total area, purchasing budget and annual operating budget. In the model, there is an additional constraint to ensure that the exhibits that make up the portfolio are selected from different fields of science. Considering the time required to solve the various problems created and the number of dominant solutions obtained, it can be said that the proposed model can be easily used in real life problems. [ABSTRACT FROM AUTHOR]

This paper studies the constrained two-dimensional guillotine cutting problem with defects, whose objective is to cut a subset of given items from a defective sheet such that the profit of selected items is maximised. The guillotine cut constraint, which requires each cut must go through one side of the sheet to the opposite side, is considered. We solve this problem via a recursive dynamic programming approach. A set of upper bounds is proposed to keep the promising nodes. The normal points and raster points are extended to reduce the number of vertical and horizontal cuts by considering the effect of the defect. The experiment results show that our approach can solve most of the instances in the literature and outperforms existing approaches. [ABSTRACT FROM AUTHOR]

In 2009, Lyubashevsky proposed a lattice-based signature scheme using the Schnorr-like identification and the Fiat-Shamir heuristic and proved its security under the collision resistance of a generalized compact knapsack function. However, their security analysis requires the witness indistinguishability property, leading to significant inefficiency and an increase of sizes of public key and signature. To overcome the efficiency issue associated with the WI property, we introduce a new lattice-based assumption, called the target-modified one-wayness problem of the GCK function and show its reduction to well-known lattice-based problems. Additionally, we present a simple and efficient GCK-based signature scheme, GCKSign, whose security is based on the Module GCK-TMO problem in the random oracle model. GCKSign is a natural extension of Lyubashevsky's scheme in a module setting, but achieves considerable efficiency gains due to eliminating the witness indistinguishability property. As a result, GCKSign achieves approximately 3.4 times shorter signature size and 2.4 times shorter public key size at the same security level. [ABSTRACT FROM AUTHOR]

Many everyday tasks require people to solve computationally complex problems. However, little is known about the effects of computational hardness on the neural processes associated with solving such problems. Here, we draw on computational complexity theory to address this issue. We performed an experiment in which participants solved several instances of the 0-1 knapsack problem, a combinatorial optimization problem, while undergoing ultra-high field (7T) functional magnetic resonance imaging (fMRI). Instances varied in computational hardness. We characterize a network of brain regions whose activation was correlated with computational complexity, including the anterior insula, dorsal anterior cingulate cortex and the intra-parietal sulcus/angular gyrus. Activation and connectivity changed dynamically as a function of complexity, in line with theoretical computational requirements. Overall, our results suggest that computational complexity theory provides a suitable framework to study the effects of computational hardness on the neural processes associated with solving complex cognitive tasks. Author summary: Humans are frequently faced with complex decisions, ranging from everyday tasks like grocery shopping to more intricate decisions such as selecting an investment portfolio. These decisions require higher-order problem-solving skills, which remain poorly understood, particularly regarding the neural processes that support deliberation. In this study, we introduce a framework that employs computational complexity theory to investigate the neural activity that occurs during complex problem-solving. We suggest that the inherent characteristics of a problem determine its computational difficulty, and that these intrinsic features could be used to identify consistent neural patterns during complex problem-solving. To test this approach, we applied it to the knapsack problem, a standard computational problem. Participants solved several versions of this problem while their brain activity was monitored using an ultra-high field MRI. By leveraging computational complexity theory, we developed generic metrics of computational difficulty and successfully identified the corresponding neural correlates and their dynamics during problem-solving. The results indicate that the proposed framework, grounded in computational complexity theory, offers a promising method for studying the neural processes involved in complex problem-solving. This approach could provide valuable insights into a topic that has previously resisted formal investigation. [ABSTRACT FROM AUTHOR]

With the development of the IoT, Wireless Rechargeable Sensor Networks (WRSNs) derive more and more application scenarios with diverse performance requirements. In scenarios where the energy consumption rate of sensor nodes changes dynamically, most existing charging scheduling methods are not applicable. The incorrect estimation of node energy requirement may lead to the death of critical nodes, resulting in missing events. To address this issue, we consider both the spatial imbalance and temporal dynamics of the energy consumption of the nodes, and minimize the Event Missing Rate (EMR) as the goal. Firstly, an Energy Consumption Balanced Tree (ECBT) construction method is proposed to prolong the lifetime of each node. Then, we transform the goal into Maximizing the value of the Evaluation function of each node's Energy Consumption Rate prediction (MEECR). Afterwards, the setting of the evaluation function is explored and the MEECR is further transformed into a variant of the knapsack problem, namely "the alternating backpack problem", and solved by dynamic programming. After predicting the energy consumption rate of the nodes, a charging scheduling scheme that meets the Dual Constraints of Nodes' energy requirements and MC's capability (DCNM) is developed. Simulations demonstrate the advantages of the proposed method. Compared to the baselines, the EMR was reduced by an average of 35.2% and 26.9%. [ABSTRACT FROM AUTHOR]

Adaptive influence maximization is an important research problem in computational social networks, which is also a typical problem in the study of adaptive processing of information and adaptive construction of objects. In this paper, we propose a new method that reduces the adaptive influence maximization problem into a nonadaptive one in a different social network, so that an adaptive optimization can be solved by those methods for nonadaptive optimization. In addition, we provide a new approximation algorithm for the submodular maximization problem with a knapsack constraint, which runs in O(n2) time and has performance ratio 1−1/e , where n is the number of nodes in the network. The ratio is better than the best known previous one with the same running time. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This research is supported in part by the National Natural Science Foundation of China [Grant U20A2068]. [ABSTRACT FROM AUTHOR]

Several real-life problems are comprised of finite single-server acyclic queueing networks. The performance optimization of these queueing networks has been the subject of several studies. The present study extends the minimization of the total buffer area and overall service rates in the network simultaneously with the maximization of throughput. It is well known that these three objectives are conflicting. This fact leads to a multi-objective approach that the literature in the area has already addressed. Nevertheless, this study aims to demonstrate that there are algorithms with low computational costs that can produce solutions more efficiently than those obtained previously. Furthermore, the provided solutions can enhance throughput by solving a stochastic knapsack problem. The greedy procedure utilizes a technique of redistributing buffers between the queues, ensuring that the overall capacity is less than or equal to the previous overall capacity; thus, one objective is improved (the throughput) without compromising the other objective (total buffer allocation). Several computational experiments attest to the quality of this proposition. In addition, we provide a comparison with previously proposed solutions. [ABSTRACT FROM AUTHOR]

Various metaheuristic algorithms inspired by nature have been designed to deal with a variety of practical optimization problems. As an excellent metaheuristic algorithm, the improved particle swarm optimization algorithm based on grouping (IPSO) has strong global search capabilities. However, it lacks a strong local search ability and the ability to solve constrained discrete optimization problems. This paper focuses on improving these two aspects of the IPSO algorithm. Based on IPSO, we propose an improved particle swarm optimization algorithm based on variable neighborhood search (VN-IPSO) and design a 0-1 integer programming solution with constraints. In the experiment, the performance of the VN-IPSO algorithm is fully tested and analyzed using 23 classic benchmark functions (continuous optimization), 6 knapsack problems (discrete optimization), and 10 CEC2017 composite functions (complex functions). The results show that the VN-IPSO algorithm wins 18 first places in the classic benchmark function test set, including 6 first places in the solutions for seven unimodal test functions, indicating a good local search ability. In solving the six knapsack problems, it wins four first places, demonstrating the effectiveness of the 0-1 integer programming constraint solution and the excellent solution ability of VN-IPSO in discrete optimization problems. In the test of 10 composite functions, VN-IPSO wins first place four times and ranks the first in the comprehensive ranking, demonstrating its excellent solving ability for complex functions. [ABSTRACT FROM AUTHOR]

We study continuous, equality knapsack problems with uniform separable, non-convex objective functions that are continuous, antisymmetric about a point, and have concave and convex regions. For example, this model captures a simple allocation problem with the goal of optimizing an expected value where the objective is a sum of cumulative distribution functions of identically distributed normal distributions (i.e., a sum of inverse probit functions). We prove structural results of this model under general assumptions and provide two algorithms for efficient optimization: (1) running in linear time and (2) running in a constant number of operations given preprocessing of the objective function. [ABSTRACT FROM AUTHOR]

A variant of the online knapsack problem is considered in the setting of predictions. In Unit Profit Knapsack, the items have unit profit, i.e., the goal is to pack as many items as possible. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. The prediction available to the online algorithm is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio r = a a ^ where a is the actual value for this average size and a ^ is the prediction. We give an algorithm which is e - 1 e -competitive, if r = 1 , and this is best possible among online algorithms knowing a and nothing else. More generally, the algorithm has a competitive ratio of e - 1 e r , if r ≤ 1 , and e - r e r , if 1 ≤ r < e . Any algorithm with a better competitive ratio for some r < 1 will have a worse competitive ratio for some r > 1 . To obtain a positive competitive ratio for all r, we adjust the algorithm, resulting in a competitive ratio of 1 2 r for r ≥ 1 and r 2 for r ≤ 1 . We show that improving the result for any r < 1 leads to a worse result for some r > 1 . [ABSTRACT FROM AUTHOR]

About 15 years ago, a paper proposed the first integer linear programming formulation for the constrained two‐dimensional guillotine cutting problem (with unlimited cutting stages). Since then, eight other formulations followed, seven of them in the last four years. This spike of interest gave no opportunity for a comprehensive comparison between the formulations. We review each formulation and compare their empirical results over instance datasets of the literature. We adapt most formulations to allow for piece rotation. The possibility of adaptation was already predicted but not realized by the prior work. The results show the dominance of pseudo‐polynomial formulations until the point instances become intractable by them, while more compact formulations keep achieving good primal solutions. Our study also reveals a mistake in the generation of the T instances, which should have the same optima with or without guillotine cuts. We also propose hybridising a recent formulation with a prior formulation for a restricted version of the problem. The hybridisations show a reduction of about 20% of the branch‐and‐bound time thanks to the symmetries broken by the hybridisation. [ABSTRACT FROM AUTHOR]

Reducing material waste and computation time are primary objectives in cutting and packing problems (C &P). A solution to the C &P problem consists of many steps, including the grouping of items to be nested and the arrangement of the grouped items on a large object. Current algorithms use meta-heuristics to solve the arrangement problem directly without explicitly addressing the grouping problem. In this paper, we propose a new pipeline for the nesting problem that starts with grouping the items to be nested and then arranging them on large objects. To this end, we introduce and motivate a new concept, namely the Geometrical Compatibility Index (GCI). Items with higher GCI should be clustered together. Since no labels exist for GCIs, we propose to model GCIs as bidirectional weighted edges of a graph that we call geometrical relationship graph (GRG). We propose a novel reinforcement-learning-based framework, which consists of two graph neural networks trained in an actor-critic-like fashion to learn GCIs. Then, to group the items into clusters, we model the GRG as a capacitated vehicle routing problem graph and solve it using meta-heuristics. Experiments conducted on a private dataset with regularly and irregularly shaped items show that the proposed algorithm can achieve a significant reduction in computation time (30% to 48%) compared to an open-source nesting software while attaining similar trim loss on regular items and a threefold improvement in trim loss on irregular items. [ABSTRACT FROM AUTHOR]

Collaborative edge intelligence, a distributed computing paradigm, refers to a system where multiple edge devices work together to process data and perform distributed machine learning (DML) tasks locally. Decentralized Internet of Things (IoT) devices share knowledge and resources to improve the quality of service (QoS) of the system with reduced reliance on centralized cloud infrastructure. However, the paradigm is vulnerable to free-riding attacks, where some devices benefit from the collective intelligence without contributing their fair share, potentially disincentivizing collaboration and undermining the system's effectiveness. Moreover, data collected from heterogeneous IoT devices may contain biased information that decreases the prediction accuracy of DML models. To address these challenges, we propose a novel incentive mechanism that relies on time-dependent blockchain records and multi-access edge computing (MEC). We formulate the QoS problem as an unbounded multiple knapsack problem at the network edge. Furthermore, a decentralized valuation protocol is introduced atop blockchain to incentivize contributors and disincentivize free-riders. To improve model prediction accuracy within latency requirements, a data scheduling algorithm is given based on a curriculum learning framework. Based on our computer simulations using heterogeneous datasets, we identify two critical factors for enhancing the QoS in collaborative edge intelligence systems: (1) mitigating the impact of information loss and free-riders via decentralized data valuation and (2) optimizing the marginal utility of individual data samples by adaptive data scheduling. [ABSTRACT FROM AUTHOR]

Summary: One of the practical preferences of cloud service providers is to use specialized physical hosts. In other words, the goal is to place homogeneous virtual machines (VMs) on the physical host according to performance criteria such as energy consumption, resource wastage, and utilization. virtual machine placement (VMP) falls into NP‐hard knapsack problems. To overcome the time complexity, the use of heuristic and metaheuristic methods has attracted the attention of researchers. In this paper, we use an entropy‐based method for VMP for the first time. The proposed method tries to place the VMs on physical machines by considering the type of VMs to minimize entropy. Entropy is a measurable property that is more associated with disorder, randomness, or uncertainty. We use one of the most common entropy criteria called the Gini coefficient. In summary, among the different placement combinations of VMs, those that can minimize the Gini coefficient are preferred. We then solve the multi‐objective problem with the non‐dominated sorting genetic algorithm (NSGA‐III). We also combine this method with differential evolution methods to improve the quality of solutions. Recent research in other engineering fields has shown that combining metaheuristic methods with differential evolution methods increases the rate of convergence toward the optimal solution. The simulation results on the CloudSim simulator, along with statistical analysis, show that the entropy‐based method has a significant improvement over the state‐of‐the‐art methods in terms of significant performance criteria such as utilization, resource wastage, and energy consumption. [ABSTRACT FROM AUTHOR]

Exact combinatorial search algorithms have applications in several areas of computational algebra, AI, discrete optimization, etc. These problems are compute-intensive and have a highly irregular search tree. Most of the earlier efforts to parallelize these algorithms used a fixed degree of parallelism during runtime. We show that such an approach leads to poor resource utilization as the parallel run-time efficiency of an irregular search application varies over time. We propose DiGTreeS, a distributed resilient framework for generalized tree search that supports elastic scaling. It features an easy-to-use API for expressing combinatorial search and hides away the system concerns such as load balancing, fault tolerance, and elastic scaling. We evaluate the DiGTreeS framework for different scaling strategies and show its effectiveness on four representative problem instances: Traveling Salesman Problem, 0–1 Knapsack, N-queens, and Generic State Space Search Application. [ABSTRACT FROM AUTHOR]

The multi-mode resource constrained project scheduling problem (MRCPSP) is an NP-hard optimisation problem involving scheduling tasks under resource and precedence constraints, while there are several modes for executing each task. In this paper, we propose a novel matheuristic based on relax-and-solve (R &S) algorithm to solve MRCPSP. In addition, a mathematical programming model, which is the generalisation of the multi-dimensional knapsack problem is developed. That model conducts the mode selection process for the purpose of generating an initial feasible solution. We evaluate the performance of the proposed algorithm by solving benchmark instances that are widely used in the literature. The results demonstrate that the proposed R &S algorithm outperforms the state-of-the-art methods for solving the MRCPSP. [ABSTRACT FROM AUTHOR]

The optimization of Multidimensional Knapsacks with Family‐Split Penalties has been introduced in the literature as a variant of the more classical Multidimensional Knapsack and Multi‐Knapsack problems. This problem deals with a set of items partitioned in families, and when a single item is picked to maximize the utility, then all items in its family must be picked. Items from the same family can be assigned to different knapsacks, and in this situation split penalties are paid. This problem arises in real applications in various fields. This paper proposes a new exact and fast algorithm based on a specific Combinatorial Benders Cuts scheme. An extensive experimental campaign computationally shows the validity of the proposed method and its superior performance compared to both commercial solvers and state‐of‐the‐art approaches. The paper also addresses algorithmic flexibility and scalability issues, investigates challenging cases, and analyzes the impact of problem parameters on the algorithm behavior. Moreover, it shows the applicability of the proposed approach to a wider class of realistic problems, including fixed costs related to each knapsack utilization. Finally, further possible research directions are considered. [ABSTRACT FROM AUTHOR]

In the cloud system, service providers supply a pool of resources in the form of a web service and the services are merged to provide the required composite services. Composing a quality-of-service aware web service is like the knapsack problem and this problem is NP-hard. Different artificial intelligence and heuristic methods have been used to achieve optimal or near-optimal composite services. In this paper, the Ant Lion optimization algorithm was modified and discretized to choose the appropriate web services from the existing services and to provide the optimal composite services. The QWS dataset contains a collection of 2507 real-world web services which are used to evaluate the proposed method. In this study, response time parameters, availability, throughput, success capability, reliability, and latency were used as the web service quality metrics. The results of the conducted experiments confirm that the provided composite service by the proposed method has considerably higher quality than the other related algorithms. Hence, the proposed method can be used in the cloud resource discovery layer. [ABSTRACT FROM AUTHOR]

In this paper, we address the difficulty of solving large-scale multi-dimensional knapsack instances (MKP), presenting a novel deep reinforcement learning (DRL) framework. In this DRL framework, we train different agents compatible with a discrete action space for sequential decision-making while still satisfying any resource constraint of the MKP. This novel framework incorporates the decision variable values in the 2D DRL where the agent is responsible for assigning a value of 1 or 0 to each of the variables. To the best of our knowledge, this is the first DRL model of its kind in which a 2D environment is formulated, and an element of the DRL solution matrix represents an item of the MKP. Our framework is configured to solve MKP instances of different dimensions and distributions. We propose a K-means approach to obtain an initial feasible solution that is used to train the DRL agent. We train four different agents in our framework and present the results comparing each of them with the CPLEX commercial solver. The results show that our agents can learn and generalize over instances with different sizes and distributions. Our DRL framework shows that it can solve medium-sized instances at least 45 times faster in CPU solution time and at least 10 times faster for large instances, with a maximum solution gap of 0.28% compared to the performance of CPLEX. Furthermore, at least 95% of the items are predicted in line with the CPLEX solution. Computations with DRL also provide a better optimality gap with respect to state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

This paper introduces a parallel implementation of an exact two-phase method for solving the bi-objective knapsack problem on a CPU-GPU system. We utilize the Branch-and-Bound procedure in both phases, along with a highly efficient reduction technique to generate all efficient solutions. However, in the first phase, we focus on identifying all supported extreme efficient solutions, followed by reducing the dimension of the problem using an object efficiency reduction algorithm. The second phase is responsible for generating all unsupported efficient solutions. We develop a combined algorithm incorporating both phases, which is implemented in the CUDA language. Our study investigates the impact of parallel computing performance on various numerical instances compared to other exact methods in the literature. Additionally, we confirm the effectiveness of our proposed parallel-solving method by testing uncorrelated instances. [ABSTRACT FROM AUTHOR]

We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling.While the priorwork on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the “classic” adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to algorithm’s reward. We design an algorithm with competitive ratio O(logT ) relative to the best fixed distribution over actions, whereT is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version, and use it as a subroutine to solve the latter. Our algorithm is the first “black-box reduction” frombandits to BwK: it takes an arbitrary bandit algorithm and uses it as a subroutine. We use this reduction to derive several extensions. [ABSTRACT FROM AUTHOR]

Benchmark instances for the unbounded knapsack problem are typically generated according to specific criteria within a given constant range R, and these instances can be referred to as the unbounded knapsack problem with bounded coefficients (UKPB). In order to increase the difficulty of solving these instances, the knapsack capacity C is usually set to a very large value. While current efficient algorithms primarily center on the Fast Fourier Transform (FFT) and (min,+)-convolution method, there is a simpler method worth considering. In this paper, based on the basic Unbounded-DP algorithm, we utilize a recent branch and bound (B&B) result and basic theory of linear Diophantine equation, and propose an improved Unbounded-DP algorithm with time complexity of O (R 4) and space complexity of O (R 3) . Additionally, the algorithm can also solve the All-capacities unbounded knapsack problem within the complexity O (R 4 + C) . In particular, the proof techniques required by the algorithm are primarily covered in the first-year mathematics curriculum, which is convenient for subsequent researchers to grasp. [ABSTRACT FROM AUTHOR]

With the exploration of next-generation network technology, visual internet of things (VIoT) systems impose significant computational and transmission demands on mobile edge computing systems that handle large amounts of offloaded video data. Visual users offload specific tasks to cloud or edge computing platforms to meet strict real-time requirements. However, the available scheduling and computational resources for offloading tasks constantly destroy the system's reliability and efficiency. This paper proposes a mechanism for task offloading and resource optimization based on predictive perception. Firstly, we proposed two LSTM-based decision-making prediction methods. In resource-constrained scenarios, we improve resource utilization by encouraging edge devices to participate in task offloading, ensuring the completion of more latency-sensitive request tasks, and enabling predictive decision-making for task offloading. We propose a polynomial time optimal mechanism for pre-emptive decision task offloading in resource-abundant scenarios. We solve the 0–1 knapsack problem of offloading tasks to better meet the demands of low-latency tasks where the system's available resources are not constrained. Finally, we provide numerical results to demonstrate the effectiveness of our scheme. [ABSTRACT FROM AUTHOR]

The power word problem for a group G asks whether an expression u 1 x 1 ⋯ u n x n , where the u i are words over a finite set of generators of G and the x i binary encoded integers, is equal to the identity of G . It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over G ). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group G is uNC 1 -many-one reducible to the power word problem for a finite-index subgroup of G . For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is AC 0 -Turing-reducible to the word problem for the free group F 2 and the power word problems of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups C without order two elements, the uniform power word problem in a graph product can be solved in AC 0 [ C = L UPowWP (C) ] , where UPowWP (C) denotes the uniform power word problem for groups from the class C . As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is NP -complete. The present paper is a combination of the two conference papers (Lohrey and Weiß 2019b, Stober and Weiß 2022a). In Stober and Weiß (2022a) our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated in Stober and Weiß (2022a) is true, our proof relies on this additional assumption. [ABSTRACT FROM AUTHOR]

The aim of this paper is to optimize the allocation of multiple advertisements on a Web banner, where the price of an advertisement depends on the location at the banner. This problem can be defined as a two-dimensional single orthogonal knapsack problem with a location-based pixel-price model. A formulation is proposed in which the problem is specified as a 0–1 integer programming problem. As this problem is NP-complete, we mainly focus on a heuristic approach to solve the problem. We propose two new heuristic algorithms: the reactive GRASP algorithm and the partitioning left-justified algorithm. Next to that, we present an exact algorithm that is able to solve small problem instances in a reasonable time. These newly presented algorithms are compared with respect to efficiency and effectiveness to existing algorithms that solve the problem without a location-based pixel-price model. To test the quality of the algorithms, we have executed two experiments. The results of these experiments show that overall the reactive GRASP algorithm is the most effective algorithm, whereas the greedy stripping algorithm is the most efficient. [ABSTRACT FROM AUTHOR]

The Multi-Objective Mixed-Integer Programming (MOMIP) problem is one of the most challenging. To derive its Pareto optimal solutions one can use the well-known Chebyshev scalarization and Mixed-Integer Programming (MIP) solvers. However, for a large-scale instance of the MOMIP problem, its scalarization may not be solved to optimality, even by state-of-the-art optimization packages, within the time limit imposed on optimization. If a MIP solver cannot derive the optimal solution within the assumed time limit, it provides the optimality gap, which gauges the quality of the approximate solution. However, for the MOMIP case, no information is provided on the lower and upper bounds of the components of the Pareto optimal outcome. For the MOMIP problem with two and three objective functions, an algorithm is proposed to provide the so-called interval representation of the Pareto optimal outcome designated by the weighting vector when there is a time limit on solving the Chebyshev scalarization. Such interval representations can be used to navigate on the Pareto front. The results of several numerical experiments on selected large-scale instances of the multi-objective multidimensional 0–1 knapsack problem illustrate the proposed approach. The limitations and possible enhancements of the proposed method are also discussed. [ABSTRACT FROM AUTHOR]

One of the major challenges in managing 5G networks is the reconfiguration of network slices. The task covers in particular reconfiguration and relocation of virtual network functions (VNFs) so as to match the service requirements of the slices and the availability of resources of the data centers. In this article, we study in deep the problem of optimal VNFs reconfiguration analyzing a number of its variants. We define two exact, compact integer linear programming formulations of the VNFs reconfiguration problem, and derive two approximate solution algorithms, one of them based on the column generation method. Numerical tests and comparisons illustrate the performance of the algorithms and the quality of the provided solutions. [ABSTRACT FROM AUTHOR]

For the expansion problem of the maximum capacity spanning arborescence in networks (EMCSA), NP-hardness is proved by constructing an instance of EMCSA from 0-1 knapsack problem, and a heuristic algorithm is designed. Finally, one special version of EMCSA, the expansion problem of the minimum arc number on the maximum capacity spanning arborescence in networks (NEMCSA), is considered. For NEMCSA, a strongly polynomial algorithm, in O(mn) time, is provided by substituting the arc with the minimum weight difference. [ABSTRACT FROM AUTHOR]

Cloud applications are built from a set of components often deployed as containers, which can be deployed individually on separate Virtual Machines (VMs) or grouped on a smaller set of VMs. Additionally, the application owner may have inhibition constraints regarding the co-location of components. Finding the best way to deploy an application means finding the best groups of components and the best VMs, and it is not trivial because of the complexity coming from the number of possible options. The problem can be mapped onto may known combinatorial problems as binpacking and knapsack formulations. However, these approaches often assume homogeneus resources and fail to incorporate the inhibition constraints. The main contribution of this paper are firstly a novel formulation of the grouping problem as constrained Coalition Structure Generation (CSG) problem, including the specification of the value function which fulfills the criteria of a Characteristic Function Game (CFG). The CSG problem aims to determine stable and disjoint groups of players collaborating to optimize the joint outcome of the game, and a CFG is a common representation of a CSG, where each group is assigned a value and where the value of the game is the sum of the groups' contributions. Secondly, the Integer-Partition (IP) CSG algorithm has been modified and extended to handle constraints. The proposed approach is evaluated with the extended IP algorithm, and a novel exhaustive search algorithm establishing the optimum grouping for comparison. The evaluation shows that our approach with the modified algorithm evaluates on average significantly less combinations than the CSG state-of-the-art algorithm. The proposed approach is promising for optimized constrained Cloud application management as the modified IP algorithm can optimally solve constrained grouping problems of attainable sizes. [ABSTRACT FROM AUTHOR]

Neutral-temperature district heating and cooling (NT-DHC) is a recent concept in the district heating sector. The current literature does not directly address the ability to create comprehensive master plans for NT-DHC systems and reliably model their performance. This research presents a new approach for the evaluation and planning of NT-DHC systems. The methodology involves the use of a knapsack optimization algorithm to perform a comprehensive analysis of the conditions that make the NT-DHC solution competitive against individual heating and cooling technologies. The algorithm determines the optimal combination of potential extensions that maximizes overall economic value. The results of a case study, which was conducted in Italy, show that NT-DHC is more suitable in dense urban areas, while air-to-water heat pumps are better suited for low heat density zones. This methodology aims to reduce the risks associated with energy demand and provide more certainty about which areas a network can expand into to be competitive. It is targeted at energy planners, utilities experts, energy engineers, and district heating experts who require assistance and guidance in the planning and early stages of designing a NT-DHC system. This method might enable pre-feasibility studies and preliminary design to determine the opportunities and limitations of a system of this kind from an economic and technological perspective. [ABSTRACT FROM AUTHOR]

This paper studies a distributionally robust multi-item newsvendor problem, where the demand distribution is unknown but specified with a general event-wise ambiguity set. Using the event-wise affine decision rules, we can obtain a conservative approximation formulation of the problem, which can typically be further reformulated as a linear program. In order to efficiently solve the resulting large-scale linear program, we develop a column generation-based decomposition scheme and speed up the computational efficiency by exploiting a special column selection strategy and stopping early based on a Karush-Kuhn-Tucker condition test. Focusing on the Wasserstein ambiguity set and the event-wise mean absolute deviation set, a computational study demonstrates both the computational efficiency of the proposed algorithm, which significantly outperforms a commercial solver and a Benders decomposition method, and the out-of-sample superiority of distributionally robust solutions relative to their sample average approximation counterparts. History: Accepted by Nicola Secomandi, Area Editor for Stochastic Models & Reinforcement Learning. Funding: This work was supported by the Natural Sciences and Engineering Research Council of Canada [492997-2016, RGPIN-2016-05208], the National Natural Science Foundation of China [71972012], Alliance de recherche numérique du Canada, and Canada Research Chairs [CRC-2018-00105]. It was also supported by Groupe d'études et de recherche en analyse des décisions (GERAD). Finally, this research was enabled in part by support provided by Digital Research Alliance of Canada (https://alliancecan.ca/en). Supplemental Material: The software that supports the findings of this study is available within the paper and its supplemental information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0010) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0010). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In this paper, we study the knapsack problem with conflict pair constraints. After a thorough literature survey on the topic, our study focuses on the special case of bipartite conflict graphs. For complete bipartite (multipartite) conflict graphs, the problem is shown to be NP-hard but solvable in pseudo-polynomial time, and it admits an FPTAS. Extensions of these results to more general classes of graphs are also presented. Further, a class of integer programming models for the general knapsack problem with conflict pair constraints is presented, which generalizes and unifies the existing formulations. The strength of the LP relaxations of these formulations is analyzed, and we discuss different ways to tighten them. Experimental comparisons of these models are also presented to assess their relative strengths. This analysis disclosed various strong and weak points of different formulations of the problem and their relationships to different types of problem data. This information can be used in designing special purpose algorithms for KPCC involving a learning component. [ABSTRACT FROM AUTHOR]

We consider the multiple knapsack problem (KP) with setup (MKPS), which is an extension of the KP with setup (KPS). We propose a new solving approach denoted by LP&DP‐VNS that combines linear programming (LP) relaxation and dynamic programming (DP) to enhance variable neighborhood search (VNS). The LP&DP‐VNS is tailored to the characteristics of the MKPS and reduced to LP&DP to solve the KPS. The approach is tested on 200 KPS and 360 MKPS benchmark instances. Computational experiments show the effectiveness of the LP&DP‐VNS, compared to integer programming (using CPLEX) and the best state‐of‐the‐art algorithms. It reaches 299/342 optimal solutions and 316/318 best‐known solutions and provides 127 new best solutions. An additional computational study shows that the LP&DP‐VNS scales up extremely well, solving optimally and near‐optimally very large instances with up 200 families and 300,000 items in a reasonable amount of time. [ABSTRACT FROM AUTHOR]