Search

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]

Owing to the availability of high computing servers and clusters to process the data, factors such as data skewness, class imbalance, and scalability in big data cause slow processing performance. This study proposes a framework for load balancing in the Apache Spark cluster that makes efficient use of cluster resources and improves overall processing performance. The proposed method configures the Apache Spark cluster initially, to fix the optimal number of CPU cores and memory for each executor. The proposed scheme explores the trade-off between workload balance and communication efficiency, while for dynamic task allocation, coarse-grained and fine-grained data placement strategies are being used. A coarse-grained strategy handles the execution of datasets with larger partitions, but comparatively few executors, by transforming resilient distributed datasets (RDDs) into smaller datasets. Fine-grained strategy handles the execution of datasets with a large number of executors in comparison with partitions; the number of executors is considered equivalent to the number of knapsacks, and the resulting multidimensional knapsack problem is solved using particle swarm optimization to join the data partitions. The partitions were transformed into RDDs equivalent to the number of executors. All experiments were carried out using a large-scale dataset comprised of Amazon product reviews data in JSON format. The fine-grained and coarse-grained data placement strategies were found to be 26.12% and 42% faster in terms of execution time compared to the default data placement approach. [ABSTRACT FROM AUTHOR]

This paper studies an interval data min–max regret (IDMR) version of the packing-delivery problem, in which a 0-1 knapsack problem is for parcel packing and a capacitated travelling salesman problem is for parcel delivery. The parcel profits for the courier and the tour costs are uncertain and they can take any value from a specific interval with lower and upper bound values. The problem is how to select and deliver a subset of parcels to minimise the maximum regret of net profit which is the difference between the total profits of the selected parcels and the total delivery costs, to deal with the trade-off of the solution robustness and performance. To tackle the problem effectively, we first prove the worst-case scenario of a solution to the problem, based on which, a mixed integer linear programming is formulated. A Benders-like decomposition algorithm is then developed to solve small-scale problems to optimality within the manageable computation time. For medium- and large-scale problems, a simulated-annealing-based heuristic method with a local search procedure is designed. Extensive computational experiments show the efficiency and effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]

Honey Badger Algorithm (HBA) is one of the recently proposed optimization techniques inspired by the foraging behavior of honey badger. Although it has been successfully applied in solving continuous problems, the algorithm cannot be implemented directly in binary problems. A binary version of HBA is proposed in this study for the 0-1 Knapsack Problem (0-1 KP). To adapt the binary version of HBA, V- Shaped, S-Shaped, U-Shaped, T-Shaped, Tangent Sigmoid, O-Shaped, and Z-Shaped transfer functions are used. Each transfer function was tested by computational experiments over 25 instances of 0-1 KP and compared results. According to the results obtained, it was observed that O1 was the best TF among 25 TFs. In addition, the proposed algorithm was compared with three different binary variants, such as BPSO, MBPSO, and NGHS. Experimental results and comparison show that the proposed method is a promising and alternative algorithm for 0-1 KP problems. [ABSTRACT FROM AUTHOR]

We consider three new knapsack problems with variable weights or profits of items, where the weight or profit of an item depends on the position of the item in the sequence of items packed in the knapsack. We show how to solve the problems exactly using dynamic programming algorithms with pseudo-polynomial running times and propose fully polynomial-time approximation schemes for their approximate solution. [ABSTRACT FROM AUTHOR]

The field of Submodular Maximization subject to a Knapsack constraint has recently expanded to a variety of application domains, which is facing some challenges such as data explosions or additional conditions. There exist plenty of objective functions that cannot be evaluated exactly in many real cases unless they are estimated with errors. It leads to solving the problem under noise models. Somewhat surprisingly, Submodular Maximization subject to a Knapsack constraint under Noise models (S M K N) has never been discussed a lot before. Hence, in this paper, we consider the problem with two kinds of noise models which are addition and multiplication. Inspired by the traditional Greedy algorithm, we first propose a Greedy algorithm under Noises with provable theoretical bounds. In order to find the solution when input data are extremely large, we then devise an efficient streaming algorithm that scans only a single pass over the data and guarantees theoretical approximations. Finally, we conduct some experiments on Influence Maximization problem under knapsack constraint, an instance of S M K N to show the performances of the proposed algorithms. [ABSTRACT FROM AUTHOR]

With the rapid development of virtual reality (VR) technology, this paper proposes an access point (AP) correlation method based on VR user behavior awareness to address the problem of how current AP correlation methods only focus on the performance improvements of ordinary users and ignore the impact of VR user behavior on service quality. This paper analyzes the AP association method under the coverage scenario of a multi-access point (multi-AP) scenario environment and controls the performance improvement of VR user APs or APs under the access controller (AC) by association. Firstly, the VR network application scenario and system model were constructed, and secondly, the user behavior was sensed by analyzing the viewing habits of users. Then, the VR user association problem based on VR user behavior perception was transformed into a "many-to-many" matching problem between VR user devices and APs, and the generalized multidimensional multiple choice knapsack (GMMKP) model was established to solve the problem using the backpack problem theory; the suboptimal solution algorithm was selected to obtain the best VR user AP association strategy. The experimental results show by simulation that the proposed algorithm in this paper performed better in terms of the AP load balancing and average network download latency compared to the comparison algorithms. [ABSTRACT FROM AUTHOR]

