|
|
 |
|
Mardi 3 Décembre
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
A branch-and-bound method for box constrained integer polynomial optimization |
| Description: |
Claudia D'Ambrosio We consider the problem of minimizing an arbitrary polynomial subject to
box and integrality constraints. We propose a new class of
under-estimators composed of separable functions of the original variables
and use it within a branch-and-bound scheme to easily and quickly compute
lower bounds. Computational results on randomly generated instances show
good performance with respect to the ones of different open-source solvers
like Couenne, Gloptipoly , and SCIP.
Moreover, the second part of the talk will be devoted to present a
different perspective on partially separable problems. In particula, an
exact algorithm for mixed integer non-linear programming problems with
separable non-convexities will be presented. |
| Heure: |
14:00 - 17:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Efficient Algorithms for Dualizing Large-Scale Hypergraphs |
| Description: |
Uno Takeaki A hypergraph F is a set family defined on vertex set V.The dual of F is the set of minimal subsets H of V such thatJ cap H
e emptyset for any J in FThe computation of the dual is equivalent to many problems, such asminimal hitting set enumeration of a subset family, minimal set coverenumeration, and the enumeration of hypergraph transversals.In this paper, we introduce a new set system induced by the minimalitycondition of the hitting sets, that enables us to use efficient pruningmethods.We further propose an efficient algorithm for checking the minimality,that enables us to construct time efficient and polynomial spacedualization algorithms.The computational experiments show that our algorithms are quite fasteven for large-scale input for which existing algorithms do notterminate in practical time. |
|
|
