Here is a summary of all optimization models required for every problem solving algorithm
Download the word file HERE


preview without ILP models are shown below

Problem

ILP model

(#variables, #constraints)

The associated LP relaxation is

UFLP



(n + mn ; m + n)

(n + mn ; m + mn)

weak"

strong"

Set Covering


(n ; m)

strong"

Set Partitioning


(n ; m)

strong"

Set Packing


(n ; m)

intermediate" if all constraints are associated with maximal cliques of G(A) (see Stable Set)

CFLP


(n + mn ; m + mn + n)

generally \strong",even if tends tobecome \weak" if facilities are equal (see BinPacking)

Bin Packing



(n + mn ; m + mn + n)


weak"

strong"

Fixed Charge


(2n ; n) plus Ax > b

weak" depending on M values

Stable Set




(n; m)

(n; O(2n))

(n; O(m))

weak"

strong"

Intermediat

Vertex Coloring




(n + n2; n + nm)

(n + n2; n + O(n2n))

(O(2n); n)

\weak"

\intermediate"

\strong"

ATSP


(n(n - 1); 2n + O(2n))

strong"

TSP


(n(n - 1)=2; n + O(2n))

strong"