Dynamic programming approach was designed in year 1950's by mathematician Richard Bellman. Dynamic programming approach works in bottom up fashion, it first divide the problem in small overlapped sub problems and then solve them starting from the smallest one and store the solution in a table. The main idea of dynamic programming is a recurrence relation which relates the solution of previous sub problems with the current instance of the problem. Step wise it increases the size of the problem and finally reached to original initial problem. 0/1 knapsack is one of the popular problem solved by using dynamic programming approach, this problem can be used to solve many problem like optimum job scheduling. strategy selection. resource allocation. policy making and many more. This paper presents one of such application of 0/1 knapsack problem in best strategics selection to optimize the objective achievements. [ABSTRACT FROM AUTHOR]

The multiple knapsack problem (0/1-mKP) is a valuable NP-hard problem involved in many science-and-engineering applications. In current research, there exist two main approaches: 1. the exact algorithms for the optimal solutions (i.e., branch-and-bound, dynamic programming (DP), etc.) and 2. the approximate algorithms in polynomial time (i.e., Genetic algorithm, swarm optimization, etc.). In the past, the exact-DP could find the optimal solutions of the 0/1-KP (one knapsack, n objects) in O(nC). For large n and massive C, the unbiased filtering was incorporated with the exact-DP to solve the 0/1-KP in O(n + C′) with 95% optimal solutions. For the complex 0/1-mKP (m knapsacks) in this study, we propose a novel research track with hybrid integration of DP-transformation (DPT), exact-fit (best) knapsack order (m!-to-m2 reduction), and robust unbiased filtering. First, the efficient DPT algorithm is proposed to find the optimal solutions for each knapsack in O([n2,nC]). Next, all knapsacks are fulfilled by the exact-fit (best) knapsack order in O(m2[n2,nC]) over O(m![n2,nC]) while retaining at least 99% optimal solutions as m! orders. Finally, robust unbiased filtering is incorporated to solve the 0/1-mKP in O(m2n). In experiments, our efficient 0/1-mKP reduction confirmed 99% optimal solutions on random and benchmark datasets (n δ 10,000, m δ 100). [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]

Solving binary-real problems with bio-inspired algorithms is an active research matter. However, the efficiency of the employed algorithm varies drastically by tailoring the governing equations or just by adopting “more adequate” parameter setting. Within this framework, we aim to improve the parameter setting of the binary particle swarm optimization (BPSO). We derive a Markov chain model of BPSO. The transition probabilities reveal that the acceleration coefficients control the transition speed between the exploitation and exploration phases. The transition probabilities also depict a poor exploration ratio in high-dimensional search spaces. Increasing the values of the acceleration coefficients may enhance the exploration ratio. Nevertheless, overly high values for these coefficients present some shortcomings. Numerical experiments realized on three different problem sets (e.g. multidimensional knapsack problem) further prove the need to increase the acceleration coefficients as the search space dimension rises. We recommend a set of equations governing the best setting for acceleration coefficients. Finally, a comparison with other BPSO variants reveals the merits of the suggested setting over the conventional ones. [ABSTRACT FROM AUTHOR]

Population-based approaches have given us new search strategies and ideas in order to solve optimization problems. Usually, these methods are based on the performance carried out by a finite number of agents, which by the interaction between them they evolve and work all over the search space. Also, it is well-known that the correct employment of parameter values in this kind of method can positively impact their performance and behavior. In this context, the present work focuses on the design of a hybrid architecture which smartly balances the population size on run-time. In order to smartly balance and control the population size, a modular approach, named Linear Modular Population Balancer (LMPB), is proposed. The main ideas behind the designed architecture include the solving strategy behind a population-based metaheuristic, the influence of learning components based on multiple statistical modeling methods which transform the dynamic data generated into knowledge, and the possibilities to tackle both discrete and continuous optimization problems. In this regard, three modules are proposed for LMPB, which concern tasks such as the management of the population-based algorithm, parameter setting, probabilities, learning methods, and selection mechanism for the population size to employ. In order to test the viability and effectiveness of our proposed approach, we solve a set of well-known benchmark functions and the multidimensional knapsack problem (MKP). Additionally, we illustrate promising solving results, compare them against state-of-the-art methods which have proved to be good options for solving optimization problems, and give solid arguments for future work in the necessity to keep evolving this type of proposed architecture. [ABSTRACT FROM AUTHOR]

