An integer linear programming approach for bilinear integer programming

We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear P. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems. (C) 2011 Elsevier B.V. All rights reserved.

Audição e linguagem em crianças deficientes auditivas implantadas inseridas em ambiente bilíngue: um estudo de casos

O implante coclear (IC) tem sido indicado para crianças deficientes auditivas de grau severo e/ou profundo que não tem benefício com o aparelho de amplificação sonora individual (AASI), e que apresentem família adequada e motivada para o uso do dispositivo, bem como condições adequadas de reabilitação na cidade de origem. Atualmente, a procura pelo IC também ocorre por pais surdos, fluentes na Língua Brasileira de Sinais (LIBRAS), que recorrem a este tratamento para oferecer outra realidade para seus filhos. O ambiente destas crianças é bilíngue, dado pela LIBRAS dos pais e pela linguagem oral dos familiares próximos, do fonoaudiólogo e da escola. Neste sentido, o presente estudo visou acompanhar quatro crianças deficientes auditivas implantadas, sendo duas crianças filhas de pais deficientes auditivos fluentes na LIBRAS (expostas a ambiente bilíngue) e duas crianças filhas de pais sem alterações auditivas (expostas a ambiente oral). Para tanto, as habilidades de audição e de aquisição da linguagem oral foram comparadas nas quatro crianças implantadas. Foi possível observar que as quatro crianças apresentaram habilidades auditivas e de linguagem semelhantes ao longo do primeiro ano de uso do IC. Contudo, a partir disto, as crianças inseridas em ambiente bilíngue apresentaram melhor desempenho auditivo e linguístico, comparado ao desenvolvimento das outras crianças. As crianças inseridas em ambiente bilíngue podem se beneficiar do IC, desenvolvendo habilidades auditivas e de linguagem similares às das crianças inseridas em ambiente oral. Ressalta-se que os benefícios do dispositivo são obtidos a partir de aspectos multifatoriais, e estudos mais aprofundados são necessários.

Ablefaro macrostomia - síndrome e audição: relato de dois casos familiares

Introdução: Síndrome de Ablefaro MAcrostomia (AMS) é uma condição rara que compreende pálpebras ausentes ou curto, orelhas anormais, macrostomia, genitália anômalo, pele redundante e cabelos ausente. Brancati et al (2004) relataram uma ocorrência estimada de perda auditiva em 70% desta população. Estudos específicos sobre a audição em AMS não estavam presentes nos jornais que compilados. Relato dos casos: Paciente 1 é o primeiro filho de um ano de idade, a mãe 23 anos e pai de 25 anos de idade, não consangüíneos. Suas características clínicas são pouco cabelo no couro cabeludo, orelhas em forma de taça, raiz nasal larga, narinas antevertidas, macrostomia, os dedos com membranas, pele redundante e hipoplasia mamilos e lábios. Ela não tem atraso no desenvolvimento neuropsicomotor e a fala é normal. A audição foi avaliada aos 15 anos com uma perda auditiva em 6 kHz. Paciente 2 é o terceiro filho do mesmo casal. Ela tem falta grave das pálpebras, uma ponte nasal baixa com narinas hipoplásica e anteversão, macrostomia, orelhas anormalmente modelados, a ausência de mamilos, um de 6 cm onfalocele, ânus anteriormente localizado, hipoplasia dos grandes lábios, unhas hipoplasia, atenuação distal de falanges e pele redundante. Ela está se desenvolvendo com atraso no desenvolvimento neuropsicomotor, fala normal e perda auditiva condutiva leve bilateral. A avaliação audiológica incluiu quatro procedimentos: história clínica audiológica, inspeção otológica, imitanciometria, audiometria tonal e discurso. Conclusões: Os pacientes estudados com AMS apresentaram perda auditiva leve e esta perda de audição pode ser considerado como uma parte do fenótipo AMS sendo compatível os achados com a literatura.

Acceda y BuStreaming: integración de audio y vídeo en el proceso de autoarchivo del Repositorio de la ULPGC en acceso abierto

Comunicación presentada en 4 Jornadas "Os Repositorios" celebradas en la Universidad de Barcelona entre los días 3 al 5 de marzo del 2010. Estas Jornadas están organizadas conjuntamente por el CBUC, UB, UAB, UPC y UOC y el eje central de esta edición son las políticas de promoción del acceso abierto.Se recoge en la comunicación las últimas actuaciones que la Biblioteca Universitaria ha llevado a cabo para sumarse al movimiento Open Access y se presentan: Acceda, Documentación científica de la ULPGC en abierto y BUStreaming canal universitario de audio y video digital.

CoolBOT: a component-oriented programming framework for robotics

