Ernesto Julián Goldberg Birgin.

Este projeto versa sobre aspectos teóricos, computacionais e aplicações de Otimização. O projeto tem como objetivo o desenvolvimento, análise teórica, implementação e aplicação de algoritmos para os diferentes aspectos da Otimização, com ênfase na Otimização Contínua. O projeto se apoia em aplicações com as quais a equipe está familiarizada. Enfatizam-se algoritmos com sólida base teórica, o que envolve a caracterização precisa dos problemas abordados, com implementação computacional cuidadosa e competitiva, e conexões com Engenharia e Ciências Aplicadas. A equipe do projeto atua no ambiente científico brasileiro há mais de 40 anos, e é sensível às novas tendências e às aplicações modernas da Otimização. Ao longo dos anos, a equipe tem realizado contribuições significativas nas áreas que envolvem métodos de decomposição, métodos quase-Newton, programação quadrática sequencial, métodos de Lagrangiano Aumentado, Restauração Inexata, problemas de grande porte, condições sequenciais de otimalidade, minimização sem derivadas, complexidade algorítmica, reconstrução de imagens e aprendizagem de máquina, entre outras. A experiência acumulada, assim como a incorporação e a renovação do time de pesquisadores no projeto, habilita a equipe a atacar problemas nos quais a função objetivo é difícil, impossível de avaliar, ou de existência questionável, o número de variáveis é enorme ou desconhecido e, finalmente, a incerteza se estende às restrições. A abordagem destes problemas exige necessariamente enfoques interdisciplinares e o impacto almejado é, ao mesmo tempo, científico, econômico e social.

Neste projeto, uma ampla gama de problemas de pesquisa operacional e otimização discreta é estudada com a finalidade de contribuir com abordagens e soluções inovadoras para os problemas de gestão da produção e cadeias de suprimentos. Os problemas a serem estudados neste Projeto Temático são divididos em: (A) problemas de corte, (B) problemas de empacotamento, (C) problemas de dimensionamento de lotes, (D) problemas de programação da produção, (E) problemas de roteamento, (F) problemas de localização e (G) a integração destes problemas. Além do estudo e desenvolvimento de modelos matemáticos relacionados a estes problemas, métodos de solução e algoritmos para resolvê-los serão desenvolvidos e seus desempenhos computacionais serão analisados. No projeto, visa-se também dar continuidade à integração e colaboração de grupos de pesquisadores de diferentes instituições interessados nestas pesquisas, assim como a formação de recursos humanos e a capacitação em pesquisa e desenvolvimento tecnológico. Pretende-se intensificar a cooperação entre o setor produtivo e a academia, com o desenvolvimento de estudos de caso nas empresas. Espera-se, com isso, possibilitar colaborações e parcerias no estudo destes problemas e no desenvolvimento de ferramentas computacionais para serem utilizadas na prática. A equipe deste projeto é formada por vários pesquisadores em diversos estágios de suas carreiras acadêmicas, desde alunos de pós-graduação e recém-doutores, até pesquisadores experientes. Este projeto é uma continuação de outros três Projetos Temáticos FAPESP, sendo o primeiro desenvolvido entre 2006 e 2010, o segundo entre 2010 e 2015 e o terceiro entre 2017 e 2023. Nos dois primeiros projetos foram estudados principalmente problemas em (A), (B), (C) e (D), bem como, algumas integrações destes problemas (G). No terceiro projeto, os problemas em (E) e (F) foram adicionados e o estudo das integrações entre os problemas foi intensificado.

Nosso grupo atua no ambiente científico brasileiro há 40 anos, e é sensível às novas tendências e às modernas aplicações da Otimização. Ao longo dos anos, este grupo, financiado por sucessivos projetos temáticos da FAPESP, tem realizado contribuições significativas nas áreas que envolvem métodos de decomposição, métodos quase-Newton, programação quadrática sequencial, métodos de Lagrangiano Aumentado, restauração inexata, problemas de porte enorme, condições sequenciais de otimalidade, minimização sem derivadas, complexidade algorítmica, reconstrução de imagens e aprendizagem de máquina, entre outras. A experiência acumulada nestes anos, assim como a incorporação e a renovação do time de pesquisadores no projeto, nos habilita a atacar problemas nos quais a função objetivo é difícil, impossível de avaliar, ou de existência questionável, o número de variáveis é enorme ou desconhecido e, finalmente, a incerteza se estende às restrições. A abordagem destes problemas exige necessariamente enfoques interdisciplinares e o impacto almejado é, ao mesmo tempo, científico, econômico e social.