The Knapsack Sharing Problem (KSP) is the problem of assigning a subset of n items from m disjoint classes to a shared knapsack such that the total profit of the smallest class is maximized subject to the knapsack capacity constraint. The KSP problem generalizes the 0/1 Knapsack Problem (KP), and it has wide applications in finance and resource allocation domains. In this article, we describe a new Dichotomous-based exact algorithm, called Sharknap, to solve large knapsack sharing problems. Sharknap solves the KSP problem by decomposition and dichotomous reduction like all existing Dichotomous-based algorithms. The decomposition phase splits each KSP instance into a series of KP problems to be solved using an exact KP solver. The dichotomous reduction phase reduces the weight of each considered class. We introduce the concept of critical class to bound the number of calls to the KP solver and to speed up the search algorithm. Experimental results on standard benchmarks from the literature as well as on randomly generated instances show that Sharknap significantly outperforms all existing exact algorithms. Interestingly, the new algorithm is able to solve large instances with up to 100000 items and 1000 classes within less than one second in many times. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variant of adaptive robust combinatorial optimization problems where the decision maker can prepare K solutions and choose the best among them upon knowledge of the true data realizations. We suppose that the uncertainty may affect the objective and the constraints through functions that are not necessarily linear. We propose a new exact algorithm for solving these problems when the feasible set of the nominal optimization problem does not contain too many good solutions. Our algorithm enumerates these good solutions, generates dynamically a set of scenarios from the uncertainty set, and assigns the solutions to the generated scenarios using a vertex p-center formulation, solved by a binary search algorithm. Our numerical results on adaptive shortest path and knapsack with conflicts problems show that our algorithm compares favorably with the methods proposed in the literature. We additionally propose a heuristic extension of our method to handle problems where it is prohibitive to enumerate all good solutions. This heuristic is shown to provide good solutions within a reasonable solution time limit on the adaptive knapsack with conflicts problem. Finally, we illustrate how our approach handles nonlinear functions on an all-or-nothing subset problem taken from the literature. Summary of Contribution: Our paper describes a new exact algorithm for solving adaptive robust combinatorial optimization problems when the feasible set of the nominal optimization problems does not contain too many good solutions. Its development relies on a progressive relaxation of the problem augmented with a row-and-column generation technique. Its efficient execution requires a reformulation of this progressive relaxation, coupled with dominance rules and a binary search algorithm. The proposed algorithm is amenable to exploiting the special structures of the problems considered as illustrated with various applications throughout the paper. A practical view is provided by the proposition of a heuristic variant. Our computational experiments show that our proposed exact solution method outperforms the existing methodologies and therefore pushes the computational envelope for the class of problems considered. [ABSTRACT FROM AUTHOR]

In this article, we consider a network of agents that has to self-assign a set of tasks while respecting resource constraints. One possible formulation is the generalized assignment problem, where the goal is to find a maximum payoff while satisfying capability constraints. We propose a purely distributed branch-and-price algorithm to solve this problem in a cooperative fashion. Inspired by classical (centralized) branch-and-price schemes, in the proposed algorithm, each agent locally solves small linear programs, generates columns by solving simple knapsack problems, and communicates to its neighbors a fixed number of basic columns. We prove finite-time convergence of the algorithm to an optimal solution of the problem. Then, we apply the proposed scheme to a generalized assignment scenario, in which a team of robots has to serve a set of tasks. We implement the proposed algorithm in a Robot Operating System testbed and provide experiments for a team of heterogeneous robots solving the assignment problem. [ABSTRACT FROM AUTHOR]

Knapsack problem with a single continuous variable (KPC) is a natural generalization of the standard 0-1 knapsack problem. In KPC, the capacity of the knapsack is not fixed, so it becomes more difficult to solve. In order to overcome the shortcoming that the performance of existing differential evolution (DE) algorithm is not good enough on highdimensional KPC instances, this paper proposes Lamarckian evolution-based DE (LEDE) algorithm to solve KPC. The improvement generated by the greedy repair and optimization operator is inherited to the offspring, which can speed up the convergence speed of DE algorithm and improve the precision of DE algorithm on high-dimensional KPC instances. At the same time, a profit-based greedy optimization strategy is introduced in the greedy repair and optimization operator to optimize the feasible solution generated by greedy repair strategy based on profit weight ratio, so as to help the algorithm jump out of local optimum. The LEDE algorithm is experimentally analyzed on 40 KPC instances. The experimental results show that the Lamarckian evolution and the profit-based greedy optimization strategy can improve the exploitation ability of LEDE algorithm, and LEDE algorithm is better than other intelligent optimization algorithms in terms of obtaining the best solution and the mean solution. [ABSTRACT FROM AUTHOR]

An important generalization of the classic 0-1 knapsack problem is the multi-demand multidimensional knapsack problem (MDMKP). In addition to being theoretically difficult to solve (it is NP-hard), it can be in practice difficult to solve because of its conflicting knapsack and demand constraints. Since there are significant large-scale applications of the MDMKP, approximate solution approaches are commonly used to solve these problems. However, using 1620 MDMKPs discussed in the literature, this article demonstrates which types of large MDMKPs can be solved efficiently by operations research practitioners using general purpose integer programming software on a standard personal computer within 0.1% of optimum. Statistical analyses are used to determine which problem parameters significantly impact solution time. Finally, based on these 1620 MDMKP instances, a classification tree is generated. This tree can be used to guide practitioners in solving MDMKPs that arise in business and industry. [ABSTRACT FROM AUTHOR]

