Many combinatorial optimization problems can be formulated as the minimization of a 0-1quadratic function subject to linear constraints. In this paper, we are interested in the exact solution of this problem through ...
详细信息
Many combinatorial optimization problems can be formulated as the minimization of a 0-1quadratic function subject to linear constraints. In this paper, we are interested in the exact solution of this problem through a two-phase general scheme. The first phase consists in reformulating the initial problem either into a compact mixed integer linear program or into a 0-1quadratic convex program. The second phase simply consists in submitting the reformulated problem to a standard solver. The efficiency of this scheme strongly depends on the quality of the reformulation obtained in phase 1. We show that a good compact linear reformulation can be obtained by solving a continuous linear relaxation of the initial problem. We also show that a good quadratic convex reformulation can be obtained by solving a semidefinite relaxation. In both cases, the obtained reformulation profits from the quality of the underlying relaxation. Hence, the proposed scheme gets around, in a sense, the difficulty to incorporate these costly relaxations in a branch-and-bound algorithm.
We explore in this paper certain rich geometric properties hidden behind quadratic 0-1 programming. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0-1 optimization prob...
详细信息
We explore in this paper certain rich geometric properties hidden behind quadratic 0-1 programming. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0-1 optimization problems by investigating geometric features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality conditions for quadratic 0-1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a branch-and-bound type, we obtain promising preliminary computational results.
In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function (x, Ax) + (c, x) over the set {0,1}(n) where ...
详细信息
In this paper we consider the constant rank unconstrained quadratic 0-1 optimization problem, CR-QP01 for short. This problem consists in minimizing the quadratic function (x, Ax) + (c, x) over the set {0,1}(n) where c is a vector in R-n and A is a symmetric real n x n matrix of constant rank r. We first present a pseudo-polynomial algorithm for solving the problem CR-QP01, which is known to be NP-hard already for r = 1. We then derive two new classes of special cases of the CR-QP01 which can be solved in polynomial time. These classes result from further restrictions on the matrix A. Finally we compare our algorithm with the algorithm of Allemand et al. (2001) for the CR-QP01 with negative semidefinite A and extend the range of applicability of the latter algorithm. It turns out that neither of the two algorithms dominates the other with respect to the class of instances which can be solved in polynomial time.
We prove that the problem of checking whether a quadratic 0-1 problem has a unique solution is NP-hard. Furthermore, we prove that finding the global minimum of quadratic 0-1 programming with unique solution remains a...
详细信息
We prove that the problem of checking whether a quadratic 0-1 problem has a unique solution is NP-hard. Furthermore, we prove that finding the global minimum of quadratic 0-1 programming with unique solution remains an NP-hard problem. Regarding local search, we prove that the problem of finding a discrete local minimum for quadratic 0-1 problems, with two coordinates being fixed, is NP-hard. In addition, we discuss an algorithm for computing discrete local minima.
We consider the reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems. In this reduction, the number of additional continuous variables is O(kn) (n is the number of initial 0-1...
详细信息
We consider the reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems. In this reduction, the number of additional continuous variables is O(kn) (n is the number of initial 0-1 variables and k is the number of quadratic constraints). The number of 0-1 variables remains the same. (C) 2004 Elsevier B.V. All rights reserved.
We present computational experience with a cutting plane algorithm for 0–1 quadraticprogramming without constraints. Our approach is based on a reduction of this problem to a max-cut problem in a graph and on a part...
详细信息
We present computational experience with a cutting plane algorithm for 0–1 quadraticprogramming without constraints. Our approach is based on a reduction of this problem to a max-cut problem in a graph and on a partial linear description of the cut polytope.
In this paper, we present two heuristics for solving the unconstrained quadratic o-i programming problem. First heuristic realizes the steepest ascent from the centre of the hypercube, while the second constructs a se...
详细信息
The decomposed information of power consumption of household appliances is meaningful for scheduling the appliances and the reduction in home energy use. This paper presents a novel nonintrusive load identification me...
详细信息
ISBN:
(纸本)9781467364874
The decomposed information of power consumption of household appliances is meaningful for scheduling the appliances and the reduction in home energy use. This paper presents a novel nonintrusive load identification method based on continuous quadratic 0-1 programming. Extensive lab tests have demonstrated that the proposed technique can provide adequate load identification accuracy for residential energy monitoring and is suitable to be used in a nonintrusive load monitoring (NILM) systems in residential and commercial buildings.
quadratic 0-1 problems with linear inequality constraints are briefly considered in this *** optimality conditions for these problems,including a necessary condition and some sufficient conditions,are *** necessary co...
详细信息
quadratic 0-1 problems with linear inequality constraints are briefly considered in this *** optimality conditions for these problems,including a necessary condition and some sufficient conditions,are *** necessary condition is expressed without dual *** relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.
We describe the simplest technique to tackle 0-1quadratic Programs with linear constraints among those that turn out to be successful in practice. This method is due to and familiar to the quadratic Assignment expert...
详细信息
We describe the simplest technique to tackle 0-1quadratic Programs with linear constraints among those that turn out to be successful in practice. This method is due to and familiar to the quadratic Assignment experts, even if it took some time to realize that most approaches to the problem could be interpreted in these terms, whereas it does not appear to be widely known outside this community. Since the technique is completely general and is by far the most successful one in several other cases, such as quadratic Knapsack, we illustrate it in its full generality, pointing out its relationship to Lagrangian and linear programming relaxations and discussing further extensions. We believe that this method should be in the background of every practitioner in Combinatorial Optimization. (c) 2006 Elsevier B.V. All rights reserved.
暂无评论