Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model

Anurag Sharma, Dharmendra SHARMA

    Research output: A Conference proceeding or a Chapter in BookConference contribution

    3 Downloads (Pure)

    Abstract

    Many science and engineering applications require finding solutions to planning and optimization problems by satisfying a set of constraints. These constraint problems (CPs) are typically NP-complete and can be formalized as constraint satisfaction problems (CSPs) or constraint optimization problems (COPs). Evolutionary algorithms (EAs) are good solvers for optimization problems ubiquitous in various problem domains. A variation of EA - Intelligent constraint handling evolutionary algorithm (ICHEA) has been demonstrated to be a versatile constraints-guided EA for all forms of continuous constrained problems in our earlier works. In this paper we investigate an incremental approach through ICHEA in solving benchmark exam timetabling problems which is a classic discrete COP and compare its performance with other well-known EAs. Incremental and exploratory search in constraint solving has shown improvement in the quality of solutions.
    Original languageEnglish
    Title of host publication26th Australasian Joint Conference on Artificial Intelligence (AI 2013)
    EditorsStephen Cranefield, Abhaya Nayak
    Place of PublicationBerlin/Heidelberg
    PublisherSpringer
    Pages196-201
    Number of pages6
    Volume8272
    ISBN (Print)9783319036793
    DOIs
    Publication statusPublished - 2013
    Event26th Australasian Joint Conference on Artificial Intelligence (AI 2013) - Dunedin, Dunedin, New Zealand
    Duration: 6 Dec 2013 → …

    Conference

    Conference26th Australasian Joint Conference on Artificial Intelligence (AI 2013)
    CountryNew Zealand
    CityDunedin
    Period6/12/13 → …

    Fingerprint

    Evolutionary algorithms
    Constraint satisfaction problems
    Planning

    Cite this

    Sharma, A., & SHARMA, D. (2013). Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model. In S. Cranefield, & A. Nayak (Eds.), 26th Australasian Joint Conference on Artificial Intelligence (AI 2013) (Vol. 8272, pp. 196-201). Berlin/Heidelberg: Springer. https://doi.org/10.1007/978-3-319-03680-9_21
    Sharma, Anurag ; SHARMA, Dharmendra. / Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model. 26th Australasian Joint Conference on Artificial Intelligence (AI 2013). editor / Stephen Cranefield ; Abhaya Nayak. Vol. 8272 Berlin/Heidelberg : Springer, 2013. pp. 196-201
    @inproceedings{121e2b790741490ba0dd7b72e815ee63,
    title = "Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model",
    abstract = "Many science and engineering applications require finding solutions to planning and optimization problems by satisfying a set of constraints. These constraint problems (CPs) are typically NP-complete and can be formalized as constraint satisfaction problems (CSPs) or constraint optimization problems (COPs). Evolutionary algorithms (EAs) are good solvers for optimization problems ubiquitous in various problem domains. A variation of EA - Intelligent constraint handling evolutionary algorithm (ICHEA) has been demonstrated to be a versatile constraints-guided EA for all forms of continuous constrained problems in our earlier works. In this paper we investigate an incremental approach through ICHEA in solving benchmark exam timetabling problems which is a classic discrete COP and compare its performance with other well-known EAs. Incremental and exploratory search in constraint solving has shown improvement in the quality of solutions.",
    keywords = "Constraint satisfaction problems, ICHEA, Evolutionary algorithms, Constraint optimization problems",
    author = "Anurag Sharma and Dharmendra SHARMA",
    year = "2013",
    doi = "10.1007/978-3-319-03680-9_21",
    language = "English",
    isbn = "9783319036793",
    volume = "8272",
    pages = "196--201",
    editor = "Stephen Cranefield and Abhaya Nayak",
    booktitle = "26th Australasian Joint Conference on Artificial Intelligence (AI 2013)",
    publisher = "Springer",
    address = "Netherlands",

    }

    Sharma, A & SHARMA, D 2013, Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model. in S Cranefield & A Nayak (eds), 26th Australasian Joint Conference on Artificial Intelligence (AI 2013). vol. 8272, Springer, Berlin/Heidelberg, pp. 196-201, 26th Australasian Joint Conference on Artificial Intelligence (AI 2013), Dunedin, New Zealand, 6/12/13. https://doi.org/10.1007/978-3-319-03680-9_21

    Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model. / Sharma, Anurag; SHARMA, Dharmendra.

    26th Australasian Joint Conference on Artificial Intelligence (AI 2013). ed. / Stephen Cranefield; Abhaya Nayak. Vol. 8272 Berlin/Heidelberg : Springer, 2013. p. 196-201.

    Research output: A Conference proceeding or a Chapter in BookConference contribution

    TY - GEN

    T1 - Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model

    AU - Sharma, Anurag

    AU - SHARMA, Dharmendra

    PY - 2013

    Y1 - 2013

    N2 - Many science and engineering applications require finding solutions to planning and optimization problems by satisfying a set of constraints. These constraint problems (CPs) are typically NP-complete and can be formalized as constraint satisfaction problems (CSPs) or constraint optimization problems (COPs). Evolutionary algorithms (EAs) are good solvers for optimization problems ubiquitous in various problem domains. A variation of EA - Intelligent constraint handling evolutionary algorithm (ICHEA) has been demonstrated to be a versatile constraints-guided EA for all forms of continuous constrained problems in our earlier works. In this paper we investigate an incremental approach through ICHEA in solving benchmark exam timetabling problems which is a classic discrete COP and compare its performance with other well-known EAs. Incremental and exploratory search in constraint solving has shown improvement in the quality of solutions.

    AB - Many science and engineering applications require finding solutions to planning and optimization problems by satisfying a set of constraints. These constraint problems (CPs) are typically NP-complete and can be formalized as constraint satisfaction problems (CSPs) or constraint optimization problems (COPs). Evolutionary algorithms (EAs) are good solvers for optimization problems ubiquitous in various problem domains. A variation of EA - Intelligent constraint handling evolutionary algorithm (ICHEA) has been demonstrated to be a versatile constraints-guided EA for all forms of continuous constrained problems in our earlier works. In this paper we investigate an incremental approach through ICHEA in solving benchmark exam timetabling problems which is a classic discrete COP and compare its performance with other well-known EAs. Incremental and exploratory search in constraint solving has shown improvement in the quality of solutions.

    KW - Constraint satisfaction problems

    KW - ICHEA

    KW - Evolutionary algorithms

    KW - Constraint optimization problems

    U2 - 10.1007/978-3-319-03680-9_21

    DO - 10.1007/978-3-319-03680-9_21

    M3 - Conference contribution

    SN - 9783319036793

    VL - 8272

    SP - 196

    EP - 201

    BT - 26th Australasian Joint Conference on Artificial Intelligence (AI 2013)

    A2 - Cranefield, Stephen

    A2 - Nayak, Abhaya

    PB - Springer

    CY - Berlin/Heidelberg

    ER -

    Sharma A, SHARMA D. Constraint Optimization for Timetabling Problems using a Contraint Driven Solution Model. In Cranefield S, Nayak A, editors, 26th Australasian Joint Conference on Artificial Intelligence (AI 2013). Vol. 8272. Berlin/Heidelberg: Springer. 2013. p. 196-201 https://doi.org/10.1007/978-3-319-03680-9_21