Understanding Complexity in a Practical Combinatorial Problem Using Mathematical Programming and Constraint Programming

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2018

Autores

Beatriz Brito Oliveira (Autor) FEUP; Maria Antónia Carravilla (Autor) FEUP

Ata de Conferência Internacional

Título: OPERATIONAL RESEARCH

Páginas: 269-295

18th Congress of the Portuguese-Association-of-Operational-Research (APDIO)

Valenca, PORTUGAL, JUN 28-30, 2017

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00N-P78

DOI: 10.1007/978-3-319-71583-4_19

Abstract (EN): Optimization problems that are motivated by real-world settings are often complex to solve. Bridging the gap between theory and practice in this field starts by understanding the causes of complexity of each problem and measuring its impact in order to make better decisions on approaches and methods. The Job-Shop Scheduling Problem (JSSP) is a well-known complex combinatorial problem with several industrial applications. This problem is used to analyse what makes some instances difficult to solve for a commonly used solution approach - Mathematical Integer Programming (MIP) - and to compare the power of an alternative approach: Constraint Programming (CP). The causes of complexity are analysed and compared for both approaches and a measure of MIP complexity is proposed, based on the concept of load per machine. Also, the impact of problem-specific global constraints in CP modelling is analysed, making proof of the industrial practical interest of commercially available CP models for the JSSP.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 27