Os problemas a serem estudados neste projeto temático podem ser divididos em: (A) problemas de corte; (B) problemas de empacotamento; (C) problemas de dimensionamento de lotes; (D) problemas de programação da produção; (E) problemas de roteamento; (F) problemas de localização e (G) a integração destes problemas. Além do estudo e desenvolvimento de modelos matemáticos relacionados a estes problemas, métodos de solução e algoritmos para resolvê-los serão desenvolvidos e seus desempenhos computacionais serão analisados. O projeto visa também dar continuidade à integração e colaboração de grupos de pesquisadores de diferentes instituições interessados nestes problemas, assim como a formação de recursos humanos e a capacitação em pesquisa e desenvolvimento tecnológico. Pretendemos intensificar a cooperação entre o setor produtivo e a academia, com o desenvolvimento de estudos de caso nas empresas. Esperamos, com isso, possibilitar colaborações e parcerias no estudo destes problemas e no desenvolvimento de ferramentas computacionais para serem utilizadas na prática. A equipe deste projeto é formada por vários pesquisadores em diversos estágios de suas carreiras acadêmicas, desde alunos de pós-graduação e recém-doutores, até pesquisadores experientes na pesquisa destes problemas. Observamos que este projeto é uma continuação de outros dois projetos temáticos FAPESP, sendo o primeiro desenvolvido entre 2006 e 2010 e o segundo entre 2010 e 2015. Nos projetos anteriores foram estudados principalmente problemas em (A), (B), (C) e (D), bem como, algumas integrações destes problemas.

O objetivo central deste projeto é o estudo abrangente dos principais tópicos da Otimização Contínua, incluindo tanto os avanços teóricos quanto o desenvolvimento de novos métodos computacionais, a implementação dos mesmos através de ?software" original e a aplicação destas técnicas à solução de problemas provenientes de outras disciplinas ou do ?mundo real" (aplicações a questões de natureza tecnológica).

Neste projeto procura-se desenvolver um software para minimizar funções sujeitas a restrições lineares de igualdade e desigualdade. O número de variáveis e o número de restrições serão grandes e, em geral, a matriz A que dene as restrições será esparsa. Serão avaliadas (1) uma abordagem de pontos interiores com métodos regiões de confiança de grande porte para globalização e (2) uma abordagem com regularização cúbica. Pretendemos ainda analisar a aplicabilidade destes métodos ao problema MPCC. O projeto aponta para a elaboração de um software em condições de representar o estado-da-arte nesta área.

A área de Ciência da Computação experimenta hoje um crescimento vertiginoso. Novidades tecnológicas surgem e tornam-se obsoletas em um ou dois anos de existência. Novas abordagens surgem com enorme rapidez. Tal desenvolvimento se dá por necessidades criadas em outras áreas do conhecimento de novas técnicas para resolver problemas cada vez mais complexos. Hoje em dia é impossível imaginar um pesquisador de qualquer área do conhecimento que possa desenvolver suas atividades sem o apoio de métodos, técnicas ou tecnologia desenvolvida por pesquisadores de Ciência da Computação. É evidente que os mais bem sucedidos avanços tecnológicos em Ciência da Computação estão fundamentados em resultados teóricos. Áreas como mineração de dados e reconhecimento de padrões, para citar apenas duas, têm seus métodos fortemente baseados em técnicas desenvolvidas em Teoria da Computação. Nosso objetivo neste projeto é o estudo de estruturas combinatórias e diversas formas de abordar problemas relacionados com tais estruturas: métodos algébricos, geométricos, probabilísticos, combinatórios, etc. Uma melhor compreensão destes objetos pode resultar em novas estratégias e algoritmos mais eficientes para resolver problemas a eles relacionados. A equipe proponente tem pesquisadores com grande experiência que cobrem uma ampla gama de subáreas de Teoria da Computação, permitindo uma maior sinergia para a solução dos problemas abordados. As principais contribuições esperadas neste projeto são a publicação de artigos científicos em conferências e periódicos bem estabelecidos, com alta circulação e de seletiva política editorial. Desejamos também intensificar o intercâmbio internacional do grupo e a formação de alunos nos vários níveis (de iniciação científica a pós-doutorandos). Pretendemos ainda, durante a execução do projeto, realizar uma Escola Avançada de Ciências na área de Teoria da Computação.

