Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
is to contribute with the state-of-the-art in linear optimization methodologies
Marcos Arenales (supervisor) and Jacek Gondzio (co-supervisor)
Theory and methods related
to minimizing (or maximizing)
a given linear function
Committee members
The domain is fully described by a set of linear equations or inequalities
They are also widely used, with the additional advantage of being applied to nonlinear problems.
Friends and colleagues from the Opt Lab (LOt) and from the University of Edinburgh
a broader range of models, which includes quadratic, logarithmic and convex functions.
Fapesp (Sao Paulo Research Foundation)
"one of the ten most influential algorithms to sciences and engineering"
Currently, they are the only methodologies which are able to find optimal solutions of important problems in manufacturing and logistics
CAPES Foundation
"it is called around thousands of times per second around the world"
Audience
The variables
may assume
fractional values
The variables are required to assume integer values
Information systems are able to
We have presented theoretical and computational developments with the aim of contributing with the state-of-the-art in linear optimization
execute very difficult tasks
By exploiting new strategies and combining different types of methods, we have obtained improvements for
Advances in hardware
and software
Theoretical developments
in mathematics, physics, ...
This research involved the study of different types of theoretical subjects and computational methods, which are usually treated separately in the literature
Pedro Augusto Munari Junior
Advisor: Marcos Arenales
Co-advisor: Jacek Gondzio
The branch-price-and-cut method has been widely used for solving integer programming problems
Reductions in the number of nodes, number of valid inequalities and CPU time
We propose to use the
For the VRPTW, the IPBPC achieves the best overall performance when compared to a simplex-based BPC
within the branch-price-and-cut method
Interior point methods can be useful to improve the performance of the branch-price-and-cut methods
We present how to modify each core component of a BPC
in order to take advantage of well-centered suboptimal solutions
Promising computational results:
Next steps:
very successful in many fields related to LP;
In the vast majority of branch-price-and-cut implementations
however, they do not seem to have made a
big impact in the integer programming context;
The primal-dual interior point algorithm will be used to provide well-centered, suboptimal solutions to
Hence, the generation of columns and valid inequalities are based on optimal solutions which are extreme points
adversely affect the performance of the column generation;
First proposals by Mitchell and his collaborators
deeper valid inequalities by using non-optimal solutions;
Mitchell and Todd (1992): primal projective IPM + cutting plane method
Borchers and Mitchell (1992): primal-dual IPM + branch-and-bound
Mitchell and Borchers (1996), Mitchell (2000): primal-dual IPM + cutting plane
Mitchell (1997): primal-dual IPM + Gomory cuts
du Merle (1999), Elhedhli and Goffin (2004): ACCPM within the branch-and-price
More stable primal and dual solutions;
Some of the earlier investigations were not successful, specially due to the lack of efficient warmstarting techniques
Deeper columns and cuts;
Speed up the solution times;
Solve a sequence of closely-related LP problems
Never been reported in the literature
Several challenging issues are involved when using this algorithm within a full branch-price-and-cut framework
The BPC has been widely used for solving integer programming models in which a special structure can be identified in the coefficient matrix
It is not just replacing a simplex-type method
After adding the valid inequalities, the RMP becomes
heuristics in the pricing subproblem;
looser optimality tolerance;
The oracle decides if it is a good time to call either the pricing subproblem or the separation subproblem
avoid solving the problem to optimality;
deeper cuts;
The additional constraints lead to new dual variables, which may adversely affect the performance of the pricing subproblem solver
In both cases: well-centered suboptimal solutions
Valid inequalities are generated at fractional solutions of the RMP by calling a
With this, we hope to reduce the number of generated valid inequalities
use the optimal solution to generate cuts
we propose to use suboptimal well-centered solutions in the separation subproblem as well!
University of São Paulo, Brazil
Primal-dual interior point method:
HOPDM (library)
Efficient warmstarting procedures
Instances: Solomon (1987)
100 customers: 100-series, 200-series
The IPBPC performance is compared to a similar BPC which is based on the simplex algorithm
Computational implementation in C
São Carlos, 31-1-13
Perturbed optimality conditions
New developments in theory
and applications of the PDCGM
Simplex-type methods are widely used nowadays
The method relies on the interior point method
to obtain
of the restricted master problems
We address a variant of the dual simplex method
This study extends earlier investigations:
New theoretical study which shows that the PDCGM converges to an optimum of the master problem
Column generation plays an
important role in optimization
Extensive computational experiments with linear relaxations of
integer programming, nonlinear programming,
non-differentiable optimization
exact approaches for solving problems such as the cutting stock problem and the vehicle routing problem
We address a variant of the CG method
which uses the
to solve the restricted master problems:
Further developments:
We present a theoretical analysis of the method
and an extensive computational study based on linear relaxations of classical integer programming problems
Further studies:
If the primal basic solution is infeasible,
then we can make a basis change in order
to improve the value of the objective function
Algorithm 7: The primal-dual column generation method
We stated the ratio test in a way that the no dual component could change its sign after the basis change
dual feasible set
0
745,991
3
2512.25
Failures:
1,077,820
Iterations:
5403.80
(number of bounded constraints in the general form)
CPU time:
Largest m
Best performance: Iterations
To work well in practice, the dual simplex method must be implemented by following certain computational techniques which are essential in efficient and stable implementations
Best performance: CPU time
0
745,991
0
2512.25
750,967
0
2768.65
Failures:
1,852,357
Iterations:
6399.31
CPU time:
2.8x faster than the SCGM
2.6x faster than the ACCPM
PDCGM with k = 200 has the
best overall performance:
1.6x faster than the SCGM with k=300
4.5x faster than the ACCPM with k = 100
Optimal solutions (extreme points) provided by the simplex method from CPLEX solver
Well-centered suboptimal solutions provided by the PDIPM from HOPDM solver
On top of OBOE/COIN-OR solver
PDCGM with k = 10 has the
best overall performance:
2.8x faster than the SCGM with k=50
8.9x faster than the ACCPM with k = 10