Search

The study of non-submodular maximization on the integer lattice is an important extension of submodular optimization. In this paper, streaming algorithms for maximizing non-negative monotone non-submodular functions with knapsack constraint on integer lattice are considered. We first design a two-pass StreamingKnapsack algorithm combining with BinarySearch as a subroutine for this problem. By introducing the DR ratio γ and the weak DR ratio γ w of the non-submodular objective function, we obtain that the approximation ratio is min ⁡ { γ 2 (1 − ε) / 2 γ + 1 , 1 − 1 / γ w 2 γ − ε } , the total memory complexity is O (K log ⁡ K / ε) , and the total query complexity for each element is O (log ⁡ K log ⁡ (K / ε 2) / ε). Then, we design a one-pass streaming algorithm by dynamically updating the maximal function value among unit vectors along with the currently arriving element. Finally, in order to decrease the memory complexity, we design an improved StreamingKnapsack algorithm and reduce the memory complexity to O (K / ε 2). • A two-pass streaming algorithm is proposed for maximizing monotone non-submodular functions with knapsack constraint on integer lattice. • By introducing DR ratio γ d (weak DR ratio γ w) we obtain the approximation ratio as min ⁡ { γ 2 (1 − ε) / 2 γ + 1 , 1 − 1 / γ w 2 γ − ε } with memory O (K log ⁡ K / ε). • A one-pass streaming algorithm is designed by dynamically updating the maximal function value among unit vectors. • We design an improve StreamingKnapsack algorithm and reduce the memory complexity to O (K / ε 2). [ABSTRACT FROM AUTHOR]

Many optimization algorithms have been applied to solve high-dimensional instances of the 0-1 knapsack problem. However, these algorithms often fall into a local optimization trap and thus fail to obtain the global optimal solutions. To circumvent this shortcoming, a hybrid harmony search algorithm with distribution estimation is proposed in this paper. A few important features of the proposed algorithm are as follows: (i) the idea of probability distribution estimation is employed to design the adaptive search strategy, (ii) a fixed improvisation process is presented to improve the algorithm searching ability, (iii) a new method of initialization is used to ensure that the initialization is feasible harmony and (iv) an improved remediation approach is proposed to effectively repair the infeasible solutions. To assess the effectiveness of the proposed algorithm, some experiments are carried out. The experimental results reveal that the proposed algorithm is a reliable and promising alternative for solving the 0-1 knapsack problem. [ABSTRACT FROM AUTHOR]

While the classical knapsack problem has been the object to be solved by optimization algorithm proposals for many years, another version of this problem, discounted {0-1} knapsack problem, is gaining a lot of attention recently. The original knapsack problem requires selecting specific items from an item set to maximize the total benefit while ensuring that the total weight does not exceed the knapsack capacity. Meanwhile, discounted {0-1} knapsack problem has more stringent requirements in which items are divided into groups, and only up to one item from a particular group can be selected. This constraint, which does not exist in the original knapsack problem, makes discounted {0-1} knapsack problem even more challenging. In this paper, we propose a new algorithm based on salp swarm algorithm in the form of four different variants to resolve the discounted {0-1} knapsack problem. In addition, we also make use of an effective data modeling mechanism and a greedy repair operator that helps overcome local optima when finding the global optimal solution. Experimental and statistical results show that our algorithm is superior to currently available algorithms in terms of solution quality, convergence, and other statistical criteria. [ABSTRACT FROM AUTHOR]

خؽارزمية عذيخة الدخقاط )MCA )ىي خؽارزمية )metaheuristic )قائمة عمى الطبيعة والتي تحاكي عمى خخيطة ً ا عمى خؽارزمية عذيخة ميخكات بناء ً الدمؽك الحكي لحيؽان الدخقاط. تقجم ىحه الؽرقة تحدين فؽضؽية واستخاتيجية التقاطع )CC-MCA .)تعمل ىاتان االستخاتيجيتان عمى زيادة تنؽيع وتكثيف الخؽارزمية المقتخحة وتعديد القجرة عمى البحث إليجاد المديج مؼ الحمؽل عالية الجؽدة. تػ حل مذكمة حقيبة العيخ 0-1 بؽاسطة MCA األساسي والندخة المحدنة مؼ ىحه نة ّ الخؽارزمية المحد CC-MCA .تػ اختبار أداء ىحه الخؽارزميات عمى مدائل ذات أبعاد منخفضة وعالية. أظيخت النتائج التجخيبية أن الخؽارزمية المقتخحة تغمبت عمى الخؽارزمية األساسية مؼ حيث جؽدة الحل وسخعتو واكتدبت األمثمية مع مذاكل األبعاد المنخفضة. عالوة عمى ذلغ ، في مذاكل األبعاد العالية ، ليا نتائج تنافدية مقارنة بالخؽارزميات األخخى. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

