# Presentation: 546443

## Parallel algorithms for discrete optimization

- Sebastian Ceria
- http://www.columbia.edu/~sc244
- Computational Optimization Research Center
- Columbia University
- joint with Gabor Pataki

- MetaNEOS meeting

## Mixed Integer Programming

- Optimization with discrete variables
- Wide variety of applications
- Very hard problems (lots of MIPs that we cannot solve with current technology)
- Faster and more powerful computers are needed
- Better algorithms have to be designed

- MetaNEOS meeting

## State-of-the-art

- Branch-and-bound (intelligent brute force)
- Some parallel implementations
- Require high-degree of coordination and synchronicity (Eckstein - Minto - Xpress)
- Branch-an-cut (improvement of the formulation + some brute force)
- Require dynamic creation of tasks but “little” coordination

- MetaNEOS meeting

## Mixed Integer Programs

- MetaNEOS meeting

## LP relaxation

- MetaNEOS meeting

## Cutting Plane Algorithm(Improve the formulation)

- Solve the LP
- relaxation

- Integral sol?

- Optimal
- solution
- found

- Generate
- cutting
- planes

- Add cuts
- to LP
- relaxation

- YES

- NO

- MetaNEOS meeting

## The LP relaxation

- MetaNEOS meeting

## x

*x*

- The optimal “fractional” solution

- MetaNEOS meeting

## A cutting plane

- MetaNEOS meeting

## The new fractional point

*x*

- MetaNEOS meeting

## An integral solution

*x*

- MetaNEOS meeting

## Disjunctive cuts

- Cutting planes are generated out of disjunctions in the problem
- For example, we can use the disjunction
- Or some other logical conditions for the problem

- MetaNEOS meeting

## The optimal “fractional” solution

- MetaNEOS meeting

## The disjunction

- MetaNEOS meeting

## x

*x*

- MetaNEOS meeting

## x

*x*

- MetaNEOS meeting

## x

*x*

- The union of the disjunctive sets

- MetaNEOS meeting

## x

*x*

- The convex-hull of the
- union of the disjunctive sets

- MetaNEOS meeting

## x

*x*

- One facet of the convex-hull
- but it is also a cut!

- MetaNEOS meeting

## x

*x*

- The new “feasible” solution!

- MetaNEOS meeting

## Cutting Plane Generation

- In order to generate (disjunctive) cuts, we need to solve a linear program
- We can generate many cutting planes in parallel (by using different disjunctions)
- Cutting planes provide new information which can be used to “enrich” the formulation (these cuts may not be essential for solving the problem)

- MetaNEOS meeting

## Branch-and-cut

- MetaNEOS meeting

## x

*x*

- The optimal “fractional” solution

- MetaNEOS meeting

## x

*x*

- One branch

- MetaNEOS meeting

## x

*x*

- The new “fractional” solution
- with

- MetaNEOS meeting

## x

*x*

- A cutting plane

- MetaNEOS meeting

## x

*x*

- The new “fractional” solution

- MetaNEOS meeting

## Solve LP relaxation

- Prune node?

- Subproblem is infeasible
- Solution is integer
**Solution is worse than **
**currently best available**

- Add global cuts

- Generate new cuts

- Choose local
- disjunctions

- Choose global
- disjunctions

- Generate
- subproblems

**Nodes**
**Cuts**
**Disjunctions**
**Current solution**

**Global resources**

- Choose local
- disjunction

- Generate cuts?

- Discard
- node

- YES

- YES

- NO

- NO

## Branching vs CuttingDisjunctions!  

- Divide the problem into two subproblems

- Generate cuts for the convex set:

- MetaNEOS meeting

## Branch-and-cut

- The problem is divided into subproblems (divide and conquer)
- Each subproblem is like a “new” integer program
- Each subproblem may generate new bounds, that can be used to “prune” other subproblems

- MetaNEOS meeting

## Each subproblem may generate cuts, that may be used by other subproblems   
The cutting planes are valid all over the search tree
Each subproblem may generate disjunctions
These disjunctions may be valid all over the search tree
Each subproblem may generate other subproblems

- The cutting planes are valid all over the search tree
- Each subproblem may generate disjunctions
- These disjunctions may be valid all over the search tree
- Each subproblem may generate other subproblems

- MetaNEOS meeting

## Metacomputing and MIP

**Nodes**
**Cuts**
**Disjunctions**
**Current solution**

**Global resources**

**Available **
**resources**

**MIP**

- MetaNEOS meeting

## Why do we need Metacomputing?

- Users provide us constantly with MIPs that cannot be solved with a single computer
- In many cases, we may want to try different strategies in parallel, because we do not know whether we will be able to solve the problem
- All the extra work that is done on a problem helps, we add new information that may help

- MetaNEOS meeting