Search

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]

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]

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]

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]

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.)

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]

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]

Multi-objective evolutionary algorithms (MOEAs) are a practical tool to solve non-linear problems with multiple objective functions. However, when applied to expensive black-box scenario-based optimization problems, MOEA's performance becomes constrained due to computational or time limitations. Scenario-based optimization refers to problems that are subject to uncertainty, where each solution is evaluated over an ensemble of scenarios to reduce risks. A primary reason for MOEA's failure is that algorithm development is challenging in these cases as many of these problems are black-box, high-dimensional, discrete, and computationally expensive. For this reason, this paper proposes a benchmark generator to create fast-to-compute scenario-based discrete test problems with different degrees of complexity. Our framework uses the structure of the Multi-Objective Knapsack Problem to create test problems that simulate characteristics of expensive scenario-based discrete problems. To validate our proposition, we tested four state-of-the-art MOEAs in 30 test instances generated with our framework, and the empirical results demonstrate that the suggested benchmark generator can analyze the ability of MOEAs in tackling expensive scenario-based discrete optimization problems. [ABSTRACT FROM AUTHOR]

The quadratic knapsack problem (QKP) is a variant of the well-known knapsack problem and arises in a variety of real life applications. The quadratic knapsack problem with conflict graphs (QKPCG) further extends QKP by considering the conflicts of items. In this work, we propose an effective hybrid search method based on the framework of memetic algorithm to tackle QKPCG. The method integrates a randomized uniform-based crossover operator to generate promising offspring solutions, a multi-neighborhood tabu search to perform local optimization, and a streamline technique to speed up the evaluation of candidate solutions. The method shows a competitive performance compared to the state-of-the-art approaches in the literature. It finds 3 improved best-known solutions and matches the best-known solutions for all the remaining cases out of the 45 benchmark instances. We investigate the effects of the key ingredients of the algorithm. [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]

This paper studies a framework of Reliable Capacitated Facility Location Problem with Single source constraint, which allows us to capture the mental account management problem for a bank under uncertain environment. In the problem, each facility, corresponding to a financial product, has limited capacity and may fail randomly, which represents that the product fails to reach the threshold level of return. Each customer, corresponding to a mental account, is served by a single primary facility or product, and its demands, or the setting goals, can be split on several backup facilities or alternative investments with redundant capacity. With the operation, a portion of the satisfaction can still be met by the backup facilities when the primary service of a customer fails. We formulate a mixed integer programming model for the problem and design a Lagrangian relaxation based solution algorithm, which sophisticatedly exploits the structure of the model and transfers the complicated relaxation problems into 0–1 knapsack problems to reduce the complexity. A local search procedure is also incorporated into the algorithm to enhance the accuracy of small- and large-scale computation. Finally, a real-life case of mental accounting is investigated to illustrate the application of the decision model. [ABSTRACT FROM AUTHOR]

Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation. However, the solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large. In order to deal with this issue, we propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits. We analyze the performance of this method on two problems, the knapsack problem and the traveling salesman problem. Our results show the advantages of this method, that balances the number of steps that the algorithm has to make with the amount of error in the solution found by the quantum hardware that the user is willing to risk. The results are obtained using the commercially available quantum hardware D-Wave Advantage, and they outline the strategy for a practical application of the quantum annealers. [ABSTRACT FROM AUTHOR]

In this paper, we describe a neural network‐based application that recommends multiple items using dialog context input and simultaneously outputs a response sentence. Further, we describe a multi‐item recommendation by specifying it as a set of clothing recommendations. For this, a multimodal fusion approach that can process both cloth‐related text and images is required. We also examine achieving the requirements of downstream models using a pretrained language model. Moreover, we propose a gate‐based multimodal fusion and multiprompt learning based on a pretrained language model. Specifically, we propose an automatic evaluation technique to solve the one‐to‐many mapping problem of multi‐item recommendations. A fashion‐domain multimodal dataset based on Koreans is constructed and tested. Various experimental environment settings are verified using an automatic evaluation method. The results show that our proposed method can be used to obtain confidence scores for multi‐item recommendation results, which is different from traditional accuracy evaluation. [ABSTRACT FROM AUTHOR]