O foco desta proposta é a transferência de conhecimento matemático para outras áreas da ciência, tecnologia e indústria, por meio de um centro de pesquisa estruturado para esse fim. Todo o conhecimento matemático é, em última análise, aplicável. se não diretamente, por meio de outros conhecimentos. Em algumas áreas da matemática a aplicação é quase ime( Entretanto, a colocação em prática de tal aplicabilidade se encontra muitas vezes travada por tradições incorretas, academicismo mal direcionado e dificuldades operacionais. Nos últimos anos, o crescimento da ciência no Brasil, e da matemática em particular, foi notável. Entretanto, a aplicação tecnológica, muitas vezes medida pelas patentes registradas, não teve o mesmo sucesso. Para fechar essa lacuna é necessário a criação de estruturas institucionais que estabeleçam as pontes entre as ciências matemáticas e aplicações como um objetivo em si mesmo. Não se trata apenas de orientar os trabalhos teóricos a áreas "potencialmente aplicáveis", mas de avançar nas aplicações até as últimas consequências, isto é, sua efetiva implementação na indústria, em sentido amplo. Não é mais possível descansar na posição de que a aplicação é problema de outros. É, de fato, problema de todos e reflete o necessário comprometimento da ciência aplicada e pura com o progresso material e espiritual da sociedade. A estratégia do presente projeto envolve, em primeiro lugar, a aglutinação de grupos destacados nas áreas mais aplicáveis da matemática no Estado visando seu direcionamento para aplicações efetivas. Os grupos selecionados têm demonstrado sua excelência na atividade científica convencional, em primeiro lugar, e em muitos casos, em aplicações relevantes. No CEPID proposto os grupos participantes continuarão com sua atividade científica habitual, e, ao mesmo tempo, desenvolverão "Ações de Transferência" de acordo com o roteiro: 1) Teses de mestrado e doutorado necessariamente vinculadas com aplicações em sentido amplo, com co-orientação explícita de especialistas nesses setores. 2) Realização de pelo menos um Workshop anual de Transferência, onde participarão os membros do CEPID e representantes de indústrias, administração, serviços, setores educativo e tecnológico. 3) Visitas periódicas de membros do CEPID a instituições com potencial para aplicações relevantes. 4) Elaboração de uma publicação interna chamada em princípio "Transference experiences" visando a consolidação de uma publicação mais permanente.

Este projeto é continuação de projetos temáticos anteriores do mesmo grupo, coordenados pelo Prof. José Mario Martínez, o último dos quais se encerrou em 2011 (processo 2006/53768-0). Nesta nova etapa a coordenadora será a Prof. Sandra Augusta Santos, mas o Prof. Martínez continuará atuando na equipe. Tem como objetivo o desenvolvimento e a análise de algoritmos para os diferentes aspectos da Otimização, com ênfase na Otimização Contínua. O projeto se apoia em aplicações com as quais o grupo está familiarizado. Enfatizam-se algoritmos com sólida base teórica, o que envolve a caracterização precisa dos problemas abordados, com implementação computacional cuidadosa e competitiva, e conexões com Engenharia e Ciências Aplicadas.

Desenvolvimento, análise e implementação de algoritmos. Estudo de problemas de otimização de natureza discreta: sobre grafos, seqüências, empacotamento e cortes, escalonamento, redes e biologia computacional. Projeto de algoritmos de aproximação e de algoritmos exatos. Estudo da complexidade computacional e do limite de aproximabilidade de problemas de otimização combinatória.

O objetivo central deste projeto é o estudo abrangente dos principais tópicos da Otimização Contínua, incluindo tanto os avanços teóricos quanto o desenvolvimento de novos métodos computacionais, a implementação dos mesmos através de ?software" original e a aplicação destas técnicas à solução de problemas provenientes de outras disciplinas ou do ?mundo real" (aplicações a questões de natureza tecnológica).

