1,721,202 research outputs found
A 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%
PGS-COM: A hybrid method for non-smooth black-box constrained optimization problems
No full textIn the areas of chemical processes and energy systems, the relevance of black-box optimization problems is growing because they arise not only in the optimization of processes with modular/sequential simulation codes but also when decomposing complex optimization problems into bilevel programs. The objective function is typically discontinuous, non-differentiable, not defined in some points, noisy, and subject to linear and nonlinear relaxable and unrelaxable constraints. In this work, after briefly reviewing the main available direct-search methods applicable to this class of problems, we propose a new hybrid algorithm, referred to as PGS-COM, which combines the positive features of Constrained Particle Swarm, Generating Set Search, and Complex. The remarkable performance of PGS-COM is assessed and compared with that of eleven main alternative methods on twenty five test problems as well as two challenging process engineering applications related to the optimization of a heat recovery steam cycle and a styrene production process
The complexity and approximability of finding maximum feasible subsystems of linear relations
No full textAbstractWe study the combinatorial problem which consists, given a system of linear relations, of finding a maximum feasible subsystem, that is a solution satisfying as many relations as possible. The computational complexity of this general problem, named Max FLS, is investigated for the four types of relations =, ⩾, > and ≠. Various constrained versions of Max FLS, where a subset of relations must be satisfied or where the variables take bounded discrete values, are also considered. We establish the complexity of solving these problems optimally and, whenever they are intractable, we determine their degree of approximability. Max FLS with =, ⩾ or > relations is NP-hard even when restricted to homogeneous systems with bipolar coefficients, whereas it can be solved in polynomial time for ≠ relations with real coefficients. The various NP-hard versions of Max FLS belong to different approximability classes depending on the type of relations and the additional constraints. We show that the range of approximability stretches from Apx-complete problems which can be approximated within a constant but not within every constant unless P = NP, to NPO PB-complete ones that are as hard to approximate as all NP optimization problems with polynomially bounded objective functions. While Max FLS with equations and integer coefficients cannot be approximated within pε for some ε > 0, where p is the number of relations, the same problem over GF(q) for a prime q can be approximated within q but not within qε for some ε > 0. Max FLS with strict or nonstrict inequalities can be approximated within 2 but not within every constant factor. Our results also provide strong bounds on the approximability of two variants of Max FLS with ⩾ and > relations that arise when training perceptrons, which are the building blocks of artificial neural networks, and when designing linear classifiers
A two-phase heuristic for the bottleneck k-hyperplane clustering problem
No full textIn the bottleneck hyperplane clustering problem, given n points in Rd and an integer k with 1≤k≤n, we wish to determine k hyperplanes and assign each point to a hyperplane so as to minimize the maximum Euclidean distance between each point and its assigned hyperplane. This mixed-integer nonlinear problem has several interesting applications but is computationally challenging due, among others, to the nonconvexity arising from the l2-norm. After comparing several linear approximations to deal with the l2-norm constraint, we propose a two-phase heuristic. First, an approximate solution is obtained by exploiting the l∞-approximation and the problem geometry, and then it is converted into an l2-approximate solution. Computational experiments on realistic randomly generated instances and instances arising from piecewise affine maps show that our heuristic provides good quality solutions in a reasonable amount of time
A Methodology for Optimizing Heat recovery Steam Cycles based on Linear Programming and Particle Swarm
No full text- …