Summary: Knapsack is a combinatorial optimization problem that involves a variety of resource allocation challenges. It is defined as non‐deterministic polynomial time (NP) hard and has a wide range of applications. Knapsack problem (KP) has been studied in applied mathematics and computer science for decades. Many algorithms that can be classified as exact or approximate solutions have been proposed. Under the category of exact solutions, algorithms such as branch‐and‐bound and dynamic programming and the approaches obtained by combining these algorithms can be classified. Due to the fact that exact solutions require a long processing time, many approximate methods have been introduced for knapsack solution. In this research, deep Q‐learning using models containing fully connected layers, attention, and transformer as function estimators were used to provide the solution for KP. We observed that deep Q‐networks, which continued their training by observing the reward signals provided by the knapsack environment we developed, optimized the total reward gained over time. The results showed that our approaches give near‐optimum solutions and work about 40 times faster than an exact algorithm using dynamic programming. [ABSTRACT FROM AUTHOR]

Compared to fuzzy utility itemset mining (FUIM), temporal fuzzy utility itemset mining (TFUIM) has been proposed and paid attention to in recent years. It considers the characteristics of transaction time, sold quantities of items, unit profit, and transformed semantic terms as essential factors. In the past, a tree-structure method with two phases was previously presented to solve this problem. However, it spent much time because of the number of candidates generated. This paper thus proposes a one-phase tree-structure method to find the high temporal fuzzy utility itemsets in a temporal database. The tree was designed to maintain candidate 1-itemsets with their upper bound values meeting the defined threshold constraint. Besides, each node in this tree keeps the required data of a 1-itemset for mining. We also designed an algorithm to construct the tree and gave an example to illustrate the mining process in detail. Computational experiments were conducted to demonstrate the one-phase tree-structure method is better than the previous one regarding the execution time on three real datasets. [ABSTRACT FROM AUTHOR]

In recent years, numerous studies have been conducted regarding inventory control of deteriorating items. However, due to the complexity of the solution methods, various real assumptions such as discrete variables and capacity constraints were neglected. In this study, we presented a multi-item inventory model for deteriorating items with limited carrier capacity. The proposed research considered the carrier, which transports the order has limited capacity and the quantity of orders cannot be infinite. Dynamic programming is used for problem optimization. The results show that the proposed solution method can solve the mixed-integer problem, and it can provide the global optimum solution. [ABSTRACT FROM AUTHOR]

This article proposes a novel binary version of recently developed Gaining Sharing knowledge-based optimization algorithm (GSK) to solve binary optimization problems. GSK algorithm is based on the concept of how humans acquire and share knowledge during their life span. A binary version of GSK named novel binary Gaining Sharing knowledge-based optimization algorithm (NBGSK) depends on mainly two binary stages: binary junior gaining sharing stage and binary senior gaining sharing stage with knowledge factor 1. These two stages enable NBGSK for exploring and exploitation of the search space efficiently and effectively to solve problems in binary space. Moreover, to enhance the performance of NBGSK and prevent the solutions from trapping into local optima, NBGSK with population size reduction (PR-NBGSK) is introduced. It decreases the population size gradually with a linear function. The proposed NBGSK and PR-NBGSK applied to set of knapsack instances with small and large dimensions, which shows that NBGSK and PR-NBGSK are more efficient and effective in terms of convergence, robustness, and accuracy. [ABSTRACT FROM AUTHOR]

Dynamic Programming is an algorithm or method in solving complex problems by describing how to solve them in several stages by dividing the problem into simpler problems. So that each stage of completion is related to each other until a final solution is produced. The Knapsack problem is a combinatorial problem, which is given a set of items, each of which has a weight and value. Knapsack solution using Dynamic Programming does not always get optimal results. [ABSTRACT FROM AUTHOR]

Knapsack problems (KPs) are famous combinatorial optimization problems that can be solved by evolutionary algorithms (EAs). In such methods, a key step is to produce new solutions for each generation. However, traditional EAs cannot guarantee the feasibility of the new solutions, causing ineffectiveness or inefficiency of the methods. Owing to the fact that directly generating a feasible solution is difficult, a practical way is to generate a potential solution and transform it to a feasible one if necessary; more ideally, transform it to the local-optimal solution. Essentially, this transforming process is to map an element of the solution set to an element of the feasible solution set, which can be analyzed and optimized from a new perspective, i.e., the set theory (ST). In this article, we provide new explanations for the transforming process of solutions based on ST and summarize the properties that the transforming process should satisfy. Furthermore, based on the proposed concepts and theories, we put forward the ideas for improving the transforming process. Consequently, some new operators for KPs are proposed. Experimental results demonstrate the superiority of the proposed operators. [ABSTRACT FROM AUTHOR]

Recent years have witnessed a growing interest in automatic learning mechanisms and applications. The concept of hyper-heuristics, algorithms that either select among existing algorithms or generate new ones, holds high relevance in this matter. Current research suggests that, under certain circumstances, hyper-heuristics outperform single heuristics when evaluated in isolation. When hyper-heuristics are selected among existing algorithms, they map problem states into suitable solvers. Unfortunately, identifying the features that accurately describe the problem state—and thus allow for a proper mapping—requires plenty of domain-specific knowledge, which is not always available. This work proposes a simple yet effective hyper-heuristic model that does not rely on problem features to produce such a mapping. The model defines a fixed sequence of heuristics that improves the solving process of knapsack problems. This research comprises an analysis of feature-independent hyper-heuristic performance under different learning conditions and different problem sets. [ABSTRACT FROM AUTHOR]

