We consider the quadratic semi-assignment problem in which we minimize a quadratic pseudo-Boolean function F subject to the semi-assignment constraints. We propose in this paper a linear programming method to obtain t...
详细信息
We consider the quadratic semi-assignment problem in which we minimize a quadratic pseudo-Boolean function F subject to the semi-assignment constraints. We propose in this paper a linear programming method to obtain the best reduction of this problem, i.e. to compute the greatest constant c such that F is equal to c plus F' for all feasible solutions, F' being a quadratic pseudo-Boolean function with nonnegative coefficients. Thus constant c can be viewed as a generalization of the height of an unconstrained quadratic 0-1 function introduced in (Hammer et al., Math. Program. 28 (1984) 121-155), to constrained quadratic 0-1 optimization. Finally, computational experiments proving the practical usefulness of this reduction are reported. (C) 2001 Elsevier Science B.V. All rights reserved.
Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framewor...
详细信息
Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framework to reformulate a BQP problem with linear constraints to a new BQP with an exponential number of variables defined on a graph. This framework relies on the concept of stars in the graph to split the quadratic costs into adjacent and nonadjacent components indicating in -star and out -of -star interactions. We exploit the star -based structure of the new reformulation to develop a decompositionbased column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures. The quadratic component of the problem is dealt with in the column generation master problem and its subproblem. Results indicate the superiority of the framework over one of the state-of-the-art solvers, GUROBI, when applied to various benchmark reformulations with adjacent -only or sparse quadratic cost matrices. The framework outperforms GUROBI in terms of both dual bound and computational time in almost all instances.
暂无评论