排序方式: 共有2条查询结果,搜索用时 0 毫秒
1
1.
Sourour Elloumi 《Journal of Combinatorial Optimization》2010,19(1):69-83
Given a set of clients and a set of potential sites for facilities, the p-median problem consists of opening a set of p sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated
facility location problem. We propose a new formulation of this problem by a mixed integer linear problem. We show that this
formulation, while it has the same value by LP-relaxation, can be much more efficient than two previous formulations. The
computational experiment performed on two sets of benchmark instances has showed that the efficiency of the standard branch-and-cut
algorithm has been significantly improved. Finally, we explore the structure of the new formulation in order to derive reduction
rules and to accelerate the LP-relaxation resolution. 相似文献
2.
Alain Billionnet Sourour Elloumi Amélie Lambert 《Journal of Combinatorial Optimization》2014,28(2):376-399
Let \((MQP)\) be a general mixed-integer quadratic program that consists of minimizing a quadratic function \(f(x) = x^TQx +c^Tx\) subject to linear constraints. Our approach to solve \((MQP)\) is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem has additional variables \(y_{ij}\) , additional quadratic constraints \(y_{ij}=x_ix_j\) , a convex objective function, and a set of valid inequalities. Contrarily to the reformulation proposed in Billionnet et al. (Math Program 131(1):381–401, 2012), the equivalent problem cannot be directly solved by a standard solver. Here, we propose a new Branch and Bound process based on the relaxation of the non-convex constraints \(y_{ij}=x_ix_j\) to solve \((MQP)\) . Computational experiences are carried out on pure- and mixed-integer quadratic instances. The results show that the solution time of most of the considered instances with up to 60 variables is improved by our Branch and Bound algorithm in comparison with the approach of Billionnet et al. (2012) and with the general mixed-integer nonlinear solver BARON (Sahinidis and Tawarmalani, Global optimization of mixed-integer nonlinear programs, user’s manual, 2010). 相似文献
1