We study the two-dimensional geometric knapsack problem for convex polygons. Given a set of weighted convex polygons and a square knapsack, the goal is to select the most profitable subset of the given polygons that fits non-overlappingly into the knapsack. We allow to rotate the polygons by arbitrary angles. We present a quasi-polynomial time O(1)-approximation algorithm for the general case and a pseudopolynomial time O(1)-approximation algorithm if all input polygons are triangles, both assuming polynomially bounded integral input data. Additionally, we give a quasi-polynomial time algorithm that computes a solution of optimal weight under resource augmentation—that is, we allow to increase the size of the knapsack by a factor of 1+δ for some δ > 0 but compare ourselves with the optimal solution for the original knapsack. To the best of our knowledge, these are the first results for two-dimensional geometric knapsack in which the input objects are more general than axis-parallel rectangles or circles and in which the input polygons can be rotated by arbitrary angles. [ABSTRACT FROM AUTHOR]

This article uses an integrated approach to solve real-world problems in three areas, namely singlemachine scheduling, 1-center location on networks and nonrenewable allocation problems. Jobs are stored at vertices and a single machine will be placed in the network. Each job receives an allocation that comes with a specific cost from an expected limited budget. Processing times of jobs are considered continuous functions of the allocation variables multiplied by costs, while release dates are defined as distances from job locations to the machine. We call this problem the scheduling-location problem with job allocation. The goal is to find a location on networks and an allocation to minimize a scheduling objective, makespan. We first consider the problem at a fixed location and propose a combinatorial algorithm that repeatedly solves continuous knapsack problems and runs in quadratic time. Concerning the original problem, we explore some properties of the objective function and develop a polynomial time algorithm to solve it. [ABSTRACT FROM AUTHOR]

This paper examines the performance of three binary metaheuristic algorithms when applied to two distinct knapsack problems (0–1 knapsack problems (KP01) and multidimensional knapsack problems (MKP)). These binary algorithms are based on the classical mantis search algorithm (MSA), the classical quadratic interpolation optimization (QIO) method, and the well-known differential evolution (DE). Because these algorithms were designed for continuous optimization problems, they could not be used directly to solve binary knapsack problems. As a result, the V-shaped and S-shaped transfer functions are used to propose binary variants of these algorithms, such as binary differential evolution (BDE), binary quadratic interpolation optimization (BQIO), and binary mantis search algorithm (BMSA). These binary variants are evaluated using various high-dimensional KP01 examples and compared to several classical metaheuristic techniques to determine their efficacy. To enhance the performance of those binary algorithms, they are combined with repair operator 2 (RO2) to offer better hybrid variants, namely HMSA, HQIO, and HDE. Those hybrid algorithms are evaluated using several medium- and large-scale KP01 and MKP instances, as well as compared to other hybrid algorithms, to demonstrate their effectiveness. This comparison is conducted using three performance metrics: average fitness value, Friedman mean rank, and computational cost. The experimental findings demonstrate that HQIO is a strong alternative for solving KP01 and MKP. In addition, the proposed algorithms are applied to the Merkle-Hellman Knapsack Cryptosystem and the resource allocation problem in adaptive multimedia systems (AMS) to illustrate their effectiveness when applied to optimize those real applications. The experimental findings illustrate that the proposed HQIO is a strong alternative for handling various knapsack-based applications.

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]

This research proposes an optimisation model for identifying the optimal locations and sizes of public charging stations for large‐scale areas based on geographic information system (GIS) data and grid partitioning. A grid partitioning technique is utilised to generate subareas and investigate the demand for electric vehicle (EV) chargers calculated based on the number of EVs in each subarea. The optimal locations are formulated as a maximum covering location problem and solved by integer programming to ensure that all vehicle access subareas, according to the GIS data, are covered by charging stations. The sizes of charging stations are formulated as a knapsack problem and solved by the EV‐charge point ratio to guarantee each subarea has the appropriate number of chargers. The Voronoi diagram is integrated to estimate vehicle density and improve visualisation. The model is extended to include potential power loss reduction by adjusting the distribution of chargers in relation to the proximity to electrical substations. The developed methodology has been implemented by the whole country area of Thailand, which covers an area of approximately 510,000 km2. The study results are represented in a map blueprint that is very useful in strategic planning to support the so‐called EV30@30 government policy's ambitious national target of 2,050,000 units of EVs in 2030. [ABSTRACT FROM AUTHOR]

