IntegerProgram<T>

Models & Types · AiDotNet.Solvers.LinearProgramming

A linear program in which some or all variables are required to take whole-number values.

For Beginners

Some quantities cannot be fractional. You can buy 2.7 kilos of flour, but you cannot hire 2.7 people, run 2.7 delivery vans, or open 2.7 warehouses. Rounding the fractional answer is tempting and frequently wrong — the rounded point is often infeasible, and when it is feasible it can be far from the best whole-number choice. Stating the requirement up front lets the solver search whole-number answers properly.

How It Works

Adding integrality to a linear program changes its character completely. A linear program is solvable in polynomial time; deciding integer feasibility is NP-complete (Karp, 1972), so every exact method is a search whose worst case is exponential. What makes it tractable in practice is that the linear relaxation — the same problem with the integrality dropped — is cheap to solve and gives a bound strong enough to prune most of the search tree.

Constructors

Constructor Summary
IntegerProgram(LinearProgram<T> relaxation, IReadOnlyList<bool> integralityMask) Creates an integer program.

Properties

Property Summary
IReadOnlyList<bool> IntegralityMask { get; } Gets a flag per variable indicating whether that variable must take an integer value.
LinearProgram<T> Relaxation { get; } Gets the underlying linear program, ignoring the integrality requirements.
int VariableCount { get; } Gets the number of decision variables.