Innovating Works

TIN2016-76573-C2-2-P

Financiado
TASSAT 3: TEORIA Y APLICACIONES EN SATISFACTIBILIDAD Y OPTIMIZACION DE RESTRICCI...
ESTA PROPUESTA PROPONE UNA NUEVA COLABORACION ENTRE DOS EQUIPOS DE INVESTIGACION QUE AGRUPAN A INVESTIGADORES DE TRES UNIVERSIDADES DIFERENTES (UDL, UPC Y UPF). ES LA SECUELA DE UNA SERIE DE PROYECTOS (TASSAT 1 Y 2) CENTRADOS EN E... ESTA PROPUESTA PROPONE UNA NUEVA COLABORACION ENTRE DOS EQUIPOS DE INVESTIGACION QUE AGRUPAN A INVESTIGADORES DE TRES UNIVERSIDADES DIFERENTES (UDL, UPC Y UPF). ES LA SECUELA DE UNA SERIE DE PROYECTOS (TASSAT 1 Y 2) CENTRADOS EN EL PROBLEMA DE LA SATISFACTIBILIDAD DE VARIOS FORMALISMOS DE LA LOGICA, INCLUYENDO LA LOGICA PROPOSICIONAL (SAT), LA SATISFACCION DE RESTRICCIONES (CSP) Y SUS VARIANTES DE OPTIMIZACION. SAT ES UNO DE LOS PROBLEMAS MAS INTENSAMENTE ESTUDIADOS EN CIENCIAS DE LA COMPUTACION Y, SU GENERALIZACION, CSP, CONSTITUYE UNO DE LOS PRINCIPALES TEMAS DE INVESTIGACION EN VARIAS AREAS, INCLUYENDO LA INTELIGENCIA ARTIFICIAL, DONDE LAS REVISTAS INTERNACIONALES (COMO 'CONSTRAINTS') Y CONFERENCIAS (COMO 'CONSTRAINT PROGRAMMING ') ESTAN DEDICADOS ESPECIFICAMENTE AL TEMA.ESTAMOS BUSCANDO FONDOS PARA CONTINUAR Y SEGUIR DESARROLLANDO ESTE PROGRAMA DE INVESTIGACION, QUE, AL IGUAL QUE EN EL PROYECTO ANTERIOR, TENDRA EN SU NUCLEO LAS TRES PRINCIPALES AREAS DE ESPECIALIZACION DE LOS GRUPOS INVOLUCRADOS: IDENTIFICACION Y CLASIFICACION DE SUBCASOS PARA SAT Y CSP QUE PUEDEN SER EFICIENTEMENTE SOLUCIONABLES, EL DESARROLLO DE RESOLUTORES EFICIENTES PARA PROBLEMAS REALES, Y EL ESTUDIO DE LA COMPLEJIDAD COMPUTACIONAL PARA SAT Y OTROS PROBLEMAS COMBINATORIOS; TODOS TEMAS DE MAYOR INTERES. EN PARTICULAR, LA PROPUESTA TIENE LOS SIGUIENTES OBJETIVOS:-EL ESTUDIO DEL PROBLEMA DE OPTIMIZACION MIN CSP QUE CONSISTE EN LA BUSQUEDA DE UNA ASIGNACION QUE MINIMIZA EL NUMERO DE RESTRICCIONES INSATISFECHAS. ESTA ES UNA DE LAS VARIANTES DE OPTIMIZACION MAS NATURALES Y ESTUDIADAS DE CSP. EN PARTICULAR, TENEMOS LA INTENCION DE COMBINAR LOS ENFOQUES HABITUALES DEL PROBLEMA (COMBINATORIO Y ANALITICO) CON METODOS ALGEBRAICOS PARA ESTUDIAR Y CLASIFICAR EL GRADO DE APROXIMACION DE MIN CSPS.- EN EL CONTEXTO DE LA COMPLEJIDAD DE DEMOSTRACIONES (PROOF COMPLEXITY), NUESTRO TRABAJO SE CONSTRUIRA SOBRE LOS RESULTADOS OBTENIDOS SOBRE EL ISOMORFISMO DE GRAFOS EN LOS PROYECTOS ANTERIORES A ESTE. EL ISOMORFISMO DE GRAFOS ES UNO DE LOS PROBLEMAS MAS ESTUDIADOS EN LA TEORIA DE LA COMPLEJIDAD. DE HECHO, EL RECIENTE ALGORITMO QUASIPOLINOMICO DE LAZLO BABAI ES AMPLIAMENTE CONSIDERADO COMO EL RESULTADO TEORICO MAS IMPORTANTE DE LA DECADA. NUESTRO OBJETIVO ES HACER CONTRIBUCIONES IMPORTANTES AL ESTUDIO DEL ISOMORFISMO GRAFICO A TRAVES DE LAS LENTES DE LA COMPLEJIDAD DE DEMOSTRACIONES.-AL IGUAL QUE EN LOS PROYECTOS ANTERIORES, VAMOS A CONTINUAR CON NUESTRO ENFASIS EN EL DESARROLLO DE TECNICAS DE RESOLUTORES EFICIENTES, PRINCIPALMENTE UNA NUEVA GENERACION DE RESOLUTORES DE MAXSAT INCOMPLETOS. NUESTRO PUNTO DE PARTIDA SON LOS RESOLUTORES EXACTOS O COMPLETOS DE MAXSAT QUE HEMOS DESARROLLADO PARA TASSAT 2. NUESTRA VIA DE INVESTIGACION ES EL ESTUDIO DE COMO EXTENDER O RELAJAR ESTOS RESOLUTORES DE MANERA QUE PODAMOS OBTENER VERSIONES INCOMPLETAS EFICIENTES.-DESARROLLAREMOS NUEVAS FORMAS DE REDUCIR PROBLEMAS A MAXSAT. A LA VISTA DE LOS CASOS YA CONOCIDOS EN QUE, LA REDUCCION A SAT/MAXSAT PROPORCIONA LA ESTRATEGIA MAS EFICIENTE DE RESOLUCION, ESTA DIRECCION PARECE PROMETEDORA. -CONTINUAREMOS TRABAJANDO SOBRE LOS PROBLEMAS DE SELECCION AUTOMATICA Y CONFIGURACION AUTOMATICA DE ALGORITMOS, MEDIANTE LA APLICACION DE NUEVAS TECNICAS DE APRENDIZAJE AUTOMATICO Y ESTRATEGIAS DE TIMEOUT. FINALMENTE, TRABAJAREMOS EN LAS VERSIONES DISTRIBUIDAS DE NUESTROS ALGORITMOS DE CONFIGURACION AUTOMATICA. PTIMIZACIÓN DE RESTRICCIONES\COMPLEJIDAD COMPUTACIONAL\ALGORITMOS\LÓGICA PROPOSICIONAL\SATISFACCIÓN DE RESTRICCIONES ver más
01/01/2016
UDL
54K€
Perfil tecnológico estimado

Línea de financiación: concedida

El organismo AGENCIA ESTATAL DE INVESTIGACIÓN notifico la concesión del proyecto el día 2016-01-01
Presupuesto El presupuesto total del proyecto asciende a 54K€
Líder del proyecto
UNIVERSITAT DE LLEIDA CCT No se ha especificado una descripción o un objeto social para esta compañía.
Sin perfil tecnológico