1,721,090 research outputs found
On coordinated cutting plane generation and mixed integer programs with nonconvex 2-norm constraints
No full textThe impact of the norm on the k-Hyperplane Clustering problem: relaxations, restrictions, approximation factors, and exact formulations
No full textA distance-based point-reassignment heuristic for the k-hyperplane clustering problem
No full textWe consider the k-Hyperplane Clustering problem where, given a set of m points in R^n, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the square of the Euclidean distance between each point and the hyperplane of
the corresponding cluster. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many critical points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm
outperforms the state-of-the-art one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest group of instances, we obtain an average improvement in the solution quality of 54%
An Adaptive Point-Reassignment Metaheuristic for the k-Hyperplane Clustering Problem
No full textThe k-Hyperplane Clustering problem is that of, given a set of m points {a1, . . . , am} in Rn, determining k hyperplanes Hj = {a ∈ R n | w T j a = γj , wj ∈ R n, γj ∈ R}, with 1 ≤ j ≤ k, and assigning each point to a hyperplane so as to minimize the sum, over all points, of the squared 2-norm orthogonal distance between each point and the corresponding hyperplane. We propose an efficient metaheuristic based on a simple criterion for identifying points which are likely to be ill-assigned in the current solution and on their explicit reassignment to other
hyperplanes. In the algorithm, an adaptive strategy for updating a control parameter, which determines the number of such points that are actually considered, is combined with two features of Tabu Search.
Computational results obtained on real-world and challenging randomly generated instances show that a multi-start version of the best available algorithm provides solutions that are worse than the ones found by our metaheuristic by a factor of 33% on average. Neglecting the instances for which both algorithms provide equivalent solutions, since they may be optimal, the difference amounts to 41%
Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
No full textIn the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a righthand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is 4-hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovasz's Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub
Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems
Full text linkWe study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items and a set of metaitems. This problem generalizes the problem introduced by Ahmed S, Atamtürk A (Mathematical programming 128(1-2):149–169, 2011), and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering location, and influence maximization problems. In the paper, we propose a double-hypograph decomposition which allows for projecting out the variables associated with the items by separately exploiting the structural properties of the utility function and of the set-union operator. Thanks to it, the utility function is linearized via an exact outer-approximation technique, whereas the set-union operator is linearized in two ways: either (i) via a reformulation based on submodular cuts, or (ii) via a Benders decomposition. We analyze from a theoretical perspective the strength of the inequalities of the resulting reformulations, and embed them into two branch-and-cut algorithms. We also show how to extend our reformulations to the case where the utility function is not necessarily increasing. We then experimentally compare our algorithms inter se, to a standard reformulation based on submodular cuts, to a state-of-the-art global-optimization solver, and to the greedy algorithm for the maximization of a submodular function. The results reveal that, on our testbed, the method based on combining an outer approximation with Benders cuts significantly outperforms the other ones
Coordinated cutting plane generation via multi-objective separation
No full textIn cutting plane methods, the question of how to generate the best
possible set of cuts is both central and crucial. We propose a lexicographic
multi-objective cutting plane generation scheme that generates, among all the
maximally violated valid inequalities of a given family, an inequality that is
undominated and maximally diverse w.r.t. the cuts that were previously found.
By optimizing a diversity measure, we introduce a form of coordination between successive cuts. Our focus is on valid inequalities with 0-1 coefficients in the left-hand side and a constant right-hand side, which encompasses several
families of valid inequalities. As cut diversity measure, we consider an aggregate of the 1-norm distances w.r.t. the normal vectors of the previous cuts. In this case, our lexicographic multi-objective separation problem reduces to the standard separation problem with different values for the objective function coefficients. The impact of our coordinated cutting plane generation scheme is assessed in a pure cutting plane setting when separating Stable Set and Cut Set inequalities for, respectively, the Max Clique and Min Steiner Tree
problems. Compared to the standard separation of undominated maximally
violated cuts, we close the same fraction of the duality gap in a considerably
smaller number of rounds and cuts. The potential of our scheme is also indicated by the results obtained in a cut-and-branch setting for Max Clique,
where cut coordination allows for a substantial reduction, on average, of the
number of branch-and-bound nodes
On the exact separation of cover inequalities of maximum-depth
Full text linkWe investigate the problem of separating cover inequalities of maximum-depth exactly. We propose a pseudopolynomial-time dynamic-programming algorithm for its solution, thanks to which we show that this problem is weakly N P-hard (similarly to the problem of separating cover inequalities of maximum violation). We carry out extensive computational experiments on instances of the knapsack and the multidimensional knapsack problems with and without conflict constraints. The results show that, with a cutting-plane generation method based on the maximum-depth criterion, we can optimize over the cover-inequality closure by generating a number of cuts smaller than when adopting the standard maximum-violation criterion. We also
introduce the Point-to-Hyperplane Distance Knapsack Problem (PHD-KP), a problem closely related to the separation problem for maximum-depth cover inequalities, and show how the proposed dynamic programming algorithm can be adapted for effectively solving the PHD-KP as well
On the generation of cutting planes which maximize the bound improvement
No full textWe propose a new cutting plane algorithm for Integer Linear Programming, which we refer to as the bound-optimal cutting plane method. The algorithm amounts to simultaneously generating k cuts which, when added to the linear programming relaxation, yield the (provably) largest bound improvement. We show that, in the general case, the corresponding cut generating problem can be cast as a Quadratically Constrained Quadratic Program. We also show that, for a large family of cuts, the latter can be reformulated as a Mixed-Integer Linear Program. We present computational experiments on the generation of bound-optimal stable set and cover inequalities for the max clique and knapsack problems. They show that, with respect to standard algorithms, the bound-optimal cutting plane method allows for a substantial reduction in the number of cuts and iterations needed to achieve either a given bound or an optimal solution
- …
