View source for Binary Integer Linear Program

A linear program is an algorithm of use when the objective function, or goal, can be expressed as an equation that is linear in the decision variables, and all constraints are likewise linear in the decision variables. An '''Binary Integer Linear Program''' is a linear program where the decision variables can take on only two values, 0 and 1.  

[[Programming Sudoku|Sudoku can be programmed]] as a binary integer linear program by defining the decision variables 

: x(i,j,k) = 0 if [[cell]] i, j in the [[grid]] is not equal to k

: x(i,j,k) = 1 if [[cell]] i, j in the [[grid]] is equal to k

The x(i,j,k) can then be limited by the four [[constraint]] types. 

Using the terminology of linear programming, Sudoku is a [[constraint satisfaction problem]] (or '''feasibility problem'''), meaning that the objective function is arbitrary, and the goal is to simply find a feasible solution, i. e. one that does not violate any constraint.  

Integer programming (IP) problems are often solved using the [http://en.wikipedia.org/wiki/Branch_and_bound branch and bound] algorithm.  IPs are frequently found in [http://en.wikipedia.org/wiki/Operations_research operations research].

== Reference ==

Barlett, Andrew C. and Amy N. Langville (2006), [http://www.cs.uleth.ca/~kadiri/Math1410-Fall08/sudoku2.pdf An Integer Programming Model for the Sudoku Problem], College of Charleston Working Paper.