Otimização Combinatória é a área que estuda métodos para encontrar pontos ótimos (máximo ou mínimo) de uma função definida sobre um certo domínio. Neste projeto estudamos o uso de técnicas de otimização para a solução de problemas de combinatória notadamente de quatro subáreas: problemas em grafos, problemas de combinatória assintótica, problemas de empacotamento e escalonamento e problemas de programação não linear.

Este projeto foi originado pela HP-Labs e pela HP-Brasil R&D, que contataram a Agência de Inovação da Universidade de São Paulo (USP). O objetivo do projeto é estudar e obter boas soluções para algumas variantes de problemas de job shop scheduling que ocorrem em PrintShop Providers na área de impressão da HP (imaging and printing group). O projeto se insere, portanto, no esforço de automação do processo de impressão digital da HP.

Neste Projeto Temático pretendemos estudar: (i) problemas de corte e empacotamento, (ii) problemas de dimensionamento de lotes e programação (scheduling), (iii) integração dos problemas de corte ou empacotamento em (i) com os problemas de dimensionamento de lotes ou programação em (ii). Este projeto é uma continuação de outro Projeto Temático FAPESP concluído em 2010, em que foram estudados principalmente problemas em (i), mas também alguns problemas integrando problemas de (i) e (ii). Os objetivos deste projeto incluem o estudo e a modelagem matemática destes problemas, o desenvolvimento de métodos de solução e algoritmos para resolvê-los, bem como a análise de seus desempenhos computacionais. Também são objetivos deste projeto promover a integração e colaboração de grupos de pesquisadores de diferentes instituições interessados nestes problemas, assim como a formação de recursos humanos e a capacitação em pesquisa e desenvolvimento tecnológico. É nossa preocupação neste projeto motivar a aproximação entre universidades e empresas, por meio do desenvolvimento de estudos de caso dos problemas aqui estudados nas empresas. Esperamos com isso possibilitar colaborações e parcerias no estudo destes problemas e no desenvolvimento de ferramentas computacionais para serem utilizadas na prática. A equipe deste projeto é formada por vários pesquisadores em diversos estágios de suas carreiras acadêmicas, desde alunos de pós-graduação e recém-doutores, até pesquisadores ativos e experientes na pesquisa destes problemas. Contaremos também com a colaboração de diversos pesquisadores do exterior especializados nestes temas.

O objetivo do presente projeto é desenvolver métodos computacionais de otimização. Pretendemos abordar todos os aspectos do desenvolvimento de métodos de otimização. Começaremos desenvolvendo a teoria que dá o embasamento teórico dos métodos e de sua convergência. No aspecto prático, pretendemos implementar algoritmos pertinentes para cada tipo de problema abordado, incluindo aqui problemas de grande porte que requerem o uso de estruturas de dados adequadas. Ademais, ainda do ponto de vista prático, o objetivo final é desenvolver software livre. O presente projeto encaixa-se nas áreas de Matemática, Computação e Software, qualificadas como estratégicas no Edital ao qual este projeto se destina, e tem duração prevista de 24 meses.

O objetivo do presente projeto é desenvolver métodos computacionais de otimização. Pretendemos abordar todos os aspectos do desenvolvimento de métodos de otimização. Começaremos desenvolvendo a teoria que dá o embasamento teórico dos métodos e de sua convergência. No aspecto prático, pretendemos implementar algoritmos pertinentes para cada tipo de problema abordado, incluindo aqui problemas de grande porte que requerem o uso de estruturas de dados adequadas. Ademais, ainda do ponto de vista prático, o objetivo final é desenvolver software livre.

O objeto central deste projeto temático consiste no estudo dos Problemas de Corte e Empacotamento (PCE), os quais abrangem uma
variedade de problemas de otimização combinatória caracterizados por uma estrutura comum que consiste em arranjar "itens dentro de um
objeto". Este arranjo, em sua versão mais concreta, pode definir o corte de peças em estoque para a produção de itens encomendados, como
também o empacotamento de caixas num contêiner. Apesar da enormidade de aplicações práticas desta "versão concreta", os problemas de corte
e empacotamento surgem naturalmente em "arranjos simbólicos" como subproblemas importantes no uso de recursos escassos, que formam a
essência dos problemas da pesquisa operacional, tais como seleção de projetos, dimensionamento de lotes, alocação de tarefas, etc.

