对于离散的α-邻居p-中心问题的确切解决方法
Elisabeth Gaar1, Markus Sinnl1,2
1Institute of Production and Logistics Management Johannes Kepler University Linz Linz Austria.
概括
本研究为离散k邻 k中心问题 (d-k-k-CP) 引入了新的整数编程公式和分支和切割算法. 这些方法有效地解决了许多问题实例,以证明最佳性,改进现有解决方案.
科学领域:
- 运营研究 运营研究
- 离散优化的优化.
- 设施位置问题 设施位置问题
背景情况:
- 离散的k-邻居k-中心问题 (d-k-k-CP) 是经典的k-中心问题的最近研究的变体.
- 对于d-k-k-CP的现有解决方案主要包括近似算法和启发式.
研究的目的:
- 为d-k-k-CP开发精确的算法.
- 引入新的整数编程公式和相关的理论结果.
主要方法:
- 为d-k-k-CP开发了两个整数编程公式.
- 纳入取消不平等,有效不平等和变量固定程序.
- 构建了增强的分支和切割 (B&C) 算法,具有启动和原始启发学.
主要成果:
- 在文献中的194个实例中,在116个实例中实现了被证明的最佳性.
- 经过证明的有效性,大多数解决的实例在1分钟的运行时间内.
- 为116个实例提供了改进的解决方案值.
结论:
- 提出的整数编程公式和B&C算法对于解决d-k-k-CP.有效.
- 这项工作推进了解决这个新出现的设施位置问题的最先进技术.
相关概念视频
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
53
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...
53
Area Computation by the Alternative Coordinate Method
52
The alternative coordinate method, also known as the Shoelace Formula, is a technique for determining the area of a traverse using Cartesian coordinates. This method relies on the sequential arrangement of x and y coordinates for each point of the shape, ensuring accuracy and ease of application.In this approach, each corner's x and y coordinates are listed as fractions, with the x-coordinate as the numerator and the y-coordinate as the denominator. These coordinates are arranged sequentially...
52
Centroid of a Body: Problem Solving
1.2K
The centroid of a body is a crucial concept in engineering and physics. Finding the centroid of a body can help determine its stability, its balance point, and even its design. In this context, consider a thin wire bent in the form of a quarter circular arc. Polar coordinates are used to calculate the centroid. The wire is first divided into small differential elements of a length equal to the radius multiplied by the differential angle.
The x-coordinates and y-coordinates of each element's...
The x-coordinates and y-coordinates of each element's...
1.2K
Theorems of Pappus and Guldinus: Problem Solving
739
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
739
Lattice Centering and Coordination Number
9.6K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
Types of Unit Cells
Imagine taking a large number of identical...
9.6K
Chirality at Nitrogen, Phosphorus, and Sulfur
5.7K
Chirality is most prevalent in carbon-based tetrahedral compounds, but this important facet of molecular symmetry extends to sp3-hybridized nitrogen, phosphorus and sulfur centers, including trivalent molecules with lone pairs. Here, the lone pair behaves as a functional group in addition to the other three substituents to form an analogous tetrahedral center that can be chiral.
A consequence of chirality is the need for enantiomeric resolution. While this is theoretically possible for all...
A consequence of chirality is the need for enantiomeric resolution. While this is theoretically possible for all...
5.7K