[EN] Programming software for controlling robotic systems in order to built working systems that perform adequately according to their design requirements remains being a task that requires an important development effort. Currently, there are no clear programming paradigms for programming robotic systems, and the programming techniques which are of common use today are not adequate to deal with the complexity associated with these systems. The work presented in this document describes a programming tool, concretely a framework, that must be considered as a first step to devise a tool for dealing with the complexity present in robotics systems. In this framework the software that controls a system is viewed as a dynamic network of units of execution inter-connected by means of data paths. Each one of these units of execution, called a component, is a port automaton which provides a given functionality, hidden behind an external interface specifying clearly which data it needs and which data it produces. Components, once defined and built, may be instantiated, integrated and used as many times as needed in other systems. The framework provides the infrastructure necessary to support this concept for components and the inter communication between them by means of data paths (port connections) which can be established and de-established dynamically. Moreover, and considering that the more robust components that conform a system are, the more robust the system is, the framework provides the necessary infrastructure to control and monitor the components than integrate a system at any given instant of time.

A Virtual Programming Lab for Moodle with automatic assessment and anti-plagiarism features

[EN] This paper describes VPL, a Virtual Programming Lab module for Moodle, developed at the University of Las Palmas of Gran Canaria (ULPGC) and released for free uses under GNU/GPL license. For the students, it is a simple development environment with auto evaluation capabilities. For the instructors, it is a students' work management system, with features to facilitate the preparation of assignments, manage the submissions, check for plagiarism, and do assessments with the aid of powerful and flexible assessment tools based on program testing, all of that being independent of the programming language used for the assignments and taken into account critical security issues.

Application-oriented Mixed Integer Non-Linear Programming

In the most recent years there is a renovate interest for Mixed Integer Non-Linear Programming (MINLP) problems. This can be explained for different reasons: (i) the performance of solvers handling non-linear constraints was largely improved; (ii) the awareness that most of the applications from the real-world can be modeled as an MINLP problem; (iii) the challenging nature of this very general class of problems. It is well-known that MINLP problems are NP-hard because they are the generalization of MILP problems, which are NP-hard themselves. However, MINLPs are, in general, also hard to solve in practice. We address to non-convex MINLPs, i.e. having non-convex continuous relaxations: the presence of non-convexities in the model makes these problems usually even harder to solve. The aim of this Ph.D. thesis is to give a flavor of different possible approaches that one can study to attack MINLP problems with non-convexities, with a special attention to real-world problems. In Part 1 of the thesis we introduce the problem and present three special cases of general MINLPs and the most common methods used to solve them. These techniques play a fundamental role in the resolution of general MINLP problems. Then we describe algorithms addressing general MINLPs. Parts 2 and 3 contain the main contributions of the Ph.D. thesis. In particular, in Part 2 four different methods aimed at solving different classes of MINLP problems are presented. Part 3 of the thesis is devoted to real-world applications: two different problems and approaches to MINLPs are presented, namely Scheduling and Unit Commitment for Hydro-Plants and Water Network Design problems. The results show that each of these different methods has advantages and disadvantages. Thus, typically the method to be adopted to solve a real-world problem should be tailored on the characteristics, structure and size of the problem. Part 4 of the thesis consists of a brief review on tools commonly used for general MINLP problems, constituted an integral part of the development of this Ph.D. thesis (especially the use and development of open-source software). We present the main characteristics of solvers for each special case of MINLP.

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

A study on set variable representations in constraint programming

Il lavoro presentato in questa tesi si colloca nel contesto della programmazione con vincoli, un paradigma per modellare e risolvere problemi di ricerca combinatoria che richiedono di trovare soluzioni in presenza di vincoli. Una vasta parte di questi problemi trova naturale formulazione attraverso il linguaggio delle variabili insiemistiche. Dal momento che il dominio di tali variabili può essere esponenziale nel numero di elementi, una rappresentazione esplicita è spesso non praticabile. Recenti studi si sono quindi focalizzati nel trovare modi efficienti per rappresentare tali variabili. Pertanto si è soliti rappresentare questi domini mediante l'uso di approssimazioni definite tramite intervalli (d'ora in poi rappresentazioni), specificati da un limite inferiore e un limite superiore secondo un'appropriata relazione d'ordine. La recente evoluzione della ricerca sulla programmazione con vincoli sugli insiemi ha chiaramente indicato che la combinazione di diverse rappresentazioni permette di raggiungere prestazioni di ordini di grandezza superiori rispetto alle tradizionali tecniche di codifica. Numerose proposte sono state fatte volgendosi in questa direzione. Questi lavori si differenziano su come è mantenuta la coerenza tra le diverse rappresentazioni e su come i vincoli vengono propagati al fine di ridurre lo spazio di ricerca. Sfortunatamente non esiste alcun strumento formale per paragonare queste combinazioni. Il principale obiettivo di questo lavoro è quello di fornire tale strumento, nel quale definiamo precisamente la nozione di combinazione di rappresentazioni facendo emergere gli aspetti comuni che hanno caratterizzato i lavori precedenti. In particolare identifichiamo due tipi possibili di combinazioni, una forte ed una debole, definendo le nozioni di coerenza agli estremi sui vincoli e sincronizzazione tra rappresentazioni. Il nostro studio propone alcune interessanti intuizioni sulle combinazioni esistenti, evidenziandone i limiti e svelando alcune sorprese. Inoltre forniamo un'analisi di complessità della sincronizzazione tra minlex, una rappresentazione in grado di propagare in maniera ottimale vincoli lessicografici, e le principali rappresentazioni esistenti.