Module integer 

Integer Programming and Mixed-Integer Optimization

This module provides algorithms for optimization problems where some or all variables must take integer values. It implements:

• BranchAndBoundSolver: Branch-and-bound for mixed-integer programs
• IntegerVariableSet: Specification of integer/binary/general integer constraints
• CuttingPlaneSolver: Gomory cutting plane method for pure integer programs

Mixed-Integer Programming (MIP)

A mixed-integer program has the form:

minimize    c^T x
subject to  A x <= b      (linear inequality constraints)
            Aeq x = beq   (linear equality constraints)
            lb <= x <= ub (bounds)
            x_I in Z      (integrality constraints for a subset I)

References

• Land, A.H. & Doig, A.G. (1960). “An automatic method of solving discrete programming problems.” Econometrica, 28(3), 497-520.
• Gomory, R.E. (1958). “Outline of an algorithm for integer solutions to linear programs.” Bulletin of the American Mathematical Society, 64(5), 275-278.

Re-exports

pub use branch_and_bound::BranchAndBoundOptions;

pub use branch_and_bound::BranchAndBoundSolver;

pub use cutting_plane::CuttingPlaneOptions;

pub use cutting_plane::CuttingPlaneSolver;

pub use lp_relaxation::LpRelaxationSolver;

Modules

branch_and_bound

Branch-and-Bound algorithm for Mixed-Integer Programming

cutting_plane

Gomory Cutting Plane Method for Integer Programming

knapsack

Knapsack Problem Solvers

lp_relaxation

LP relaxation solver for use in branch-and-bound

milp_branch_and_bound

Mixed-Integer Linear Programming via Branch-and-Bound

Structs

IntegerVariableSet

Set of integer variable constraints for a MIP problem

LinearProgram

Linear program specification

MipResult

Result from a MIP solve

Enums

IntegerKind

Type of integer variable constraint

Functions

is_integer_valued

Check if a value is integer (within tolerance)

most_fractional_variable

Find the most fractional variable index