We propose a method called Polynomial Quadratic Convex Reformulation (PQCR) to solve exactly unconstrained binary polynomial problems (UBP) through quadratic convex reformulation. First, we ...quadratize the problem by adding new binary variables and reformulating (UBP) into a non-convex quadratic program with linear constraints (MIQP). We then consider the solution of (MIQP) with a specially-tailored quadratic convex reformulation method. In particular, this method relies, in a pre-processing step, on the resolution of a semi-definite programming problem where the link between initial and additional variables is used. We present computational results where we compare PQCR with the solvers Baron and Scip. We evaluate PQCR on instances of the image restoration problem and the low auto-correlation binary sequence problem from MINLPLib. For this last problem, 33 instances were unsolved in MINLPLib. We solve to optimality 10 of them, and for the 23 others we significantly improve the dual bounds. We also improve the best known solutions of many instances.
In this paper, we consider problem (P) of minimizing a quadratic function q(x)= xtQx + ctx of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. ...But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q + diag(u)) is positive semidefinite. Then, using the fact that xi2 = xi, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved. PUBLICATION ABSTRACT
Let (
MQP
) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (
MQP
), ...i.e. we reformulate (
MQP
) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation point of view. This reformulation, that we call MIQCR (Mixed Integer Quadratic Convex Reformulation), is based on the solution of an SDP relaxation of (
MQP
). Computational experiences are carried out with instances of (
MQP
) including one equality constraint or one inequality constraint. The results show that most of the considered instances with up to 40 variables can be solved in 1 h of CPU time by a standard solver.
Wireless sensor networks have been widely deployed in the last decades to provide various services, like environmental monitoring or object tracking. Such a network is composed of a set of sensor ...nodes which are used to sense and transmit collected information to a base station. To achieve this goal, two properties have to be guaranteed: (i) the sensor nodes must be placed such that the whole environment of interest (represented by a set of targets) is covered, and (ii) every sensor node can transmit its data to the base station (through other sensor nodes). In this paper, we consider the
Minimum Connected k-Coverage
(MC
k
C) problem, where a positive integer
k
≥
1
defines the coverage multiplicity of the targets. We propose two mathematical programming formulations for the MC
k
C problem on square grid graphs and random graphs. We compare them to a recent model proposed by Rebai et al. (Comput Oper Res 59:11–21,
2015
). We use a standard mixed integer linear programming solver to solve several instances with different formulations. In our results, we point out the quality of the LP-bound of each formulation as well as the total CPU time or the proportion of solved instances to optimality within a given CPU time.
Let
(
QP
)
be a 0-1 quadratic program which consists in minimizing a quadratic function subject to linear equality constraints. In this paper, we present QCR, a general method to reformulate
(
QP
)
...into an equivalent 0-1 program with a convex quadratic objective function. The reformulated problem can then be efficiently solved by a classical branch-and-bound algorithm, based on continuous relaxation. This idea is already present in the literature and used in standard solvers such as CPLEX. Our objective in this work was to find a convex reformulation whose continuous relaxation bound is, moreover, as tight as possible. From this point of view, we show that QCR is optimal in a certain sense. State-of-the-art reformulation methods mainly operate a perturbation of the diagonal terms and are valid for any
{
0
,
1
}
vector. The innovation of QCR comes from the fact that the reformulation also uses the equality constraints and is valid on the feasible solution domain only. Hence, the superiority of QCR holds by construction. However, reformulation by QCR requires the solution of a semidefinite program which can be costly from the running time point of view. We carry out a computational experience on three different combinatorial optimization problems showing that the costly computational time of reformulation by QCR can however result in a drastically more efficient branch-and-bound phase. Moreover, our new approach is competitive with very specific methods applied to particular optimization problems.
We consider unconstrained polynomial minimization problems with binary variables (BPO). These problems can be easily linearized, i.e., reformulated into a MILP in a higher dimensional space. Several ...linearizations are possible for a given BPO, depending on how each monomial is decomposed and replaced by additional variables and constraints. We focus on finding efficient linearizations that maximize the continuous relaxation bound of the resulting MILP. For this purpose, we introduce the notion of linearization patterns that allow us to model and enumerate the possible decompositions of a degree-d monomial. The assignment of a unique pattern to each monomial of BPO results in a reformulation of BPO into a MILP. Our method, called MaxBound, amounts to searching for an optimal association between monomials and patterns in the sense that it leads to a MILP with the best continuous relaxation bound. We show that this process can be formulated as a MILP which we denote by (MB˜). We further highlight domination properties among the patterns that allow us to discard the dominated patterns and to decrease the size of (MB˜). Another effect of these domination properties is that it now makes sense to search for a reformulation that requires as few additional variables as possible, based only on the non-dominated patterns. We call this reformulation method ND-MinVar and again show that it can be found by solving another MILP. We make an experimental study on degree 4 polynomials that compares the results of both methods and shows the advantages and disadvantages of each.
•Different extended linear reformulations yield different LP bounds.•An extended linear reformulation can be decomposed in linearization patterns.•Linearization patterns can be picked in order to maximize the LP bound.•Some patterns lead to a better bound than others.•Possibility to maximize the LP bound and minimize added variables simultaneously.
The weighted vertex p-center problem (PCP) consists of locating p facilities among a set of available sites such that the maximum weighted distance (or travel time) from any demand node to its ...closest located facility is minimized. This paper studies the exact solution of the two-stage robust weighted vertex p-center problem (RPCP2). In this problem, the location of the facilities is fixed in the first stage while the demand node allocations are recourse decisions fixed once the uncertainty is revealed. The problem is modeled by box uncertainty sets on both the demands and the distances. We introduce five different robust reformulations based on MILP formulations of (PCP) from the literature. We prove that considering a finite subset of scenarios is sufficient to obtain an optimal solution of (RPCP2). We leverage this result to introduce a column-and-constraint generation algorithm and a branch-and-cut algorithm to efficiently solve this problem optimally. We highlight how these algorithms can also be adapted to solve the single-stage problem (RPCP1) which is obtained when no recourse is considered. We present a numerical study to compare the performances of these formulations on randomly generated instances and on a case study from the literature.
•Five MILP formulations considering box uncertainty sets on demands and distances•The optimal solution can be obtained by only considering a finite subset of scenarios•A branch-and-cut algorithm and a column-and-constraint algorithm are proposed•The exact solution algorithms can be adapted to solve the single-stage problem
•The Benders sub-problems of the p-median problem can be solved very quickly with a polynomial-time algorithm.•The efficient implementation of a two-stage Benders decomposition algorithm performs ...better than state-of-the-art exact methods in solving instances of up to 238025 clients and sites, and also previously unsolved benchmark instances.•The two-stage Benders decomposition algorithm can be adapted to other location problems such as the uncapacitated facility location problem and the optimal diversity management problem.
The p-median problem is a classic discrete location problem with numerous applications. It aims to open p sites while minimizing the sum of the distances of each client to its nearest open site. We study a Benders decomposition of the most efficient formulation in the literature. We show that the Benders cuts can be separated in linear time. The Benders reformulation leads to a compact formulation for the p-median problem. We implement a two-phase Benders decomposition algorithm that outperforms state-of-the-art methods on benchmark instances by an order of magnitude and allows to exactly solve for the first time several instances among which are large TSP instances and BIRCH instances. We also show that our implementation easily applies to the uncapacitated facility location problem.
Interval branch-and-bound solvers provide reliable algorithms for handling non-convex optimization problems by ensuring the feasibility and the optimality of the computed solutions, i.e. ...independently from the floating-point rounding errors. Moreover, these solvers deal with a wide variety of mathematical operators. However, these solvers are not dedicated to quadratic optimization and do not exploit nonlinear convex relaxations in their framework. We present an interval branch-andbound method that can efficiently solve quadratic optimization problems. At each node explored by the algorithm, our solver uses a quadratic convex relaxation which is as strong as a semi-definite programming relaxation, and a variable selection strategy dedicated to quadratic problems. The interval features can then propagate efficiently this information for contracting all variable domains. We also propose to make our algorithm rigorous by certifying firstly the convexity of the objective function of our relaxation, and secondly the validity of the lower bound calculated at each node. In the non-rigorous case, our experiments show significant speedups on general integer quadratic instances, and when reliability is required, our first results show that we are able to handle medium-sized instances in a reasonable running time.
PDF
