Henry Wolkowicz's Research

Research Home
Publications & Abstracts
Talks & Presentations
Semidefinite
Programming
EDM
and SNL
Graph
Partitioning

Maximum
Cut

Linear
Programming
Quadratic
Assignment

NLP,
Regularization,
TRS
Set
Partitioning
Matrix
Approximation
Misc. Software/Opt. Matrices
and
Optimization

Set Partitioning

 

The Model


Minimize cost cx
s.t. Ax=1 , x is 0,1

and c is a vector of rational components,
A is a 0,1 matrix.

 

Applications


The best known application is to
Airline Crew Scheduling.


A set of flight legs (between cities) are given that must be flown.

Each constraint (row) represents a flight leg. Feasible trips (i.e., a sequence of flight legs) for crews need to be chosen (columns of constraint matrix).
 
 

Further Information


An SDP relaxation for the SPP


     J.E. Beasley's home page
has a section on
set covering / partitioning.

The OR-Library has
test data sets for
set partitioning.






Last Modified:  Friday 22 December 2006