Compared with the stable states of the ground networks, the space-ground integrated networks (SGIN) have limited resources, high transmission delay, and vulnerable topology, which make traditional caching strategies unable to adapt to the complex space network environment. An intelligent and efficient caching strategy is required to improve the edge service capabilities of satellites. Therefore, we investigate these problems in this paper and make the following contributions. First, the content value evaluation model based on classification and regression tree is proposed to solve the problem of "what to cache" by describing the cache value of content, which considers the multidimensional content characteristics. Second, we propose a cache decision strategy based on the node caching cost model to answer "where to cache." This strategy modified the genetic algorithm to adapt the 0-1 knapsack problem under SDN architecture, which greatly improved the cache hit rate and the network service quality. Finally, we propose a cache replacement strategy by establishing an effective service time model between the satellite and ground transmission link, which solves the problem of "when to replace." Numerical results demonstrate that the proposed strategy in SGIN can improve the nodes' cache hit rate and reduce the network transmission delay and transmission hops. [ABSTRACT FROM AUTHOR]

We propose a dead-end control algorithm for the exact solution of NP-hard combinatorial optimization problems. The efficiency of the algorithm is demonstrated by examples of solving the set-partition and 0-1 knapsack problems. The paper also shows that the use of the idea of dead-end controls when implementing the dynamic programming method can considerably reduce the number of problem state variables at each optimization step. A comparative analysis of the proposed method with known algorithms for solving these problems is carried out. [ABSTRACT FROM AUTHOR]

Due to the problem of high link load of edge cache and small storage space of edge server, a caching architecture by the collaborative of edge nodes and the cloud server is proposed. The content cache location is designed and optimized, which can be the content provider, cloud server (CS), and edge node (EN). In the proposed system, cloud servers collaborate with edge servers and the performance of content caching can be improved by coordinating caching on the cloud server or caching on the edge server. In this paper, a cloud-edge collaborative caching model based on the greedy algorithm is proposed, which includes the content caching model and collaborative caching model. Network architecture, file popularity estimation, link capacity, and other factors are considered in the model. Correspondingly, a cloud-edge collaborative cache algorithm based on a greedy algorithm is proposed. The related optimization problem is decomposed into the knapsack problem of cache layout in each layer, and then the greedy algorithm is used to solve the knapsack problem of cache placement and cooperative cache proposed in this paper. The affiliation between CS cache and EN caches in the layered architecture is improved and recognized. In the experimental results, the link load is reduced, the cache hit rate is improved by using the proposed method of edge caching, and it also has obvious advantages in the average end-to-end service delay. [ABSTRACT FROM AUTHOR]

The retail sector is an extremely competitive area. One of the most important facets of retailing is managing retail shelf space. In a market place, retailers should offer customers an option of selecting not only the product but also the packaging size and purchasing quantity. In such instances, product prices often differ. This paper investigates a retail shelf-space allocation problem that maximizes the overall planogram profit. The common shelf-space allocation problem was simplified in this research by selecting the shelf on which the items would be placed in advance. This is explained by practical reasons as sometimes retailers assign the products of the specific package, type, brand, price, form or size, weight to the specific shelf. The problem has been formulated as a 0-1 bounded knapsack problem. Exact methods for solving such kinds of a problem include dynamic programming algorithm. We proposed dynamic programming, which could solve the problem using less time and computational resources. The developed dynamic programming could be applied for solving shelf-space allocation problem subproblems or as being a part of other heuristics and metaheuristics approaches. The results of the research are important for the retailers, category managers, and scientists focused on shelf-space allocation or shelf-space optimization problems. [ABSTRACT FROM AUTHOR]

