Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Transcript

The aim of this research

A few acknowledgments...

Linear optimization

The best proportion of

ingredients in a blending

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

Interior point method

The domain is fully described by a set of linear equations or inequalities

The best way to invest your money

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.

Simplex method

Column generation

Fapesp (Sao Paulo Research Foundation)

"one of the ten most influential algorithms to sciences and engineering"

(Dongarra and Sullivan, 2000)

Currently, they are the only methodologies which are able to find optimal solutions of important problems in manufacturing and logistics

Best way to deliver goods

Best regions for setting a distribution center

CAPES Foundation

"it is called around thousands of times per second around the world"

Linear optimization

(Elwes, 2012)

Branch-and-price

Audience

Linear

programming

Integer programming

The variables

may assume

fractional values

The variables are required to assume integer values

Conclusion

Motivation

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

simplex-type methods

branch-price-and-cut

Suggesting a disease treatment

column generation

Advances in hardware

and software

Theoretical developments

in mathematics, physics, ...

Find the best timetable for a public transportation system

This research involved the study of different types of theoretical subjects and computational methods, which are usually treated separately in the literature

Forecasting a natural disaster

Theoretical and computational issues for improving the performance of linear optimization methods

We have put together different subjects with the purpose of exploiting the strength of each one

We believe the obtained results contribute with the Computer Science and Operations Research areas, which has a positive impact to our society

Concluding remarks

Pedro Augusto Munari Junior

Advisor: Marcos Arenales

Co-advisor: Jacek Gondzio

Integration of the primal-dual interior point algorithm and the branch-price-and-cut method

Outline

Concluding remarks

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

Outline

We propose to use the

For the VRPTW, the IPBPC achieves the best overall performance when compared to a simplex-based BPC

  • Briefly describe the main linear programming methodologies:

primal-dual interior point algorithm

within the branch-price-and-cut method

Main contributions

Interior point methods can be useful to improve the performance of the branch-price-and-cut methods

  • primal simplex method
  • dual simplex method
  • primal-dual interior point method

It requires a change of strategy!

We present how to modify each core component of a BPC

  • Review the main linear programming methodologies

  • A theoretical framework to address simplex type methods and interior point methods uniformly

  • Review the warmstarting techniques for interior point methods

Interior point methods can and should be used within integer programming methodologies

in order to take advantage of well-centered suboptimal solutions

Promising computational results:

  • Introduce a unifying framework to describe these linear programming methodologies
  • Vehicle routing problem with time windows (VRPTW)

2

5

Next steps:

  • Improve the implementation of the pricing subproblem solver
  • Solve other integer programming problems

The interior point branch-price-and-cut method

Interior point methods

Linear programming

Branch-price-and-cut

very successful in many fields related to LP;

In summary

In the vast majority of branch-price-and-cut implementations

a simplex-type method is used to solve the LP problems

however, they do not seem to have made a

big impact in the integer programming context;

(several reasons: historical, reoptimization, replacing the simplex, ...)

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

Interior point methods + integer programming methodologies

Column generation

adversely affect the performance of the column generation;

First proposals by Mitchell and his collaborators

Branching

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

Cut generation

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;

A scenario that has changed in the last years

Speed up the solution times;

Solve a sequence of closely-related LP problems

Interior point methods + branch-price-and-cut method

Never been reported in the literature

Several challenging issues are involved when using this algorithm within a full branch-price-and-cut framework

Linear programming

methodologies

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

Branching

Change of strategy!

Rethink every piece of a standard BPC

Two steps

Column generation, valid inequalities, branching, ...

Cut generation: Valid inequalities

After adding the valid inequalities, the RMP becomes

heuristics in the pricing subproblem;

To quickly solve the MP, we use:

looser optimality tolerance;

But, by using a point in the interior of the feasible set:

Primal-dual column and cut generation

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;

Using the primal-dual interior point algorithm within the branch-price-and-cut method

The additional constraints lead to new dual variables, which may adversely affect the performance of the pricing subproblem solver

Hence, we should keep the number of valid inequalities small

In both cases: well-centered suboptimal solutions

Valid inequalities are generated at fractional solutions of the RMP by calling a

separation subproblem

With this, we hope to reduce the number of generated valid inequalities

Standard approach:

Thus...

use the optimal solution to generate cuts

we propose to use suboptimal well-centered solutions in the separation subproblem as well!

Simplex-type methods

Unified framework for linear programming

University of São Paulo, Brazil

Computational experiments

Primal simplex method

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

Desaulniers, Lessard and Hadjar. Transportation Science, 2008.

Vehicle routing problem with time windows

Dual simplex method

Impact of changes in the core components

Early branching threshold

CPU time (s)

Separation subproblem threshold

Primal-dual interior point method

São Carlos, 31-1-13

Perturbed optimality conditions

Number of valid inequalities

Number of nodes

CPU time (s)

Number of valid inequalities

100-series

Number of nodes

200-series

Concluding remarks

New developments in theory

and applications of the PDCGM

Outline

Simplex-type methods are widely used nowadays

  • Novel theoretical discussion, which extends previous studies
  • Main techniques that are required in efficient implementations
  • Computational results using the Netlib instances

well-centered suboptimal dual solutions

The method relies on the interior point method

to obtain

of the restricted master problems

We address a variant of the dual simplex method

  • It exploits special features of the general form
  • Instead of transforming the problem before solving it, we modify the simplex method