• The 0-1 knapsack problem (KP01) is one of the classic variants of knapsack problems in which the aim is to select the items with the total profit to be in the knapsack. • In this paper, a comprehensive survey on the recent advances in 0-1 knapsack problem is presented. • Literature survey reveals some interesting challenges and future research directions. 0-1 knapsack problem (KP01) is one of the classic variants of knapsack problems in which the aim is to select the items with the total profit to be in the knapsack. In contrast, the constraint of the maximum capacity of the knapsack is satisfied. KP01 has many applications in real-world complex problems such as resource distribution, portfolio optimization, etc. This study reviews the basic theory and main algorithms of 0-1 knapsack, proposes many different types of nature-inspired metaheuristic algorithms, and divides existing 0-1 knapsack problems into 6 types according to the different coding methods of the algorithms, for a comprehensive overview of it. In this paper, a comprehensive survey on the recent advances in 0-1 knapsack problem is presented. Literature survey reveals some interesting challenges and future research directions. [ABSTRACT FROM AUTHOR]

The knapsack problem arises in several real-world applications, like manufacturing systems, transportation, cutting and packing, and hydrological studies. In this paper, we investigate the use of an iterative rounding strategy-based algorithm for tackling a special knapsack problem: the set-union knapsack problem. First, the approach builds a series of starting partial solutions by using the principle of fractional values related to a series of linear relaxations of the (sub)instance at hand. Second, each step of the rounding procedure is coupled with an enhanced local search procedure, where its goal is to search around a local partial solution by applying the so-called critical element tailored for the problem studied. Third, both degrading and re-optimization strategies are introduced in order to extend the diversified search space. Finally, all strategies are embedded into an iterative search in order to augmenting the quality of the solutions. The performance of the proposed method is evaluated on benchmark instances of the literature and new large-scale instances; its provided results are compared to those reached by the Cplex solver and the best methods available in the literature. The method seems competitive, where it is able to achieve new (lower) bounds and matches the rest of the bounds. [ABSTRACT FROM AUTHOR]

Person re-identification (Re-ID) across multi-camera views remains a very challenging task. In fact, the use of global convolutional neural network (CNN) features is not optimal since the appearance similarity of identities is overlooked. Hence, persons with similar global appearance (wearing in very similar clothes) may be confused and hard to distinguish. To address these shared challenges, some attribute labels (such as hat or bag) can improve the discriminative ability of Re-ID model by depicting person images with more detailed descriptions. Hence, we propose in this paper a new attributes recognition model, called ARN, based on a deep CNN model. Then, we propose a new approach based on attributes similarity and k-reciprocal re-ranking algorithm in order to enhance person Re-ID baseline performances. The proposed approach, called K-RNNA, is motivated first of all, by the potential of re-ranking methods to resort the 'baseline' re-identification results from the initial retrieval. Second, attributes, as a mid-level semantic representation of the person's local appearance, could also potentially resolve these challenges. In fact, learned semantic attributes such as gender, hair, accessories (hat, bags, backpack, etc.) are used as a supplement during the re-ranking phase in order to discriminate between identities with similar global appearance. The experimental study conducted on Market-1501, Duke-MTMC-reID and CUHK03 datasets confirms that when attributes are used as supplement in the verification phase, we improve considerably the person Re-ID performances and we reach competitive results in terms of mean average precision (mAP) and Rank-1. [ABSTRACT FROM AUTHOR]