This research proposes and analyzes new models for a stochastic resource allocation problem that arises in a variety of operations contexts. One of the primary contributions of the paper lies in providing a succinct, robust, and general model that can address a range of different risk-based objectives and cost assumptions under uncertainty. Although the model expression is relatively simple, it embeds a reasonably high degree of underlying complexity, as the analysis shows. In addition, in-depth analysis of the model, both in its general form and under various specific risk measures, uncovers some interesting and powerful insights regarding the problem trade-offs. Furthermore, this analysis leads to a highly efficient class of heuristic algorithms for solving the problem, which we demonstrate via numerical experimentation to provide close-to-optimal solutions. This computational benefit is a critical element for solving a class of broadly applicable larger problems for which our problem arises as a subproblem that requires repeated solution. This paper considers a single-resource allocation problem for multiple items with random, independent resource consumption values, known as the static stochastic knapsack problem (SSKP). Whereas the existing SSKP literature generally assumes a risk-neutral objective using an expected value approach, such an approach can maximize expected profit while admitting the possibility of very high losses in some unfavorable scenarios. Because of this, we consider two popular risk measures, conditional value-at-risk (CVaR) and a mean-standard deviation trade-off, in order to address risk within this problem class. Optimizing the trade-offs associated with these risk measures presents significant modeling and computational challenges. To address these challenges, we first provide mixed-integer linear programming models using a scenario-based approach, which can be exploited to provide exact solutions for discrete distributions. For general distributions, a sample average approximation method provides approximate solutions. We then propose a general mixed integer nonlinear optimization modeling approach for the special case of normally distributed resource requirements. This modeling approach incorporates a new class of normalized penalty functions that account for both the expected costs and risks associated with uncertainty, and it can be specialized to a broad class of risk measures, including CVaR and mean-standard deviation. Our results characterize key optimality properties for the associated continuous relaxation of the proposed general model and provide insights on valuable rank-ordering mechanisms for items with uncertain resource needs under different risk measures. For this broadly applicable case, we present a class of efficient and high-performing asymptotically optimal heuristic methods based on these optimality conditions. An extensive numerical study evaluates the efficiency and quality of the proposed solution methods, identifies optimal item selection strategies, and examines the sensitivity of the solution to varying levels of risk, excess weight penalty values, and knapsack capacity values. Summary of Contribution: This research proposes and analyzes new models for a stochastic resource allocation problem that arises in a variety of operations contexts. One of the primary contributions of the paper lies in providing a succinct, robust, and general model that can address a range of different risk-based objectives and cost assumptions under uncertainty. While the model expression is relatively simple, it embeds a reasonably high degree of underlying complexity, as the analysis shows. In addition, in-depth analysis of the model, both in its general form and under various specific risk measures, uncovers some interesting and powerful insights regarding the problem tradeoffs. Furthermore, this analysis leads to a highly efficient class of heuristic algorithms for solving the problem, which we demonstrate via numerical experimentation to provide close-to-optimal solutions. This computational benefit is a critical element for solving a class of broadly applicable larger problems for which our problem arises as a subproblem that requires repeated solution. [ABSTRACT FROM AUTHOR]

The paper is devoted to an emerging trend in modern automation of production - collaborative multi-agent systems – characterized by the simultaneous use of the labor of people and robots in a single system in the framework of solving the target problem. The need in collaborative multi-agent systems is due to the fact that the industrial use of fully automated multicomponent systems is limited by the financial and infrastructural unavailability of various industries to switch to completely unmanned technologies. The article discusses the issue of the effectiveness of applying this approach as an alternative to full robotization of production. A multi-criteria assessment of the effectiveness of collaborative multi-agent systems as optimization knapsack problem is formulated. A multicriteria genetic algorithm based on the principle of small variations of the basic solution is presented for the solution of the stated problem. The resulting Pareto set is constructed according to the rank of possible solutions. [ABSTRACT FROM AUTHOR]

Various multicriteria sorting methods have been proposed in the literature to assign the feasible alternatives into predefined categories. We consider here problems involving a set of totally ordered categories representing different achievement levels in the satisfaction of criteria. As in many existing methods, the assignment rule of an alternative to a category is based on the comparison of its performance vector to reference profiles defining lower bounds of the categories. Within this standard setting we address a new problem that consists in finding how to modify a given solution, within a combinatorial set of alternatives, to upgrade it in the upper category (or higher) at minimum cost. We also consider the problem of identifying the sequence of solutions that minimize the total cost while satisfying some budget constraint at every step, and the problem of determining how to modify the current solution to save money while staying in the same category. We first propose a general approach based on mixed integer (linear or quadratic) programming to solve these problems. Then, we implement this approach on various multiobjective combinatorial problems, such as multi‐agent assignment problems and multiobjective knapsack problems. Numerical tests are provided to establish the feasibility of the approach on instances of different sizes. [ABSTRACT FROM AUTHOR]

In this paper we introduce the Ameso optimization problem, a special class of discrete optimization problems. We establish its basic properties and investigate the relation between Ameso optimization and the convex optimization. Further, we design an algorithm to solve a multi-dimensional Ameso problem by solving a sequence of one-dimensional Ameso problems. Finally, we demonstrate how the knapsack problem can be solved using the Ameso optimization framework. [ABSTRACT FROM AUTHOR]

The theory of inverse location involves modifying parameters in such a way that the total cost is minimized and one/several prespecified facilities become optimal based on these perturbed parameters. When the modifying parameters are grouped into sets, with each group's cost measured under the rectilinear norm and the overall cost measured under the Chebyshev norm, the resulting problem is known as the max-sum inverse location problem. This paper addresses the max-sum inverse median location problem on trees with a budget constraint, where the objective is to modify the vertex weights so that a specified vertex becomes a 1-median, while minimizing the max-sum objective within the available budget. To solve this problem, a uni-variable optimization problem is first induced, where the objective function for each specified value of the variable can be obtained through a continuous knapsack problem. Leveraging the monotonicity of the cost function, a combinatorial algorithm is developed, which solves the problem in O (n log ⁡ n) time, where n denotes the number of vertices present in the tree. • We address the max-sum inverse median location problem on trees. • We reformulate the problem as a univariate optimization problem. • The objective of the induced optimization problem is a piecewise linear monotone function. • A combinatorial algorithm is developed to solve the problem in O (n log ⁡ n) time. [ABSTRACT FROM AUTHOR]