Outline

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

  • Arenales (1984), Sousa et al. (2005), Silva et al. (2007)

important role in optimization

  • Successfully applied to several contexts:

The DSMGF is competitive with the DSMSF and outperforms the PSMSF. It has the best relative performance in many of the most difficult instances.

Extensive computational experiments with linear relaxations of

integer programming, nonlinear programming,

non-differentiable optimization

  • Methodologies based on CG are the most efficient

classical integer programming problems

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:

Main contributions

primal-dual interior point algorithm

  • Well-centered dual solutions
  • Early termination (suboptimal solutions)

3

  • We describe the main techniques to have an efficient implementation of the method

  • We show how to update the primal and dual basic solutions

  • The performance of the method is verified by experiments using the Netlib instances.

By analyzing the results, PDCGM achieves the best overall performance when compared to SCGM and ACCPM

Further developments:

  • More stable approach than using extreme dual solutions
  • In general, reduces the CPU time and the number of iterations
  • The larger the instances the better the relative performance

Main contributions

4

We present a theoretical analysis of the method

  • Experiments with larger instances, in particular those arising from linear relaxations
  • Check the behavior within integer programming methodologies
  • Pricing rules, initial basis, ...

and an extensive computational study based on linear relaxations of classical integer programming problems

Further studies:

  • compare against advanced column generation variants (bundle, volume, ...)
  • warmstarting techniques
  • integer solutions!
  • Cutting stock problem (CSP),
  • Vehicle routing problem with time windows (VRPTW)
  • Capacitated lot sizing problem with setup times (CLSPST)

Dual simplex method for problems in the general form

Basic solutions

Dual formulation

The column generation method

Improving a basic solution

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

Primal-dual column generation

A dual simplex-type algorithm for problems in the general form

Centrality

The bound flipping ratio test

We stated the ratio test in a way that the no dual component could change its sign after the basis change

Distance to optimality

Convergence

However, the dual components corresponding to bounded primal constraints are free variables!

Suboptimal solutions

Using the primal-dual interior point algorithm within the column generation method

CG lower bound

?

Standard column generation

CG variants

RMP

dual feasible set

Column generation

Restricted master problem (RMP)

Master problem (MP)

Oracle/subproblem

Computational implementation and experiments

DSMGF-BFRT

X

0

DSMGF-SRT

745,991

3

(1.44)

2512.25

Failures:

1,077,820

(2.15)

Iterations:

5403.80

(number of bounded constraints in the general form)

CPU time:

Largest m

Implementation issues

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

  • Data structure to exploit sparsity

  • Representation of the basic matrix
  • LU factorization and LU update
  • We extend the techniques by Suhl & Suhl (1990, 1993)
  • Data structure

Computational experiments

DSMGF

X

Linear relaxations of three classical problems

0

DSMSF

X

745,991

0

PSMSF

(1.01)

2512.25

750,967

0

(1.10)

(2.48)

2768.65

Failures:

1,852,357

(2.55)

Iterations:

6399.31

  • Standard form: constraints are given by a set of equations
  • The three methods are implemented using the same core components
  • The DSMSF implementation also relies on a bound flipping ratio test

CPU time:

  • Solving linear systems by Forward Transformation (FTRAN) and Backward Transformation (BTRAN)

  • Scaling, tolerances, ...

44 additional instances

  • 11 challenging instances
  • replicated 5, 10, 15 and 20 times
  • n from 150 to 400

Capacitated lot sizing with

setup times (CLSPST)

2.8x faster than the SCGM

2.6x faster than the ACCPM

751 instances: Trigeiro et al. (1989)

Medium size instances

X3

X2

Computational experiments

X1

G

W

Small size instances

F

E

All instances

Netlib instances:

  • 109 instances (including Kennington)
  • Challenging for simplex type methods due to numerical stability issues
  • Instances from 27 x 32 up to 105,127 x 154,699

n = 100 (large)

k = 200

n = 50 (medium)

n = 25 (small)

First, we compare two variants of the DSMGF:

87 instances: Solomon (1987)

Vehicle routing problem with

time windows (VRPTW)

PDCGM with k = 200 has the

best overall performance:

k = 1

1.6x faster than the SCGM with k=300

4.5x faster than the ACCPM with k = 100

k = 200

k = 50

k = 300

  • DSMGF-SRT: standard ratio test
  • DSMGF-BFRT: bound flipping ratio test

k = 100

Three different CG variants

Then, we compare the best variant against standard simplex type methods:

  • Standard column generation method (SCGM)

Optimal solutions (extreme points) provided by the simplex method from CPLEX solver

  • PSMSF: primal simplex method for problems in the standard form
  • DSMSF: dual simplex method for problems in the standard form
  • Primal-dual column generation method (PDCGM)

Well-centered suboptimal solutions provided by the PDIPM from HOPDM solver

  • Analytic center cutting-plane method (ACCPM)

On top of OBOE/COIN-OR solver

k = 10

medium size (m from 200 to 555)

small size (m from 15 to 199)

k = 1

PDCGM with k = 10 has the

best overall performance:

k = 10

2.8x faster than the SCGM with k=50

8.9x faster than the ACCPM with k = 10

k=50

k=100

Cutting stock problem (CSP)

Learn more about creating dynamic, engaging presentations with Prezi