A relevância dos PCE's advém do crescente estímulo que as indústrias, em geral, têm recebido para otimizar seus processos. Este estímulo
ocorre, entre outras causas, pela maior competitividade imposta pelas transformações que têm afetado a ordem econômica mundial. O Brasil se
alinha nesta tendência e experimenta profundas mudanças no seu setor produtivo no que tange à modernização de seus processos produtivos,
melhoria da qualidade de seus produtos e racionalização administrativa.

Neste projeto visa-se o desenvolvimento de modelos matemáticos de problemas oriundos de ambientes industriais de corte e empacotamento,
o desenvolvimento e/ou aperfeiçoamento de métodos de solução, o desenvolvimento de estudos computacionais, a identificação de novos
problemas práticos, bem como a revisão de problemas da literatura.

Estudos de Problemas de Corte e Empacotamento têm sido desenvolvidos por diversos pesquisadores em diferentes instituições de
ensino/pesquisa no estado de S. Paulo, seja de forma independente ou já em colaboração. Por meio do presente projeto, busca-se dar
continuidade à integração e/ou integrar novos grupos de pesquisadores neste tema, objetivando o inte

O objetivo deste projeto é a formulação, análise teórica, desenvolvimento e implementação de algoritmos para os problemas clássicos de otimização: programação linear e não linear, resolução de sistemas de equações lineares e não lineares, problemas de viabilidade convexa (ou seja resolução de sistemas de inequações convexas), problemas de complementaridade linear e não linear, problemas de equilíbrio geral, problemas de programação semi-definida e desigualdades variacionais. Outrossim, o núcleo abordará o estudo de técnicas de decomposição de descentralização para problemas estruturados, e o desenvolvimento de "software", apropriado para este tipo de problemas. Compete também ao núcleo a resolução de problemas práticos usando ferramentas típicas da otimização numérica.

Otimização Combinatória é a área da matemática que estuda métodos para encontrar pontos ótimos (máximo ou mínimo) de uma função definida sobre um certo domínio. Nos problemas desta área o domínio é finito, e os pontos podem ser enumerados. Entretanto, o número de pontos do domínio pode ser muito grande, inviabilizando uma abordagem que enumerasse todas as possibilidades. 

Diversos problemas práticos podem ser modelados como problemas de Otimização Combinatória. Tais aplicações práticas motivam o estudo de abordagens exatas e aproximadas para sua resolução, objeto principal de estudo neste projeto. Os problemas que estudaremos provêm de diversas áreas como Biologia Computacional, Escalonamento de Tarefas, Empacotamento, entre outros.

A equipe do projeto consiste de 14 pesquisadores que já interagem há algum tempo dos quais 5 são pesquisadores de instituições emergentes, que fizeram seus doutoramentos orientados por pesquisadores do IME-USP, instituição principal deste projeto. As instituições
envolvidas são a USP (através do IME e da Escola Politécnica), UFRJ, UECE, UFPE e UFMS.

Os objetivos deste projeto são o fortalecimento da colaboração existente entre os grupos de pesquisa envolvidos e a ampliação do
apoio aos doutores egressos da instituição, a fim de que possam continuar a desenvolver pesquisa de qualidade na área. Durante o
projeto pretendemos realizar oficinas semestrais de pesquisa, que visam a expor os alunos envolvidos a um ambiente de pesquisa
prolífero. Tais oficinas contarão com a participação de pesquisadores do país e do exterior que apresentarão palestras de seus trabalhos. Além disso, haverá também seções de problemas em aberto com a participação ativa dos estudantes. Ampliar esta interação é um dos principais objetivos deste projeto.

O objetivo central da pesquisa proposta é investigar objetos combinatórios relevantes à matemática discreta e à teoria da computação, dando especial ênfase a aspectos estruturais clássicos, algorítmicos e não-algorítmicos, e a aspectos envolvendo a complexidade dos objetos de interesse. Subtemas específicos de pesquisa: (i) problemas estruturais sobre grafos e matróides, (ii) combinatória extremal, probabilística e assintótica, (iii) pseudoaleatoriedade em combinatória e em teoria da computação, e (iv ) algoritmos sobre estruturas discretas e aplicações.