Definitive optimization algorithms are not able to solve high-dimensional optimization problems because the search space grows exponentially with the problem size and an exhaustive search will be impractical. Therefore, approximate algorithms are applied to solve them. A category of approximate algorithms are meta-heuristic algorithms. They have shown an acceptable efficiency to solve these problems. Among them, particle swarm optimization (PSO) is one of the well-known swarm intelligence algorithms to optimize continuous problems. A transfer function is applied in this algorithm to convert the continuous search space to the binary one. The role of the transfer function in binary PSO (BPSO) is very important to enhance its performance. Several transfer functions have been proposed for BPSO such as S-shaped, V-shaped, linear and other transfer functions. However, BPSO algorithm can sometimes find local optima or show slow convergence speed in some problems because of using the velocity of PSO and these transfer functions. In this study, a novel transfer function called x-shaped BPSO (XBPSO) is proposed to increase exploration and exploitation of BPSO in the binary search space. The transfer function uses two functions and improved rules to generate a new binary solution. The proposed method has been run on 33 benchmark instances of the 0–1 multidimensional knapsack problem (MKP), two discrete maximization functions and 23 minimization functions. The results have been compared with some well-known BPSO and discrete meta-heuristic algorithms. The results showed that x-shaped transfer function considerably increased the solution accuracy and convergence speed in BPSO algorithm. The average error of compared algorithms on all 0–1 MKP benchmark instances indicated that XBPSO has the minimum error of 8.9%. Also, the mean absolute error (MAE) obtained by XBPSO on two discrete maximization functions is 0.45. Moreover, the proposed transfer function provides superior solutions in 18 functions from 23 minimization functions. [ABSTRACT FROM AUTHOR]

When solving large-scale multiobjective optimization problems, solvers can get stuck because of memory and/or time limitations. In such cases, one is left with no information on the distance to the best feasible solution, found before the optimization process has stopped, to the true Pareto optimal solution. In this work, we show how to provide such information. To this aim we make use of the concept of lower shells and upper shells, developed in our earlier works. No specific assumptions about the problems to be solved are made. We illustrate the proposed approach on biobjective multidimensional knapsack problems derived from single-objective multidimensional knapsack problems in the Beasley OR Library. We address cases when a top-class commercial mixed-integer linear solver fails to provide Pareto optimal solutions attempted to be derived by scalarization. [ABSTRACT FROM AUTHOR]

This study focuses on the maximization of the minimum completion time using identical parallel processors. The objective of this maximization is to ensure fair distribution. A set of processes is to be scheduled to several identical parallel processors, and this problem is proved as NP-hard. The research for this paper is based primarily on the performance of the proposed heuristics with other methods cited in the literature review. Our heuristics are developed mainly using the randomization method and the iterative utilization of the knapsack problem to solve the above-mentioned problem. The heuristics are assessed by several instances represented in the experimental results. The results shew that the knapsack-based heuristic provides a performance that is almost like the heuristic in the literature review but with better running time. [ABSTRACT FROM AUTHOR]

Traditionally, in the bilevel optimization framework, a leader chooses her actions by solving an upper-level problem, assuming that a follower chooses an optimal reaction by solving a lower-level problem. However, in many settings, the lower-level problems might be nontrivial, thus requiring the use of tailored algorithms for their solution. More importantly, in practice, such problems might be inexactly solved by heuristics and approximation algorithms. Motivated by this consideration, we study a broad class of bilevel optimization problems where the follower might not optimally react to the leader's actions. In particular, we present a modeling framework in which the leader considers that the follower might use one of a number of known algorithms to solve the lower-level problem, either approximately or heuristically. Thus, the leader can hedge against the follower's use of suboptimal solutions. We provide algorithmic implementations of the framework for a class of nonlinear bilevel knapsack problem (BKP), and we illustrate the potential impact of incorporating this realistic feature through numerical experiments in the context of defender-attacker problems. [ABSTRACT FROM AUTHOR]

Featured Application: An uncorrelated instance is equivalent to solving any problem where the benefit is independent of the weight. A weakly correlated instance has a high correlation between the benefit and the weight of each element. Typically, the benefit differs from the weight by a small percentage. Such instances are the most practical in administration, such as with a return on an investment, which is generally proportional to the sum of the amount invested. This paper presents a process that is based on sets of parts, where elements are fixed and removed to form different binary branch-and-bound (BB) trees, which in turn are used to build a parallel algorithm called "multi-BB". These sequential and parallel algorithms calculate the exact solution for the 0–1 knapsack problem. The sequential algorithm solves the instances published by other researchers (and the proposals by Pisinger) to solve the not-so-complex (uncorrelated) class and some problems of the medium-complex (weakly correlated) class. The parallel algorithm solves the problems that cannot be solved with the sequential algorithm of the weakly correlated class in a cluster of multicore processors. The multi-branch-and-bound algorithms obtained parallel efficiencies of approximately 75%, but in some cases, it was possible to obtain a superlinear speedup. [ABSTRACT FROM AUTHOR]

