Journal:Informatica
Volume 24, Issue 4 (2013), pp. 523–542
Abstract
In this article, we propose a practical algorithm for capacitated facility location problems (CFLP). There are some approaches which can obtain primal solutions while simultaneously exploiting the primal structure and the dual structure. One of these approaches is the mean value cross decomposition (MVCD) method that ensures convergence without solving master problems. However, MVCD has been previously applied only to uncapacitated facility location problems (UFLP), due to the fact that the performance is highly dependent on the structure of the problem. The proposed algorithm, named the dynamic mean value cross decomposition algorithm (DMVCD), is effectively integrated with MVCD and cutting plane methods in order to tighten the bounds by reducing the duality gap. Computational results of various instances are also reported to verify the effectiveness and efficiency of DMVCD.
Journal:Informatica
Volume 8, Issue 4 (1997), pp. 559–582
Abstract
In this research, we develop an algorithm for linear programming problems based on a new interpretation of Karmarkar's representation for this problem. Accordingly, we examine a suitable polytope for which the origin is an exterior point, and in order to determine an optimal solution, we need to ascertain the minimum extent by which this polytope needs to be slid along a one-dimensional axis so that the origin belongs to it. To accomplish this, we employ strongly separating hyperplanes between the origin and the polytope using a closest point routine. The algorithm is further enhanced by the generation of dual solutions which enable us to deform the polytope so that it is favorably positioned with respect to the origin and the axis of sliding motion. The overall scheme is easy to implement, requires a minimal amount of storage, and produces quick good quality lower bounds for the problem in its infinite convergence process. A switchover to the simplex method or an interior point method is also possible, using the current available solution as an advanced start. Preliminary computational results are provided along with implementation guidelines.