Agostinho Agra
The robust vehicle routing problem with time windows
This work addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different robust approach. The first formulation extends the well-known resource inequalities formulation by employing robust programming with recourse. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The second formulation generalizes a path inequalities formulation to the uncertain context. The uncertainty appears implicitly in this formulation, so that we develop a new cutting plane technique for robust combinatorial optimization problems with complicated constraints. In particular, efficient separation procedures are discussed. We compare the two formulations on maritime transportation instances.
Joint work with: Marielle Christiansen, Rosa Figueiredo, Lars Magnus Hvattum, Michael Poss, Cristina Requejo.
Joint work with: Marielle Christiansen, Rosa Figueiredo, Lars Magnus Hvattum, Michael Poss, Cristina Requejo.
Enide Martins
Laplacian eigenvalues of caterpillars
A caterpillar is a tree of order greater or equal than 5 such that removing all the pendant vertices produces a path with at least two vertices. We characterize the Laplacian eigenvalues of caterpillars by means of the eigenvalues of its line graph using the concept of generalized composition.
Joint work with: D. M. Cardoso, M. A. A. de Freitas, M. Robbiano and B. San Martín.
Joint work with: D. M. Cardoso, M. A. A. de Freitas, M. Robbiano and B. San Martín.
Alexander Plakhov
Problems of optimal resistance in Newtonian aerodynamics
A rigid body moves in a rarefied medium of resting particles and at the same time very slowly rotates (somersaults). Each particle of the medium is reflected elastically when hitting the body boundary (multiple reflections are possible). The resulting resistance force acting on the body is time-dependent; we consider the time-averaged value of resistance. The problem is: given a convex body, find a roughening of its surface that minimizes or maximizes its resistance. (The problem includes mathematical definition of roughening.) This problem is solved using the methods of billiard theory and
optimal mass transportation. Surprisingly, the minimum and maximum depend only on the dimension of the ambient Euclidean space and do not depend on the original body. In particular, the resistance of a 3-dimensional convex body can be decreased by (approx.) 3.05% at most and can be increased at most twice by roughening.
optimal mass transportation. Surprisingly, the minimum and maximum depend only on the dimension of the ambient Euclidean space and do not depend on the original body. In particular, the resistance of a 3-dimensional convex body can be decreased by (approx.) 3.05% at most and can be increased at most twice by roughening.
Tatiana Tchemisova
On a constructive approach to optimality conditions for optimization problems with infinite constraint sets
We consider problems of convex Semi-Infinite and Semidefinite Programming. In the study of this problems, we apply the reduction approach suggested in our recent papers and based on the notions of immobile indices and their immobility orders (SIP) and subspace of immobile indices (SDP). The main results consist in new optimality conditions that do not use constraint qualifications (CQ), and have the form of criteria for some classes of problems. The constructive algorithms that are developed for implementation of our approach permit also to study regularity of any problem. The comparison of the new optimality conditions obtained with other known results permits to conclude that the results obtained are as good as the best known results in the case of regular problems and are more strong in the irregular case.
