Allan Sapucaia Barboza

• Abstract

  In this project, we study integer linear programing formulations and heuristics for geometric decomposition problems. In this context, geometric decomposition problems have the goal of covering, packing or partitioning a given region in the plane with objects of predetermined shapes in order to optimize a given objective function. One of the most studied geometric decomposition problems i…

  Geometric decomposition problems, BP.DD

• Abstract

  In this project, we study integer linear programming formulations and heuristics for the Minimum Convex Partition Problem. A convex partion with respect to a set $P$ of points in the plane is a planar division whose vertices are the points of $P$ and edges are a subset of the line segments with extreme points in P. The edges of the convex hull CH(P) of P define the unbounded face and all …

  Mininum convex partition problem, BP.MS

• Abstract

  In this project, we study integer linear programming formulations and heuristics for the Rectangle Escape Problems, that arise in integrated circuit design. Given a rectangular base board and components represented by rectangles with axes parallel to the board, we want to connect the components to the bus located in the board edges. This connection is made by projecting one of the compone…

  Mathematical models and algorithmic study for rectangle escape problems, BP.IC

(Only some records are available in English at this moment)

• Abstract

  The traveling salesman problem (TSP) can be described as: given a set of cities and travel costs between every pair of cities, a "salesman" wishes to visit every city exactly once, and then return to the starting city, in the shortest possible total cost. The goal of this project is to study and compare the strength of two hierarchies of successively tighter lower bounds for the TSP: Appr…

  Computational experiments for mixed-integer programming, BE.EP.IC