We explore the benefits of multivariable branching schemes for linear-programming-based branch-and-bound algorithms for the 0-1 knapsack problem—that is, the benefits of branching on sets of variables rather than on a single variable (the current default in integer-programming solvers). We present examples where multivariable branching has advantages over single-variable branching and partially characterize situations in which this happens. Chvátal shows that for a specific class of 0-1 knapsack instances, a linear-programming-based branch-and-bound algorithm (employing a single-variable branching scheme) must explore exponentially many nodes. We show that for this class of 0-1 knapsack instances, a linear-programming-based branch-and-bound algorithm employing an appropriately chosen multivariable branching scheme explores either three or seven nodes. Finally, we investigate the performance of various multivariable branching schemes for 0-1 knapsack instances computationally and demonstrate their potential; the multivariable branching schemes explored result in smaller search trees (some in search trees that are an order of magnitude smaller), and some also result in shorter solution times. Summary of Contribution: As a powerful modeling tool, mixed-integer programming (MIP) is ubiquitous in Operations Research and is usually solved via the branch-and-bound framework. However, solving MIPs is computationally challenging in general, where branching affects the performance of solvers dramatically. In this paper, we explore the benefits of branching on multiple variables, which can be viewed as a generalization of the standard single-variable branching. We analyze its theoretical behavior on a special instance introduced by Chvátal, which is proved to be hard for single-variable branching. We also partially characterize situations in which branching on multiple variables is superior to its single-variable counterpart. Lastly, we demonstrate its potential in reducing the overall computational time and possible memory usage for storing unexplored nodes through numerical experiments on 0-1 knapsack problems. [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]

In the ETL system, when the data generation speed encounters large fluctuations, in order to make the existing resources meet the user ' s needs to a great extent under limited conditions, this paper proposed an ETL flexible scheduling mechanism based on resource urgency. First, it built a time series prediction model based on historical data to predict the speed of data generation. Then, according to the resource list each ETL process submits and the load of each server, it adjusted the resources of multiple ETL processes for a single user. This scheduling mechanism turned resource scheduling problem into a multi-dimensional knapsack problem, and proposed urgency based dynamic schedule algorithm. Experimental results show that when user's resources are scarce for all ETL processes, the proposed scheduling algorithm makes better use. The experiments verify that the flexible scheduling has advantages over the traditional scheduling method in resource utilization. [ABSTRACT FROM AUTHOR]

We consider robust combinatorial optimization problems with cost uncertainty where the decision maker can prepare K solutions beforehand and chooses the best of them once the true cost is revealed. Also known as min–max–min robustness (a special case of K -adaptability), it is a viable alternative to otherwise intractable two-stage problems. The uncertainty set assumed in this paper considers that in any scenario, at most Γ of the components of the cost vectors will be higher than expected, which corresponds to the extreme points of the budgeted uncertainty set. While the classical min–max problem with budgeted uncertainty is essentially as easy as the underlying deterministic problem, it turns out that the min–max–min problem is NP - hard for many easy combinatorial optimization problems, and not approximable in general. We thus present an integer programming formulation for solving the problem through a row-and-column generation algorithm. While exact, this algorithm can only cope with small problems, so we present two additional heuristics leveraging the structure of budgeted uncertainty. We compare our row-and-column generation algorithm and our heuristics on min-knapsack and shortest path instances previously used in the scientific literature and find that the heuristics obtain good quality solutions in short computational times. [ABSTRACT FROM AUTHOR]

In the multidimensional multiple choice knapsack problem (MMKP), items with nonnegative profits are partitioned into groups. Each item consumes a predefined nonnegative amount of a set of resources with given availability. The problem looks for a subset of items consisting of exactly one item for each group that maximizes the overall profit without violating the resource constraints. The MMKP is among the most complex problems in the knapsack family. In the literature, although a plethora of heuristic approaches have been proposed, very few exact methods can be found, and all of them work only on limited size instances. In this paper, we propose a new exact approach for the problem. The method exactly solves subproblems of increasing size by means of a recursive variable-fixing process until an optimality condition is satisfied. The algorithm has several properties. Memory requirement remains almost constant during computation, and the method is general enough to be easily adapted to other knapsack problems. Finally, it can be converted at no cost into a heuristic approach. We close to optimality 10 open benchmark instances and improve the best-known values for many of the remaining ones. Interesting enough, our algorithm is able to find, within three minutes, better solutions than the ones found by Gurobi in one hour. [ABSTRACT FROM AUTHOR]

A Packing problem consists in the best arrangement of several objects inside a bounded area named as the container. This arrangement must fulfill with technological constraints, for example, objects should not be overlapping. Some packing models for circular objects are typically formulated as non-convex optimization problems; where the continuous variables are the coordinates of the objects, so they are limited to not finding optimal solutions. Due to the combinatorial nature in the arrangement of such objects, heuristic methods are being used extensively which combine methods of global search and methods of local exhaustive search of local minima or their approximations. In this paper, we will address the packing problem for non-congruent (different size) circles with the binary version of the monkey algorithm which incorporates a cooperation process and a greedy strategy. We use a rectangular grid for covering the container. Every node in the grid represent potential positions for a circle. In this sense, binary monkey algorithm for the knapsack problem, can be used to solve de 0–1 approximate packing problem for non-congruet circles. The binary monkey problem uses two additional processes of the original monkey algorithm, these two processes are a greedy process and a cooperation processes. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.363 - ε) -approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4 - ε) -approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and ε . [ABSTRACT FROM AUTHOR]

