welcome: please sign in

Revision 9 as of 2011-01-10 16:24:33

Clear message
location: PreliminaryProblemList

Preliminary List of Selected Benchmark Problems


#

Problem Name

Author(s)

Model & Solve Competition

System Competition

Type

Class

Language for System Competition

Preliminary Problem Description

1

Crossing minimization in layered graphs

Peter Stuckey and Graeme Gange

Yes

No

Optimization

Beyond NP/Opt

-

view

2

Reachability

Giorgio Terracina

Yes

Yes

Query

P

ASP-Core

view

3

Strategic Companies

Mario Alviano, Marco Maratea and Francesco Ricca

Yes

Yes

Search

Beyond NP

ASP-Core

view

4

Company Controls

Mario Alviano

Yes

Yes

Optimization

P

ASP-RfC

view

5

Company Controls Optimize

Mario Alviano

Yes

No

Optimization

Beyond NP/Opt

-

view

6

Grammar-Based Information Extraction

Marco Manna

Yes

Yes

Search

P

ASP-Core

view

7

Generalized Slitherlink

Wolfgang Faber

Yes

No

Search

NP

-

view

8

Fastfood Optimality Check

Wolfgang Faber

Yes

No

Search

NP

-

view

9

Fastfood Optimization

Wolfgang Faber

Yes

No

Optimization

Beyond NP/Opt

-

view

10

Sokoban Decision

Wolfgang Faber

Yes

Yes

Search

NP

ASP-Core

view

11

Sokoban Optimization

Wolfgang Faber

Yes

No

Optimization

Beyond NP/Opt

-

view

12

Knight Tour

Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

13

Disjunctive Scheduling

Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

14

Packing Problem

Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

15

Tomography Problem

Neng-Fa Zhou

Yes

Yes

Optimization

NP

ASP-Core

view

16

Maximal Clique

Johan Wittocx

Yes

No

Optimization

Beyond NP/Opt

-

view

17

Labyrinth

Martin Gebser

Yes

Yes

Search

NP

ASP-Core

view

18

Minimal Diagnosis

Martin Gebser

Yes

Yes

Search

Beyond NP

ASP-Core

view

19

Multi Context System Querying

Peter Schüller

No

Yes

Query

NP

ASP-Core

view

20

Numberlink

Naoyuki Tamura and Neng-Fa Zhou

Yes

Yes

Search

NP

ASP-Core

view

21a

Reverse Folding

Andrea Formisano, Agostino Dovier and Enrico Pontelli

Yes

No

Search

NP

-

view

21b

Gas Diffusion

Andrea Formisano, Agostino Dovier and Enrico Pontelli

Yes

Yes

Search

NP

ASP-Core

view

21c

Tangram

Andrea Formisano, Agostino Dovier and Enrico Pontelli

Yes

No

Search

NP

-

view

22

Hanoi Tower

Miroslaw Truszczynski

Yes

Yes

Search

NP

ASP-Core

view

23

Magic Square Sets

Yisong Wang and Jia-Huai You

Yes

No

Search

NP

ASP-RfC

view

24

Airport Pickup

A. Ricardo Morales

Yes

No

Search

NP

-

view

25

GraphColouring

Yuliya Lierler and Marcello Balduccini

Yes

Yes

Search

NP

ASP-Core

view

26

Solitaire

Yuliya Lierler and Marcello Balduccini

Yes

Yes

Search

NP

ASP-Core

view

27

Partner Units

Anna Ryabokon, Andreas Falkner and Gerhard Friedrich

Yes

No

Search

NP

-

view

27b

Partner Units - Polynomial

Anna Ryabokon, Andreas Falkner and Gerhard Friedrich

Yes

Yes

Search

P

ASP-Core

view

28

Weight-Assignment Tree

Yuliya Lierler

Yes

Yes

Search

NP

ASP-Core

view

30

Hydraulic Leaking

Francesco Calimeri

Yes

Yes

Search

P

ASP-Core

view

31

Hydraulic Planning

Francesco Calimeri

Yes

Yes

Search

P

ASP-Core

view

32

Stable Marriage problem

Francesco Ricca

Yes

Yes

Search

P

ASP-Core

view

33

Maze Generation

Martin Brain and Mario Alviano

Yes

Yes

Search

NP

ASP-Core

view