Related Experiment Video
Updated: Jul 7, 2026
11:53
The Modular Design and Production of an Intelligent Robot Based on a Closed-Loop Control Strategy
Published on: October 14, 2017
Genetic algorithms with decomposition procedures for multidimensional 0-1 knapsack problems with block angular
1Dept. of Artificial Complex Syst. Eng., Hiroshima Univ., Higashi-Hiroshima, Japan.
Summary
This study introduces genetic algorithms with decomposition for large-scale multidimensional 0-1 knapsack problems. The novel method efficiently finds feasible solutions for complex block angular structures.
Area of Science:
- Operations Research
- Computer Science
- Optimization
Background:
- Large-scale multidimensional 0-1 knapsack problems with block angular structures are computationally challenging.
- Existing methods may struggle with the complexity of coupling and block constraints.
Purpose of the Study:
- To present a novel genetic algorithm approach using decomposition procedures for large-scale multidimensional 0-1 knapsack problems.
- To develop a method that effectively handles block angular structures and coupling constraints.
Main Methods:
- Introduction of a triple string representation and a corresponding decoding algorithm.
- Application of genetic algorithms with decomposition procedures as an approximate solution technique.
Main Results:
- The proposed method generates potential solutions satisfying both block and coupling constraints.
- Computational experiments with up to 1000 variables demonstrate the method's feasibility and efficiency.
Conclusions:
- Genetic algorithms with decomposition procedures offer a viable and efficient approach for solving large-scale multidimensional 0-1 knapsack problems.
- The triple string representation and decoding algorithm are key to handling complex constraint structures.
More Related Videos
Related Concept Videos
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
01:30Gaussian Elimination: Problem Solving
Systems of linear equations in several variables are pivotal in modeling complex scenarios involving multiple unknowns and constraints. Such systems are widely used in various fields to represent relationships where several conditions must be simultaneously satisfied. Each variable in the system corresponds to an unknown quantity, while each equation imposes a linear constraint, leading to a structured approach for analyzing and solving real-world problems.A system of three equations with three...
01:16Statically Indeterminate Problem Solving
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
01:30Lagrange Multipliers: Problem Solving
A silo with a cylindrical base, flat bottom, and hemispherical roof is a common design in agricultural and industrial storage due to its structural efficiency and ease of construction. Optimizing its dimensions to maximize storage capacity for a given amount of material—i.e., a fixed surface area—is a classic problem in applied calculus and engineering design. The key parameters are the radius r of the base and the height h of the cylindrical section.The total volume of the silo is obtained by...
01:29Vectors in 2D: Problem Solving
A plane traveling due north at 180 km/h in still air was found to be 80 km off-course after 30 minutes, deviating approximately 5 degrees east of north. This deviation means the influence of a crosswind alters the plane’s intended trajectory. The actual ground path formed a diagonal, suggesting that the aircraft’s effective ground speed was reduced to 160 km/h and directed slightly to the east due to the wind.By analyzing the displacement from the intended path, the velocity contributed by the...
01:24One-Compartment Open Model: Wagner-Nelson and Loo Riegelman Method for ka Estimation
This lesson introduces two critical methods in pharmacokinetics, the Wagner-Nelson and Loo-Riegelman methods, used for estimating the absorption rate constant (ka) for drugs administered via non-intravenous routes. The Wagner-Nelson method relates ka to the plasma concentration derived from the slope of a semilog percent unabsorbed time plot. However, it is limited to drugs with one-compartment kinetics and can be impacted by factors like gastrointestinal motility or enzymatic degradation.
On...
On...