This paper addresses one of the key operational decision problems in the steel industry which is related to the allocation of orders to stock materials in the surplus inventory. The meta slab allocation problem can be stated as the 'multi-stage multiple knapsack problem' where the problem is to design slabs using orders with similar properties (the first stage) and allocating these designed slabs into the existing meta slabs in the inventory yard (the second stage). The objective of the problem is to maximise the allocated order weights in slabs and meta slabs. For the given problem, we propose a column generation algorithm, where a column in the master problem represents meta slabs and the sub problem is to design 'bins', here slabs with the given orders. The sub problem itself also becomes a multiple knapsack problem and we proposed a practical set-partitioning heuristic. The proposed algorithm was tested with daily operation data given from an integrated steel company in the Asia Pacific. The computational results showed that the proposed heuristic solved the real instances pretty well. The proposed algorithm was successfully deployed to the integrated steel mill. [ABSTRACT FROM AUTHOR]

The knapsack problem with Boolean variables and a single constraint is studied. In the general case, this problem is NP-hard; for this reason, its exact solution requires the use of various search algorithms with the decomposition of the set of feasible solutions and computation of estimates of the objective function. Combinatorial formulas for computing and estimating the value of the objective function in various cases depending on the set of given parameters of the problem are derived. The case when the coefficients of the constraint vector coincide with the coefficients of the objective function is considered. The relationship between the set of solutions of the problem and threshold functions of a certain type is revealed. The coefficients of the objective function, the coefficients of the constraint vector, and the knapsack size are used as parameters. The classical method of generating functions is used as the basic technique. The results obtained in this paper can be used, in particular, for estimating the complexity of search and decomposition methods of solving the problem and for developing such methods as auxiliary procedures. [ABSTRACT FROM AUTHOR]

The generalized birthday problem (GBP) was introduced by Wagner in 2002 and has shown to have many applications in cryptanalysis. In its typical variant, we are given access to a function H : { 0 , 1 } ℓ → { 0 , 1 } n (whose specification depends on the underlying problem) and an integer K > 0 . The goal is to find K distinct inputs to H (denoted by { x i } i = 1 K ) such that ∑ i = 1 K H (x i) = 0 . Wagner's K-tree algorithm solves the problem in time and memory complexities of about N 1 / (⌊ log K ⌋ + 1) (where N = 2 n ). In this paper, we improve the best known GBP time-memory tradeoff curve (published independently by Nikolić and Sasaki and also by Biryukov and Khovratovich) for all K ≥ 8 from T 2 M ⌊ log K ⌋ - 1 = N to T ⌈ (log K) / 2 ⌉ + 1 M ⌊ (log K) / 2 ⌋ = N , applicable for a large range of parameters. We further consider values of K which are not powers of 2 and show that in many cases even more efficient time-memory tradeoff curves can be obtained. Finally, we optimize our techniques for several concrete GBP instances and show how to solve some of them with improved time and memory complexities compared to the state-of-the-art. Our results are obtained using a framework that combines several algorithmic techniques such as variants of the Schroeppel–Shamir algorithm for solving knapsack problems (devised in works by Howgrave-Graham and Joux and by Becker, Coron and Joux) and dissection algorithms (published by Dinur, Dunkelman, Keller and Shamir). [ABSTRACT FROM AUTHOR]

Copyright of Umm Al-Qura University Journal of Engineering & Architecture (Association of Arab Universities) is the property of Association of Arab Universities 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.)

A new scheme of approximate lexicographic search is proposed for the solution of the multidimensional Boolean knapsack problem. The main idea of the algorithm is to gradually define the lexicographic order (ordering of variables) in which “qualitative” solutions of the problem belong to a direct two-sided lexicographic constraint whose upper bound is the lexicographic maximum of the set of feasible solutions of the problem in this order. Since the search for “qualitative” solutions in each order is carried out on a bounded lexicographic interval, the proposed algorithm is called a bounded lexicographic search. The quality of the approximate method of bounded lexicographic search is investigated by solving test tasks from the well-known Beasley and Glover-Kochenberger sets. [ABSTRACT FROM AUTHOR]

We propose a method for finding approximate solutions to multiple-choice knapsack problems. To this aim we transform the multiple-choice knapsack problem into a bi-objective optimization problem whose solution set contains solutions of the original multiple-choice knapsack problem. The method relies on solving a series of suitably defined linearly scalarized bi-objective problems. The novelty which makes the method attractive from the computational point of view is that we are able to solve explicitly those linearly scalarized bi-objective problems with the help of the closed-form formulae. The method is computationally analyzed on a set of large-scale problem instances (test problems) of two categories: uncorrelated and weakly correlated. Computational results show that after solving, in average 10 scalarized bi-objective problems, the optimal value of the original knapsack problem is approximated with the accuracy comparable to the accuracies obtained by the greedy algorithm and an exact algorithm. More importantly, the respective approximate solution to the original knapsack problem (for which the approximate optimal value is attained) can be found without resorting to the dynamic programming. In the test problems, the number of multiple-choice constraints ranges up to hundreds with hundreds variables in each constraint. [ABSTRACT FROM AUTHOR]