A pesquisa em métodos computacionais de otimização vem sendo desenvolvida no Departamento de Matemática Aplicada da Unicamp, sob a coordenação do responsável principal por este projeto, nos últimos 27 anos. A área de interesse do grupo é Otimização, nas suas três vertentes principais: Teoria sobre problemas e métodos, Implementação prática de Algoritmos e Aplicações. Neste projeto temático, a proposta consiste em dar continuidade a esse trabalho e ao projeto 2001/04597-4, com o mesmo título e o mesmo coordenador. O grupo está inserido no PRONEX de Otimização, atualmente em vigência.

In this project we plan to develop new approaches and algorithms to solve hard combinatorial optimization problems. Many of these problems have important applications in practice. For instance, many problems that arise in the design of VLSI circuits can be formulated as combinatorial optimization problems.

We are specially interested in packing problems. Such problems have been broadly investigated not only because of their interesting theoretical aspects, but also due to their many practical
applications, such as in cloth, glass, paper and wood industries. They also have applications in design of VLSI circuits, warehouse storage, newspapers paging, production of alcohol in the sugar cane industry, and in several other contexts.

In this project we intend to develop new algorithms for a variety of packing problems. All participants have ongoing experience on this
subject, and this project is a natural attempt to combine their skills to solve new hard problems.

O foco central desta proposta é a investigação de problemas de Otimização Discreta e Grafos, com ênfase em seus aspectos teóricos, algorítmicos e aplicados.

Nossa proposta é desenvolver pesquisa de primeira linha nesse tema, trazendo contribuições de caráter prático e teórico. A área de Otimização Discreta se situa na fronteira entre a Ciência da Computação, a Matemática e as Engenharias, ocupando um lugar de grande destaque na pesquisa científica que vem sendo conduzida no mundo todo.

Dentre os vários problemas de otimização discreta que investigaremos incluem-se: projetos de redes de telecomunicações (redes de fibra ótica para conexões de banda larga), projetos de computadores e de chips VLSI, roteamento ou escalonamento de veículos, empacotamento de caixas em contêineres, corte de barras e placas, seqüenciamento de genes e DNA, mineração de dados, compressão de dados, etc.

Neste REDE focaremos o estudo de técnicas para a solução de problemas como os descritos acima, implementação eficiente dessas técnicas para a solução de problemas reais, e pesquisas de caráter mais teórico na área de grafos e combinatória.

Na área de grafos, serão pesquisados problemas sobre determinadas classes de grafos, bem como o desenvolvimento de algoritmos para a solução de problemas clássicos nessas classes e a análise da complexidade computacional dos problemas abordados. Pesquisas na área de grafos aleatórios também serão conduzidas. Esta área encontra-se na interseção das áreas de teoria dos grafos, combinatória e teoria das probabilidades. Consideramos o estudo de diversos problemas combinatórios, incluindo aspectos probabilísticos e assintóticos. Estes problemas têm um papel fundamental na investigação sobre grafos aleatórios e pseudo-aleatórios, assim como na análise assintótica de algoritmos e outras estruturas combinatórias.

Esta REDE é constituída pelos seguintes projetos temáticos, conduzidos por 6 grupo de pesquisa.

Grupo G1: Algoritmos exatos baseados em pr

O objetivo deste projeto é a formulação, análise teórica, desenvolvimento e implementação de algoritmos para os problemas clássicos de otimização: programação linear e não linear, resolução de sistemas de equações lineares e não lineares, problemas de viabilidade convexa (ou seja resolução de sistemas de inequações convexas), problemas de complementaridade linear e não linear, problemas de equilíbrio geral, problemas de programação semi-definida e desigualdades variacionais. Outrossim, o núcleo abordará o estudo de técnicas de decomposição de descentralização para problemas estruturados, e o desenvolvimento de "software", apropriado para este tipo de problemas. Compete também ao núcleo a resolução de problemas práticos usando ferramentas típicas da otimização numérica.