Search

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]

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]

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]

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]

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]

Abstract SARS‐CoV‐2 epidemic (severe acute respiratory corona virus 2 syndromes) has caused major impacts on a global scale. Several countries, including India, Europe, U.S.A., introduced a full state/nation lockdown to minimise the disease transmission through human interaction after the virus entered the population and to minimise the loss of human life. Millions of people have gone unemployed due to lockdown implementation, resulting in business and industry closure and leading to a national economic slowdown. Therefore, preventing the spread of the COVID‐19 virus in the world while also preserving the global economy is an essential problem requiring an effective and immediate solution. Using the compartmental epidemiology S, E, I, R or D (Susceptible, Exposed, Infectious, Recovery or Death) model extended to multiple population regions, the authors predict the evolution of the SARS‐CoV‐2 disease and construct an optimally scheduled lockdown calendar to execute lockdown over phases, using the well‐known Knapsack problem. A comparative analysis of both classical and quantum models shows that our model decreases SARS‐CoV‐2 active cases while retaining the average global economic factor, Gross Domestic Product, in contrast to the scenario with no lockdown.

As optimization problems become more complicated and extensive, parameterization becomes complex, resulting in a difficult task requiring significant amounts of time and resources. In this paper we propose a heuristic search algorithm we call MCSA (Montecarlo-Clustering Search Algorithm), which is based on Montecarlo sampling, and a clustering strategy involving two techniques. Our objective is to apply MCSA, an inherently stochastic method, to address optimization problems. To assess its performance, we conducted an evaluation using classical benchmark optimization functions. Additionally, we leveraged the CEC2017 benchmark suite to comprehensively evaluate the algorithm, highlighting the pivotal role of the Exploration stage in our methodology. Subsequently, we extended our methodology to tackle a practical combinatorial problem, the Knapsack problem. This NP-Hard problem holds significant real-world applications in resource allocation, scheduling, planning, logistics, and more. Our contributions lie in parameterizing the Knapsack Problem to align with MCSA’s parameters for reference indicators adjustment and achieving high-quality solutions, surpassing 90% in comparison to exhaustive methods such as branch and bound.

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]

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]

The 0-1 knapsack polyhedron as the most basic relaxation of a 0-1 integer program has attracted the attention of many researchers over the years. We present a very fast method that is guaranteed to generate one facet for the 0-1 knapsack polyhedron. Unlike lifting of cover inequities, our method does not require an initial minimal cover or a predetermined lifting sequencing, and its worst-case complexity is linear in some variables. Therefore, with minimal computational burden, it can be used to generate a potentially strong valid inequality based on any 0-1 relaxation of a general (Mixed) Integer Program (M)IP. Such valid inequalities can be added to the (M)IP problem prior to solving, or given their low computational cost, can be generated during solving the (M)IP, checked to see if they separate the incumbent fractional solution, and added to the problem if they do. [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]

This article studies binary linear programming problems in the presence of uncertainties that may prevent implementing the computed solution. This type of uncertainty, called implementation uncertainty, is modelled affecting the decision variables rather than model parameters. The binary nature of the decision variables invalidates using existing robust models for implementation uncertainty. The robust solutions obtained are optimal for a worst-case min–max objective. Structural properties allow the reformulation of the problem as a binary linear program. Constraint relaxation and cardinality-constrained parameters control the degree of solution conservatism. An optimization problem permits the selection of solutions from the obtained set of robust solutions. Results from a case study in the context of the knapsack problem suggest the methodology yields solutions that perform well in terms of objective value and feasibility. Furthermore, the selection approach can identify robust solutions with desirable implementation characteristics. [ABSTRACT FROM AUTHOR]

Articles scattered in the VINITI abstract database dated 2020–2022 are studied using the example of three thematic fragments: chemistry and chemical technologies, mechanical engineering, and metallurgy and welding. The mathematical formulas of Bradford and Vickery were used to calculate the number of journals in the third scattering zone. It is argued that the Bradford–Vickery law of publication scattering allows us to predict the minimum number of journals that cover more than 90% of articles quantity on a certain topic. The optimization of journal selection is reduced to the solution of the well-known knapsack problem. It is proposed to rank journals by thematic relevance. Unlike the Bradford model, intended to select the most productive journals, the proposed model is designed to select the most relevant journals. [ABSTRACT FROM AUTHOR]