Travel times in real-world transportation networks are affected by many disruptions. When we conduct the network design optimization, the traffic condition and its resulting travel time variability should be taken into account. However, most of the previous network design optimizations adopted the lengths or expected travel times of links. Based on travel time means and standard deviations, we develop an arc-based model that is a nonlinear and concave integer program. By the Dantzig-Wolfe reformulation, we transform it into an equivalent column-based model that is an integer linear program with a large number of variables. Based on the column-based model, we develop a hybrid method based on column generation and Lagrangian relaxation. The restricted master problem can be settled by the linear programming solvers. The pricing subproblems incorporate independent reliable shortest path problems and a knapsack problem. In numerical experiments, the proposed method can generate feasible solutions with good integrality gaps. [ABSTRACT FROM AUTHOR]

To effectively address large-scale optimization problems, this paper proposes an evolutionary dynamic grouping (EDG) based cooperative co-evolution (CC) algorithm. In the proposed algorithm, a novel decomposition method is designed to generate the sub-components of decision variables dynamically. Additionally, an evolutionary search method based on the fireworks search strategy is proposed to enhance the searchability of the algorithm. The performance of the proposed algorithm is assessed using two benchmark suites, IEEE CEC'2010 and IEEE CEC'2013, as well as a real-world optimization problem, the 0/1 Knapsack Problem (KP). Experimental results demonstrate that the proposed algorithm achieves competitive results when compared with other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Maintenance planning of low volume rural road network is a challenging task due to its large length and importance to the concerned habitation. The proposed methodology is focused on developing a cost-effective maintenance plan for low volume rural Himalayan hill roads by considering the predominant distresses and factors. Maximizing overall network pavement condition rating while minimizing the budget is taken as the objective function in the optimization problem. The maintenance plan is optimized using Knapsack modified Genetic Algorithm technique developed in MATLAB. Validation of the proposed model was done by applying it to a case study of 42 low volume rural hill roads of Hamirpur district of Himachal Pradesh state in India, located in the Himalayan region. Knapsack modified GA makes maintenance planning easier by considering different scenarios of budgetary limitations varying from 0 to 100% of total need. The present model can be very helpful for pavement maintenance planners in developing an optimized cost-effective maintenance program in developing countries where budget limitation is a big concern. [ABSTRACT FROM AUTHOR]

In this paper, we study the classic submodular maximization problem subject to a group equality constraint under both nonadaptive and adaptive settings. It is shown that the utility function of many machine learning applications, including data summarization, influence maximization in social networks, and personalized recommendation, satisfies the property of submodularity. Hence, maximizing a submodular function subject to various constraints can be found at the heart of many of those applications. On a high level, submodular maximization aims to select a group of most representative items (e.g., data points). However, the design of most existing algorithms does not incorporate the fairness constraint, leading to underrepresentation or overrepresentation of some particular groups. This motivates us to study the submodular maximization problem with group equality, in which we aim to select a group of items to maximize a (possibly nonmonotone) submodular utility function subject to a group equality constraint. To this end, we develop the first constant-factor approximation algorithm for this problem. The design of our algorithm is robust enough to be extended to solving the submodular maximization problem under a more complicated adaptive setting. Moreover, we further extend our study to incorporating a global cardinality constraint and other fairness notations. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0384. [ABSTRACT FROM AUTHOR]

