Search

The Unit-capacity Constrained Permutation Problem with Feasibility Recovery (UCPPFR) is to find a sequence of moves for pieces over a set of locations. From a given location, a piece can be moved to a unit capacity location, i.e. the latter location must be free of its original piece. Each piece has a specific type, and in the end every location must contain a piece of a required type. A piece must be handled using a specific tool, thus incurring a setup cost whenever a tool changeover is required. It could be necessary to use some Steiner locations to find a solution, thus incurring a Steiner cost. The aim of the UCPPFR is to find a sequence of moves with a minimum total setup and Steiner cost. We give a necessary and sufficient condition to check whether an instance admits a solution with no Steiner location. We show that the UCPPFR reduces to finding simultaneously a vertex-disjoint path cover and a shortest common supersequence. Finally, using a compact encoding for solutions and integer linear programming tools, we solve real instances coming from the nuclear power plant fuel renewal problem. [ABSTRACT FROM AUTHOR]

Metric uncapacitated facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. Capacitated facility location ( Cfl) is a generalization for which there are local-search-based constant-factor approximations, while there is no known compact relaxation with constant integrality gap. This paper produces, through a host of impossibility results, the first comprehensive investigation of the effectiveness of mathematical programming for metric capacitated facility location, with emphasis on lift-and-project methods. We show that the relaxations obtained from the natural LP at $$\varOmega (n)$$ levels of the semidefinite Lovász-Schrijver hierarchy for mixed programs, and at $$\varOmega (n)$$ levels of the Sherali-Adams hierarchy, have an integrality gap of $$\varOmega (n)$$ , where $$n$$ is the number of facilities, partially answering an open question of An et al. (Centrality of trees for capacitated k-center, ), Li and Svensson (Proceedings of 45th ACM Symposium on Theory of Computing, STOC '13. ACM, pp 901-910, ). For the families of instances we consider, both hierarchies yield at the $$n$$ th level an exact formulation for Cfl. Thus our bounds are asymptotically tight. Building on our methodology for the Sherali-Adams result, we prove that the standard Cfl relaxation enriched with the submodular inequalities of Aardal et al. (Math Oper Res 20:562-582, ), a generalization of the flow-cover valid inequalities, has also an $$\varOmega (n)$$ gap and thus not bounded by any constant. This disproves a long-standing conjecture of Levi et al (Math Program 131(1-2):365-379, ). We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration-style LPs. We characterize the behavior of proper relaxations for Cfl through a sharp threshold phenomenon. [ABSTRACT FROM AUTHOR]

In this paper the Uncapacitated Multiple Allocation p-hub Median Problem (the UMApHMP) is considered. A new heuristic method based on a genetic algorithm approach (GA) for solving UMApHMP is proposed. The described GA uses binary representation of the solutions. Genetic operators which keep the feasibility of individuals in the population are designed and implemented. The mutation operator with frozen bits is used to increase the diversibility of the genetic material. The running time of the GA is improved by caching technique. Proposed GA approach is bench-marked on the well known CAB and AP data sets and compared with the existing methods for solving the UMApHMP. Computational results show that the GA quickly reaches all previously known optimal solutions, and also gives results on large scale AP instances (up to n-200, p=20) that were not considered in the literature so far. [ABSTRACT FROM AUTHOR]