In order to overcome the shortcomings of the basic bat algorithm, such as easy to fall into local optimum and slow convergence speed, the optimization study was carried out. This paper proposed a new hybrid bat algorithm based on the original features, framework of the basic bat algorithm and specific characteristics of the 0- 1 knapsack problem. The hybrid algorithm introduced the crossover mechanism of the genetic algorithm and the inverse operator to construct a brand-new location transfer method and local search rule. The greedy strategy was added to make the solution feasible and fully utilized, enhancing the local search ability and speeding up the convergence. This hybrid bat algorithm was applied to two sets of 0-1 knapsack cases. The simulation results exceeded adaptive cellular particle swarm optimization, basic bat algorithm and greedy binary bat algorithm. The results verify the feasibility and effectiveness of the hybrid algorithm in solving 0-1 knapsack problem. [ABSTRACT FROM AUTHOR]

Service-oriented architecture (SOA) has emerged as a flexible software design style. SOA focuses on the development, use, and reuse of small, self-contained, independent blocks of code called web services that communicate over the network to perform a certain set of simple tasks. Web services are integrated as composite services to offer complex tasks and to provide the expected services and behavior in addition to fulfilling the clients' requests according to the service-level agreement (SLA). Web service selection and composition problems have been a significant area of research to provide the expected quality of service (QoS) and to meet the clients' expectations. This research paper presents a hybrid web service composition model to solve web service selection and composition problems and to optimize web services' resource utilization using k-means clustering and knapsack algorithms. The proposed model aims to maximize the service compositions' QoS and minimize the number of web services integrated within the service composition using the knapsack algorithm. Additionally, this paper aims to track the service compositions' QoS attributes by evaluating and tracking the web services' QoS using the reward function and, accordingly, use the k-means algorithm to decide to which cluster the web service belongs. The experimental results on a real dataset show the superiority and effectiveness of the proposed algorithm in comparison with the results of the state–action–reward–state–action (SARSA) and multistage forward search (MFS) algorithms. The experimental results show that the proposed model reduces the average time of the web service selection and composition processes to 37.02 s in comparison to 47.03 s for the SARSA algorithm and 42.72 s for the MFS algorithm. Furthermore, the average of web services' resource utilization results increased by 4.68% using the proposed model in comparison to the resource utilization by the SARSA and MFS algorithms. In addition, the experimental results showed that the average number of service compositions using the proposed model improved by 26.04% compared with the SARSA and MFS algorithms. [ABSTRACT FROM AUTHOR]

Due to its broad applications, maximizing a diminishing return submodular function with a knapsack constraint has been extensively studied recently. In the paper, we mainly consider this problem on the integer lattice. Assuming the optimal value is known, we first design a one-pass algorithm and prove that its approximation ratio is (1 / 3 − ɛ). Observing the difficult of actually knowing the optimal value, we design a streaming algorithm with two passes, where in the first round we find the maximum value of the unit vector to estimate the range of the OPT. Furthermore, in order to improve the performance of the algorithm, we design an online algorithm called DynamicMRT to reduce the number of rounds, eventually achieving an approximation ratio (1 / 3 − ɛ) , a memory complexity O (K log K ∖ ε) and query complexity O (log 2 K ∖ ε) per element for the knapsack constraint K. [Display omitted] • Maximizing a diminishing return submodular function over the integer lattice. • Design streaming algorithm for diminishing return submodular maximization. • Space complexity is related to the knapsack constraint. • The query number of per-element is related to the knapsack constraint. [ABSTRACT FROM AUTHOR]

In this paper, the bi-objective quadratic multiple knapsack problem is tackled with a hybrid population-based method. The proposed method starts by computing two reference solutions, where a specialized powerful mono-objective algorithm is used. From both reference solutions, a starting population is built by using a series of perturbations around the solutions. Next, the so-called non-sorting genetic process is combined with a new drop/rebuild operator for generating a series of populations till converging toward an approximate Pareto front with high density. The performance of the hybrid population based algorithm (namely HBPA) is evaluated on a set of benchmark instances of the literature containing both medium and large-scale instances. Its provided results are compared to those achieved by the best methods available in the literature. Encouraging results have been obtained. • A hybrid method is designed for the multi-objective quadratic multiple knapsack. • The diversity is maintained with a learning strategy. • The method is analyzed on instances of the literature. • It reaches new dominated solutions with high approximate Pareto fronts. [ABSTRACT FROM AUTHOR]

