Navegando por Autor "Uchoa, Eduardo"

Filtrar resultados informando as primeiras letras
Agora exibindo 1 - 3 de 3
  • Nenhuma Miniatura Disponível
    Item
    Branch-and-cut and GRASP with hybrid local search for the multi-level capacitated minimum spanning tree problem.
    (2009) Uchoa, Eduardo; Toffolo, Túlio Ângelo Machado; Souza, Maurício Cardoso de; Martins, Alexandre Xavier
    We propose efficient algorithms to compute tight lower bounds and high quality upper bounds for the Multi-Level Capacitated Minimum Spanning Tree problem. We first develop a branch-and-cut algorithm for the problem. This algorithm is able to solve instances of medium size and to provide tight lower bounds for larger ones. We then use the branch-and-cut within GRASP to evaluate subproblems during the search. The computational experiments conducted have improved best known lower and upper bounds on benchmark instances
  • Nenhuma Miniatura Disponível
    Item
    Branch-and-cut and hybrid local search for themulti-level capacitated minimum spanning tree problem.
    (2012) Uchoa, Eduardo; Toffolo, Túlio Ângelo Machado; Souza, Maurício Cardoso de; Martins, Alexandre Xavier; Fukasawa, Ricardo
    We propose algorithms to compute tight lower boundsand high quality upper bounds (UBs) for the multilevelcapacitated minimum spanning tree problem. We firstdevelop a branch-and-cut algorithm, introducing somenew features: (i) the exact separation of cuts correspond-ing to some master equality polyhedra found in theformulation; (ii) the separation of Fenchel cuts, solvingLPs considering all the possible solutions restricted tosmall portions of the graph. We then use that branch-and-cut within a GRASP that performs moves by solvingto optimality subproblems corresponding to partial solu-tions. The computational experiments were conductedon 450 benchmark instances from the literature. Numer-ical results show improved best known (UBs) for almostall instances that could not be solved to optimality.
  • Nenhuma Miniatura Disponível
    Item
    Strong bounds with cut and column generation for class-teacher timetabling.
    (2012) Santos, Haroldo Gambini; Uchoa, Eduardo; Ochi, Luiz Satoru; Maculan Filho, Nelson
    This work presents an integer programming formulation for a variant of the ClassTeacher Timetabling problem, which considers the satisfaction of teacher preferences and also the proper distribution of lessons throughout the week. The formulation contains a very large number of variables and is enhanced by cuts. Therefore, a cut and column generation algorithm to solve its linear relaxation is provided. The lower bounds obtained are very good, allowing us to prove the optimality of previously known solutions in three formerly open instances.