Chaotic maps are sources of randomness formed by a set of rules and chaotic variables. They have been incorporated into metaheuristics because they improve the balance of exploration and exploitation, and with this, they allow one to obtain better results. In the present work, chaotic maps are used to modify the behavior of the binarization rules that allow continuous metaheuristics to solve binary combinatorial optimization problems. In particular, seven different chaotic maps, three different binarization rules, and three continuous metaheuristics are used, which are the Sine Cosine Algorithm, Grey Wolf Optimizer, and Whale Optimization Algorithm. A classic combinatorial optimization problem is solved: the 0-1 Knapsack Problem. Experimental results indicate that chaotic maps have an impact on the binarization rule, leading to better results. Specifically, experiments incorporating the standard binarization rule and the complement binarization rule performed better than experiments incorporating the elitist binarization rule. The experiment with the best results was STD_TENT, which uses the standard binarization rule and the tent chaotic map. [ABSTRACT FROM AUTHOR]

Copyright of Environmental & Social Management Journal / Revista de Gestão Social e Ambiental is the property of Environmental & Social Management Journal 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.)

Many service robots have to operate in a variety of different Service Event Areas (SEAs). In the case of the waste collection robot MARBLE (Mobile Autonomous Robot for Litter Emptying) every SEA has characteristics like varying area and number of litter bins, with different distances between litter bins and uncertain filling levels of litter bins. Global positions of litter bins and garbage drop-off positions from MARBLEs after reaching their maximum capacity are defined as task-performing waypoints. We provide boundary delimitation for characteristics that describe the SEA. The boundaries interpolate synergy between individual SEAs and the developed algorithms. This helps in determining which algorithm best suits an SEA, dependent on the characteristics. The developed route-planning methodologies are based on vehicle routing with simulated annealing (VRPSA) and knapsack problems (KSPs). VRPSA uses specific weighting based on route permutation operators, initial temperature, and the nearest neighbor approach. The KSP optimizes a route's given capacity, in this case using smart litter bins (SLBs) information. The game-theory KSP algorithm with SLBs information and the KSP algorithm without SLBs information performs better on SEAs lower than 0.5 km 2 , and with fewer than 50 litter bins. When the standard deviation of the fill rate of litter bins is ≈ 10 % , the KSP without SLB is preferred, and if the standard deviation is between 25 and 40%, then the game-theory KSP is selected. Finally, the vehicle routing problem outperforms in SEAs with an area of 0.5 ≤ 5 km2, 50–450 litter bins, and a fill rate of 10–40%. [ABSTRACT FROM AUTHOR]

A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection. TTP comprises an entanglement of a travelling salesman problem (TSP) and a knapsack problem (KP) since items of KP are scattered over cities of TSP, and a thief has to visit cities to collect items. In TTP, city selection and item selection decisions need close coordination since the thief's travelling speed depends on the knapsack's weight and the order of visiting cities affects the order of item collection. Existing TTP solvers deal with city selection and item selection separately, keeping decisions for one type unchanged while dealing with the other type. This separation essentially means very poor coordination between two types of decision. In this paper, we first show that a simple local search based coordination approach does not work in TTP. Then, to address the aforementioned problems, we propose a human designed coordination heuristic that makes changes to collection plans during exploration of cyclic tours. We further propose another human designed coordination heuristic that explicitly exploits the cyclic tours in item selections during collection plan exploration. Lastly, we propose a machine learning based coordination heuristic that captures characteristics of the two human designed coordination heuristics. Our proposed coordination based approaches help our TTP solver significantly outperform existing state-of-the-art TTP solvers on a set of benchmark problems. Our solver is named Cooperation Coordination (CoCo) and its source code is available from https://github.com/majid75/CoCo. [ABSTRACT FROM AUTHOR]

The single-sink fixed-charge transportation problem is known to have many applications in the area of manufacturing and transportation as well as being an important subproblem of the fixed-charge transportation problem. However, even the best algorithms from the literature do not fully leverage the structure of this problem, to the point of being surpassed by modern general-purpose mixed-integer programming solvers for large instances. We introduce a novel reformulation of the problem and study its theoretical properties. This reformulation leads to a range of new upper and lower bounds, dominance relations, linear relaxations, and filtering procedures. The resulting algorithm includes a heuristic phase and an exact phase, the main step of which is to solve a very small number of knapsack subproblems. Computational experiments are presented for existing and new types of instances. These tests indicate that the new algorithm systematically reduces the resolution time of the state-of-the-art exact methods by several orders of magnitude. [ABSTRACT FROM AUTHOR]

