# Presentation: 710389

## FATCOP: A Mixed Integer Program Solver

- Michael Ferris		Qun Chen
- University of Wisconsin-Madison
- Jeffrey Linderoth
- Argonne National Laboratories

## MIP formulation

- minimize	       cTx
- subject to	       Ax  b
- 	               l  x  u
- and  some      xj  integer

- Problems are specified by application
- convenient format - GAMS, AMPL, or MPS

## Branch-and-Bound Algorithm

- Integer
- infeasible

- Integer feasible
- incumbent = Z

- LP relaxation
- Zlp > Z

- LP
- infeasible

## The “Seymour Problem”

- Set covering problem used in proof of four color theorem
- CPLEX 6.0 and Condor (2 option files)
- Running since June 23, 1999
- Currently >340 days CPU time per job
- (7.9 million nodes; 1.5 million nodes)

## FAT COP

- FAT - large # of processors
- opportunistic environment (Condor)
- COP - Master Worker control
- fault tolerant: task exit, host suspend
- portable parallel programming
- Mixed Integer Program Solver
- Branch and Bound: LP relaxations
- MPS file, AMPL or GAMS input

## Condor and PVM

## Condor Pool

- master

-  worker

- INTERNET

## Application Problem

- LPSOLVER INTERFACE

## Operation

- Setup

- Create
- Work Pool

- Request Host

- Host Add

- Sub Solved

- Error

- Receive
- Solve
- Report

- Send Data
- Send Problem
- Request Host

- Clean Up
- Problem

- Remove Prob
- Update Pool
- Send New
- Problem

## FATCOP: Single Job

##       Master

- solution

- Message queue

- Host suspend

-      ** ****Master**

- Host deletion

- Task exit

- Host add

- Host resume

- .
- .
- .

- .
- .
- .

**Condor pool**

- MIP data
- subproblem

**Condor Central Manager **

**worker**

- Select machines

**worker**

**worker**

- Host add requests

## FATCOP Daily Log

## FATCOP Weekly Log

## FATCOP Monthly Log

## MIP Technology

- Each task is a subtree, time limit
- Diving heuristic
- Cutting planes (global)
- Pseudocosts
- Preprocessing
- Master checkpoint
- Worker has state, how to share info?

## Slide 16

## TEST on MIPLIB problems

- MIPLIB:	57 problems, varying size and
- 		difficulty (several not proven optimal)
- Solved by FATCOP sequential solver:	41 (72%)
- Solved by FATCOP: 46 (80%)

## MIPLIB Problems: Cuts

## FATCOP: sequential/parallel

## FATCOP on real problems

## FATCOP vs CPLEX

## Machine utilization

- For one run of  “NSA” problem, used 122 machines (linux, intel/solaris, sun), 26 from UNM, 11 from NCSA.
- Average number of machines in use 111
- Wall clock time - 31.8 hrs
- Total worker cpu time - 3014 hrs
- Total worker suspension time - 40 hrs

## Simple Interfaces

- Write the heuristic code  in C/C++
- Perform heuristics at root node
- Rounding/reformulation at any node
- Searching heuristics at integer nodes
- Compile and copy the object file to the solver directory
- Turn on option “perform heuristics”

## Without Rounding Heuristic

## With Rounding Heuristic

## Set Covering Problem

- min  cTx s.t.	Ex>=e  and  xj = 0 or 1
- E  {0,1}300600,	ci  U(1,20)
- Rounding heuristic every 10 iterations
- Do “good solutions” early in the process help?

## Product Design Problem

- Maximize market share by choosing a product profile (or other objectives)
- Product has K attributes, and each attribute has L levels, N customers
- Important marketing problem
- NP hard, but good heuristics
- How good are these solutions?

## Product Design: MIP + GA

## Slide 29

## MIP Solution for Product Design using FATCOP

- Run FATCOP parallel solver
- Incorporate following user defined heuristics:
- Upper bound (NP/GA heuristics)
- Priority Branching (Greedy heuristic)
- Reformulation (both in root and subtrees)

## Product design - optimality

- K=12, L=3, N=200
- Use FATCOP parallel solver
- Turn on all user defined heuristics
- Provable optimal solution found
- The FATCOP job lasted ***10.1*** hours, evaluated ***18,115,883*** nodes and utilized ***75*** machines on average

## Product design - practicality

- K=12, L=3, N=200
- Use FATCOP sequential solver
- Turn on all user defined heuristics
- Prove the solution found by heuristics is within 20% gap in about 90,000 nodes.
- Run CPLEX MIP solver for comparison

## Slide 33

## Back to Seymour

- Schmieta, Pataki, Linderoth and Ferris
- explored to depth 8 in tree
- applied cuts at each of these 256 nodes
- solved in parallel, using whatever resources available
- Problem solved with over 1 year CPU

## Seymour Node 319

- FATCOP
-  47.0 hrs with 2,887,808 nodes
- average number of machine used is 108
- CPLEX
- 12 days, 10 hrs with 356,600 nodes
- single machine, clique cuts useful

## Future Work

- How to use heuristics to guide node selection and branching variable selection?
- Fly-in FATCOP
- FATCOP under AMPL
- Branch and Cut algorithm
- www.cs.wisc.edu/math-prog/tech-reports