Recent estimates indicate that there are over a million runaway and homeless youth and young adults (RHY) in the United States (US). Exposure to trauma, violence, and substance abuse, coupled with a lack of community support services, puts homeless youth at high risk of being exploited and trafficked. Although access to safe housing and supportive services such as physical and mental healthcare is an effective response to the vulnerability of RHY towards being trafficked, the number of youth experiencing homelessness exceeds the capacity of available housing resources in most US communities. We undertake a RHY-informed, systematic, and data-driven approach to project the collective capacity required by service providers to adequately meet the needs of RHY in New York City, including those most at risk of being trafficked. Our approach involves an integer linear programming model that extends the multiple multidimensional knapsack problem and is informed by partnerships with key stakeholders. The mathematical model allows for time-dependent allocation and capacity expansion, while incorporating stochastic youth arrivals and length of stays, services provided in a periodic fashion, and service delivery time windows. Our RHY and service provider-centered approach is an important step toward meeting the actual, rather than presumed, survival needs of vulnerable youth. [ABSTRACT FROM AUTHOR]

Evaluating the treatment effect has become an important topic for many applications. However, most existing literature focuses mainly on average treatment effects. When the individual effects are heavy tailed or have outlier values, not only may the average effect not be appropriate for summarizing treatment effects, but also the conventional inference for it can be sensitive and possibly invalid due to poor large-sample approximations. In this paper we focus on quantiles of individual treatment effects, which can be more robust in the presence of extreme individual effects. Moreover, our inference for them is purely randomization based, avoiding any distributional assumptions on the units. We first consider inference in stratified randomized experiments, extending the recent work by Caughey et al. (2021). We show that the computation of valid p -values for testing null hypotheses on quantiles of individual effects can be transformed into instances of the multiple-choice knapsack problem, which can be efficiently solved exactly or slightly conservatively. We then extend our approach to matched observational studies and propose a sensitivity analysis to investigate to what extent our inference on quantiles of individual effects is robust to unmeasured confounding. The proposed randomization inference and sensitivity analysis are simul- taneously valid for all quantiles of individual effects, noting that the analysis for the maximum or minimum individual effect coincides with the conventional analysis assuming constant treatment effects. [ABSTRACT FROM AUTHOR]

The evolution of the smart grid has enabled residential users to manage the ever-growing energy demand in an efficient manner. The smart grid plays an important role in managing this huge energy demand of residential households. A home energy management system enhances the efficiency of the energy infrastructure of smart homes and provides an opportunity for residential users to optimize their energy consumption. Smart homes contribute significantly to reducing electricity consumption costs by scheduling domestic appliances effectively. This residential appliance scheduling problem is the motivation to find an optimal appliance schedule for users that could balance the load profile of the home and helps in minimizing electricity cost (EC) and peak-to-average ratio (PAR). In this paper, we have focused on appliance scheduling on the consumer side. Two novel home energy management models are proposed using multiple scheduling options. The residential appliance scheduling problem is formulated using the multiple knapsack technique. Serial and parallel scheduling algorithms of home appliances namely MKSI (Multiple knapsacks with serial implementation) and MKPI (Multiple knapsacks with parallel implementation) are proposed to reduce electricity cost and PAR. Price-based demand response techniques are incorporated to shift appliances from peak hours to off-peak hours to optimize energy consumption. The proposed algorithms are tested on real-time datasets and evaluated based on time of use pricing tariff and critical peak pricing. The performance of both the algorithms is compared with the unscheduled scenario and existing algorithm. Simulations show that both proposed algorithms are efficient methods for home energy management to minimize PAR and electricity bills of consumers. The proposed MKSI algorithm achieves cost reduction of 20.26% and 42.53% for TOU and CPP, respectively as compared to the unscheduled scenario while PAR is reduced by 45.07% and 39.51% for TOU and CPP, respectively. The proposed MKPI algorithm achieves 22.33% and 46.36% cost reduction compared to the unscheduled case for TOU and CPP while the PAR ratio is reduced by 46.47% and 41.16% for TOU and CPP respectively. [ABSTRACT FROM AUTHOR]

The average-case complexity of a branch-and-bound algorithm for Min Dominating Set problem in random graphs in the G (n , p) model is studied. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes. [ABSTRACT FROM AUTHOR]