We study the investment incentives created by truthful mechanisms that allocate resources using approximation algorithms. Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem but guarantee nothing when accounting for investment incentives. An algorithm's allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. We introduce fast approximation algorithms for the knapsack problem that have no confirming negative externalities and guarantees close to 100% for both allocation and investment. [ABSTRACT FROM AUTHOR]

In this paper, we address the constrained knapsack problem with divisible item sizes and penalties (the CK-DSP problem, for short), which is modelled as follows. Given a set A = { a 1 , a 2 , ... , a n } of n items and a knapsack K with capacity L, where each item a i ∈ A has a size s i ∈ Z + , a profit c i ∈ R + , a penalty p i ∈ R + , and these n item sizes are divisible, i.e., either s i | s j or s j | s i for any two distinct items a i and a j in A, each item a i ∈ A must be either put into K under the constraint that the summation of sizes of items in K does not exceed L, or rejected with its penalty p i that we must pay for, it is asked to find a subset X ⊆ A to satisfy the constraint s (X) = ∑ a i ∈ X s i ≤ L . We consider three versions of the CK-DSP problem, respectively. (1) The constrained knapsack problem with divisible item sizes and total penalties (the CK-DSTP problem, for short) is asked to find a subset X ⊆ A to satisfy the constraint s (X) ≤ L , the objective is to maximize the value of total profits of the items in X minus total penalties paid for the rejected items not in X; (2) The constrained knapsack problem with divisible item sizes and maximum penalty (the CK-DSMP problem, for short) is asked to find a subset X ⊆ A to satisfy the constraint s (X) ≤ L , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the rejected items not in X; (3) The penalized knapsack problem with divisible item sizes (the PK-DS problem, for short) is asked to find a subset X ⊆ A to satisfy the constraint s (X) ≤ L , the objective is to maximize the value of total profits of the items in X minus maximum penalty paid for the items in X. As our contributions, we design three exact combinatorial algorithms to solve the CK-DSTP problem, the CK-DSMP problem and the PK-DS problem, and these three algorithms run in time O (n log n) , O (n 2 log n) and O (n 2 log n) , respectively, where n is the number of items with divisible sizes. [ABSTRACT FROM AUTHOR]

Lead pipe remediation budgets are limited and ought to maximize public health impact. This goal implies a nontrivial optimization problem; lead service lines connect water mains to individual houses, but any realistic replacement strategy must batch replacements at a larger scale. Additionally, planners typically lack a principled method for comparing the relative public health value of potential interventions and often plan projects based on nonhealth factors. This paper describes a simple process for estimating child health impact at a parcel level by cleaning and synthesizing municipal datasets that are commonly available but seldom joined due to data quality issues. Using geocoding as the core record linkage mechanism, parcel‐level toxicity data can be combined with school enrollment records to indicate where young children and lead lines coexist. A harm metric of estimated exposure‐years is described at the parcel level, which can then be aggregated to the project level and minimized globally by posing project selection as a 0/1 knapsack problem. Simplifying for use by nonexperts, the implied linear programming relaxation is solved with the greedy algorithm; ordering projects by benefit cost ratio produces a priority list that planners can then consider holistically alongside harder to quantify factors. A case study demonstrates the successful application of this framework to a small U.S. city's existing data to prioritize federal infrastructure funding. [ABSTRACT FROM AUTHOR]

Enterprise competitiveness is based on resource optimization, which can be considered a knapsack problem with resource constraints at both an enterprise level and some specific-resource level. Modeling an enterprise from a resource-based perspective, in this article, a Mathematical Modeling based on a knapsack problem is built to analyze the optimization of enterprise resources that are inside and outside of the enterprise, and the basic genetic algorithm is applied to solve the optimization in the knapsack problem of enterprise resource optimization. Enterprise resource optimization schemes from the perspective of knapsack problems, help allocate and make full use of resources and form different capabilities, to realize the corporate strategy.