welcome: please sign in

Upload page content

You can upload content for the page named below. If you change the page name, you can also upload content for another page. If the page name is empty, we derive the page name from the file name.

File to load page content from
Page name
Comment

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

Graph Colouring

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 and Maria Carmela Santoro

Yes

Yes

Search

P

ASP-Core

view

31

Hydraulic Planning

Francesco Calimeri and Maria Carmela Santoro

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

35

Incremental Scheduling

Marcello Balduccini and Yuliya Lierler

Yes

Yes

Search

NP

ASP-Core

view