Contributed Session Thu.1.H 3012

Thursday, 10:30 - 12:00 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Exact algorithms for hard problems


Chair: Réal André Carbonneau



Thursday, 10:30 - 10:55 h, Room: H 3012, Talk 1

Réal André Carbonneau
Globally optimal clusterwise regression by branch and bound optimization with heuristics, sequencing and ending subset

Coauthors: Gilles Caporossi, Pierre Hansen


Clusterwise regression is a clustering technique which fits multiple lines or hyperplanes to mutually exclusive subsets of observations. It is a cubic problem, but can be re-formulated as a mixed logical-quadratic programming problem. An extension and generalization of Brusco's repetitive branch and bound algorithm (RBBA) is proposed for global optimization of the clusterwise regression problem. Branch and bound optimization is enhanced by heuristics, observation sequencing and ending subset optimization. Heuristics can improve the upper bound, observation sequencing can improve the search path and can increase fathoming, while the ending subsets can recursively strengthen the lower bounds of the search. Additionally, symmetry breaking and incremental regression calculations are employed to further speed up the optimization. Experiments demonstrate that the proposed optimization strategy is significantly faster than CPLEX and that the combination of all the components is significantly faster than each one individually. The proposed approach can optimize much larger datasets than what is possible using CPLEX.



Thursday, 11:00 - 11:25 h, Room: H 3012, Talk 2

Marzena Fügenschuh
LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: A computational comparison

Coauthors: Michael Armbruster, Christoph Helmberg, Alexander Martin


While semidefinite relaxations are known to deliver good approximations for combinatorial optimization problems like graph bisection, their practical scope is mostly associated with small dense instances. For large sparse instances, cutting plane techniques are considered the method of choice. These are also applicable for semidefinite relaxations via the spectral bundle method, which allows to exploit structural properties like sparsity. In order to evaluate the relative strengths of linear and semidefinite approaches for large sparse instances, we set up a common branch-and-cut framework for linear and semidefinite relaxations of the minimum graph bisection problem. Extensive numerical experiments show that our semidefinite branch-and- cut approach is a superior choice to the classical simplex approach for large sparse test instances from VLSI design and numerical optimization.



Thursday, 11:30 - 11:55 h, Room: H 3012, Talk 3

Adelaide Cruz Cerveira
A two-stage branch and bound algorithm to solve truss topology design problems

Coauthors: Agostinho Agra, Fernando Bastos, Joaquim Gromicho


Our paper considers a classic problem in the field of Truss topology design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage branch and bound algorithm. In the first stage we perform a branch and bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a branch and bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. For stability reasons, when a free node exists in the structure, we impose that at least two incident bars on it. These constraints are added during the first stage and lead to a tight model.
We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to ensure stability, as compared to a classical branch and bound algorithm, where branching is only performed on the bar areas.


  The majority of financial loan companies provide the service of getting Payday Loans North Carolina for U.S. citizens. In rare cases, the smarting in eyes and the tumefaction of eyelids can happen. In case of long term Cialis Black administration the side effects become less perceptible or disappear at all.