integer programs

Work in Progress

Concept

An integer program (IP) is an LP with integrality restrictions. It is pure if every variable is integral and mixed otherwise. Binary variables satisfy . Integrality can turn an easy LP into a computationally hard problem; polynomial-time algorithms are known for LP, but not expected for general IP.

Typical pure-IP models include integer knapsack,

and cyclic staff scheduling, where integer variables count workers beginning each shift pattern and coverage constraints meet each day’s demand.

Binary modelling

Binary variables encode choices and implications. If and activity is allowed only when , use . To enforce either or , use

For a discrete set , introduce :

The bound must be valid; an unnecessarily large big- weakens the relaxation.

Application

Use integer variables only when divisibility matters. Logical conditions are handled by binary modeling; later, integer hulls and meyers theorem explains the relation to LP.