35. On the selection of an initial set of conditions for submodular function maximization for fully connected graph instances
Invited abstract in session WF-2: Combinatorial Optimization II, stream Discrete Optimization.
Wednesday, 16:45 - 18:15Room: C 103
Authors (first author is the speaker)
| 1. | Eszter Csokas
|
| 2. | Tamas Vinko
|
| University of Szeged |
Abstract
The submodular function maximization (SFM) problem is a popular and well-researched combinatorial optimization problem. Nemhauser and Wolsey published the well-known constraint generating (CG) algorithm in 1981. CG solves a reduced MIP problem first, which is extended iteratively with additional constraints. In that paper, Nemhauser and Wolsey stated also that four problems are fundamental to solving integer programming models. One of them is the set of initial constraints, i.e., how to choose this set correctly, efficiently. Since the greedy method provides the approximation (1-1/e), it is traditionally used as the starting point for CG-type solving algorithms.
In our previous work, we have given a centrality metric that can be used to define an initial set of constraints for SFM tasks with non-fully bipartite graph representation. It turns out that choosing a starting point different from the greedy solution can provide a more efficient solution in terms of runtime for CG-type solver algorithms.
The focus of our current research is to extend the above mentioned centrality metric for SFM tasks with fully-connected bipartite graph representation. The effectiveness of using the starting point proposed by the centrality metric will be demonstrated.
Keywords
- Complexity and efficiency of optimization algorithms
- Global optimization
- Data driven optimization
Status: accepted
Back to the list of papers