Reversible data hiding is a confidential communication technique that takes advantage of image file characteristics, which allows us to hide sensitive data in image files. In this paper, we propose a novel high-fidelity reversible data hiding scheme. Based on the advantage of the multipredictor mechanism, we combine two effective prediction schemes to improve prediction accuracy. In addition, the multihistogram technique is utilized to further improve the image quality of the stego image. Moreover, a model of the grouped knapsack problem is used to speed up the search for the suitable embedding bin in each sub-histogram. Experimental results show that the quality of the stego image of our scheme outperforms state-of-the-art schemes in most cases. [ABSTRACT FROM AUTHOR]

Fog Radio Access Network (F-RAN) has emerged as a promising architecture to reduce latency and network congestion by caching popular content at the edge. However, optimizing caching strategies in F-RAN faces challenges due to limited storage capacity and global vs. local content popularity. This paper proposes a novel proactive caching placement strategy using queueing theory to minimize latency. Specifically, we formulate an integer linear program based on a queuing model that captures content popularity and service rates. To solve this problem efficiently, we design two low-complexity heuristic algorithms: (1) An improved greedy algorithm that prioritizes globally popular content; and (2) A knapsack algorithm that optimizes cache allocation based on localized content popularity. Extensive simulations demonstrate that our proposed strategy achieves lower average latency and traffic cost compared to baseline caching schemes like LRU, LFU, and random replacement. The key innovation lies in optimizing caching decisions based on joint modeling of queuing delays and localized content popularity. This work provides an effective proactive caching framework for latency-critical F-RAN applications. [ABSTRACT FROM AUTHOR]

Federated learning (FL) has been proposed as a privacy-preserving distributed learning paradigm, which differs from traditional distributed learning in two main aspects: the systems heterogeneity, meaning that clients participating in training have significant differences in systems performance including CPU frequency, dataset size, and transmission power, and the statistical heterogeneity, indicating that the data distribution among clients exhibits Non-Independent Identical Distribution. Therefore, the random selection of clients will significantly reduce the training efficiency of FL. In this article, we propose a client selection mechanism considering both systems and statistical heterogeneity, which aims to improve the time-to-accuracy performance by trading off the impact of systems performance differences and data distribution differences among the clients on training efficiency. First, client selection is formulated as a combinatorial optimization problem that jointly optimizes systems and statistical performance. Then, we generalize it to a submodular maximization problem with knapsack constraint, and propose the Iterative Greedy with Partial Enumeration (IGPE) algorithm to greedily select the suitable clients. Then, the approximation ratio of IGPE is analyzed theoretically. Extensive experiments verify that the time-to-accuracy performance of the IGPE algorithm outperforms other compared algorithms in a variety of heterogeneous environments. [ABSTRACT FROM AUTHOR]

Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type max { c ⊤ x : A x = b , x ∈ Z ≥ 0 n } , where all the entries of A, b, c are integer, parameterized by the number of rows of A and ‖ A ‖ max . This class of problems is known under the name of ILP problems in the standard form, adding the word "bounded" if x ≤ u , for some integer vector u. Recently, many new sparsity, proximity, and complexity results were obtained for bounded and unbounded ILP problems in the standard form. In this paper, we consider ILP problems in the canonical form max { c ⊤ x : b l ≤ A x ≤ b r , x ∈ Z n } , where b l and b r are integer vectors. We assume that the integer matrix A has the rank n, (n + m) rows, n columns, and parameterize the problem by m and Δ (A) , where Δ (A) is the maximum of n × n sub-determinants of A, taken in the absolute value. We show that any ILP problem in the standard form can be polynomially reduced to some ILP problem in the canonical form, preserving m and Δ (A) , but the reverse reduction is not always possible. More precisely, we define the class of generalized ILP problems in the standard form, which includes an additional group constraint, and prove the equivalence to ILP problems in the canonical form. We generalize known sparsity, proximity, and complexity bounds for ILP problems in the canonical form. Additionally, sometimes, we strengthen previously known results for ILP problems in the canonical form, and, sometimes, we give shorter proofs. Finally, we consider the special cases of m ∈ { 0 , 1 } . By this way, we give specialised sparsity, proximity, and complexity bounds for the problems on simplices, Knapsack problems and Subset-Sum problems. [ABSTRACT FROM AUTHOR]