TY  - JOUR
A1  - Roostapour, Vahid
A1  - Neumann, Aneta
A1  - Neumann, Frank
A1  - Friedrich, Tobias
T1  - Pareto optimization for subset selection with dynamic cost constraints
JF  - Artificial intelligence
N2  - We consider the subset selection problem for function f with constraint bound B that changes over time. Within the area of submodular optimization, various greedy approaches are commonly used. For dynamic environments we observe that the adaptive variants of these greedy approaches are not able to maintain their approximation quality. Investigating the recently introduced POMC Pareto optimization approach, we show that this algorithm efficiently computes a phi=(alpha(f)/2)(1 - 1/e(alpha)f)-approximation, where alpha(f) is the submodularity ratio of f, for each possible constraint bound b <= B. Furthermore, we show that POMC is able to adapt its set of solutions quickly in the case that B increases. Our experimental investigations for the influence maximization in social networks show the advantage of POMC over generalized greedy algorithms. We also consider EAMC, a new evolutionary algorithm with polynomial expected time guarantee to maintain phi approximation ratio, and NSGA-II with two different population sizes as advanced multi-objective optimization algorithm, to demonstrate their challenges in optimizing the maximum coverage problem. Our empirical analysis shows that, within the same number of evaluations, POMC is able to perform as good as NSGA-II under linear constraint, while EAMC performs significantly worse than all considered algorithms in most cases.
KW  - Subset selection
KW  - Submodular function
KW  - Multi-objective optimization
KW  - Runtime analysis
Y1  - 2022
U6  - https://doi.org/10.1016/j.artint.2021.103597
SN  - 0004-3702
SN  - 1872-7921
VL  - 302
PB  - Elsevier
CY  - Amsterdam
ER  - 
TY  - JOUR
A1  - Bobda, Christophe
A1  - Yonga, Franck
A1  - Gebser, Martin
A1  - Ishebabi, Harold
A1  - Schaub, Torsten H.
T1  - High-level synthesis of on-chip multiprocessor architectures based on answer set programming
JF  - Journal of Parallel and Distributed Computing
N2  - We present a system-level synthesis approach for heterogeneous multi-processor on chip, based on Answer Set Programming(ASP). Starting with a high-level description of an application, its timing constraints and the physical constraints of the target device, our goal is to produce the optimal computing infrastructure made of heterogeneous processors, peripherals, memories and communication components. Optimization aims at maximizing speed, while minimizing chip area. Also, a scheduler must be produced that fulfills the real-time requirements of the application. Even though our approach will work for application specific integrated circuits, we have chosen FPGA as target device in this work because of their reconfiguration capabilities which makes it possible to explore several design alternatives. This paper addresses the bottleneck of problem representation size by providing a direct and compact ASP encoding for automatic synthesis that is semantically equivalent to previously established ILP and ASP models. We describe a use-case in which designers specify their applications in C/C++ from which optimum systems can be derived. We demonstrate the superiority of our approach toward existing heuristics and exact methods with synthesis results on a set of realistic case studies. (C) 2018 Elsevier Inc. All rights reserved.
KW  - System design
KW  - Architecture synthesis
KW  - Answer set programming
KW  - Multi-objective optimization
KW  - Technology mapping
KW  - Reconfigurable architecture
Y1  - 2018
U6  - https://doi.org/10.1016/j.jpdc.2018.02.010
SN  - 0743-7315
SN  - 1096-0848
VL  - 117
SP  - 161
EP  - 179
PB  - Elsevier
CY  - San Diego
ER  - 
TY  - JOUR
A1  - Banbara, Mutsunori
A1  - Inoue, Katsumi
A1  - Kaufmann, Benjamin
A1  - Okimoto, Tenda
A1  - Schaub, Torsten H.
A1  - Soh, Takehide
A1  - Tamura, Naoyuki
A1  - Wanko, Philipp
T1  - teaspoon
BT  - solving the curriculum-based course timetabling problems with answer set programming
JF  - Annals of operation research
N2  - Answer Set Programming (ASP) is an approach to declarative problem solving, combining a rich yet simple modeling language with high performance solving capacities. We here develop an ASP-based approach to curriculum-based course timetabling (CB-CTT), one of the most widely studied course timetabling problems. The resulting teaspoon system reads a CB-CTT instance of a standard input format and converts it into a set of ASP facts. In turn, these facts are combined with a first-order encoding for CB-CTT solving, which can subsequently be solved by any off-the-shelf ASP systems. We establish the competitiveness of our approach by empirically contrasting it to the best known bounds obtained so far via dedicated implementations. Furthermore, we extend the teaspoon system to multi-objective course timetabling and consider minimal perturbation problems.
KW  - Educational timetabling
KW  - Course timetabling
KW  - Answer set programming
KW  - Multi-objective optimization
KW  - Minimal perturbation problems
Y1  - 2018
U6  - https://doi.org/10.1007/s10479-018-2757-7
SN  - 0254-5330
SN  - 1572-9338
VL  - 275
IS  - 1
SP  - 3
EP  - 37
PB  - Springer
CY  - Dordrecht
ER  -