• This paper studies the knapsack problem with setups. • This paper presents an algorithm based on a Lagrangean relaxation of the problem. • We used very large data sets to test the algorithm. • The algorithm can solve near optimally the problem in reasonable amount of time. We consider the knapsack problem with setups which is a generalization of the classical knapsack problem where the items belong to families and an item can be placed in the knapsack only if its family is selected. The problem has received increasing attention by researchers because of its theoretical significance and practical applications related to resource allocation. This paper presents an algorithm based on a Lagrangean relaxation of the problem that produces solutions whose quality can be assessed automatically with the algorithm itself without ever knowing the optimal solutions. We report results of an extensive computational study which show that the method can solve near optimally very large instances of the problem with up to 500 families and 2,000,000 items in reasonable amount of time. This study shows the merit of using the Lagrangean relaxation method to solve the current problem when the constraints to relax are chosen properly. [ABSTRACT FROM AUTHOR]

• An improved QCCEA (called MSQCCEA) algorithm with multi-strategy is proposed. • Rrandom rotation direction strategy can avoid local optimum and realize solution space search. • Hamming adaptive rotation angle strategy can improve global search ability and convergence speed. • An airport gate allocation multi-objective optimization model is established. • An airport gate allocation optimization method based on the MSQCCEA is proposed. In order to overcome the slow convergence speed, poor global search ability and difficult designing rotation angle of quantum-inspired evolutionary algorithm (QEA), an improved quantum-inspired cooperative co-evolution algorithm based on combining the strategies of cooperative co-evolution, random rotation direction and Hamming adaptive rotation angle, namely MSQCCEA is proposed, which is employed to propose a new airport gate allocation optimization method in this paper. In the proposed MSQCCEA, the cooperative co-evolution strategy is used to improve the global search capability. The random rotation direction strategy is developed to change the quantum evolution direction from one to two in order to avoid local optimal solution and realize the full search of the solution space. A new Hamming adaptive rotation angle strategy is designed to enable individuals to adaptively adjust the rotation angle according to the difference degree between the individual and the target individual, so as to improve the global search ability and convergence speed. A new airport gate allocation optimization method using MSQCCEA is realized to effectively allocate airport gates to the flights. Finally, the knapsack problem and the actual airport gate allocation problem are used to verify the effectiveness of the proposed MSQCCEA and gate allocation optimization method, respectively. The comparison experiment results demonstrate that the proposed MSQCCEA has faster convergence speed and higher convergence accuracy, and the proposed gate allocation optimization method takes on great potential to make decisions for actual airport management. [ABSTRACT FROM AUTHOR]

In this paper, we propose a penalized gradient projection algorithm for solving the continuous convex separable knapsack problem, which is simpler than existing methods and competitive in practice. The algorithm only performs function and gradient evaluations, sums, and updates of parameters. The relatively complex task of the algorithm, which consists in minimizing a function in a compact set, is given by a closed formula. The convergence of the algorithm is presented. Moreover, to demonstrate its efficiency, illustrative computational results are presented for medium-sized problems. [ABSTRACT FROM AUTHOR]

• New "Anytime" Framework for Automatic Algorithm Selection. • Application of the Anytime Automatic Algorithm Selection Framework to Knapsack. • 3 Machine Learning Models proposed for the Problem. • Knapsack Instances, Features and Solvers Behavior publicly available. In this paper, we present a new approach for Automatic Algorithm Selection. In this new procedure, we feed the predictor of the best algorithm choice with a runtime limit for the solvers. Hence, the machine learning model should consider and learn from the Anytime Behavior of the solvers, together with features characterizing each instance. For this purpose, we propose a general Framework and apply it to the Knapsack problem. Thus, we created a large and diverse dataset of 15 , 000 instances, recorded the anytime behavior of 8 solvers on them and trained and tested three machine learning strategies, collecting the results for different machine learning algorithms. Our results show that, for the majority of the tuples < instance, time > , the solver that computes the best objective value can be predicted. We also make this data publicly available, as a challenge for the community to work in this problem and propose new and better machine learning models and solvers. [ABSTRACT FROM AUTHOR]