This is the first part of the ILP series. For your convenience you can find other parts using the links below:
Part 1 – Boolean algebra
Part 2 – Multiplication
Part 3 – Division, remainder, exponentation, roots
Part 4 – Comparisons
Part 5 — Absolute value, maximum, minimum
Part 6 — Faster multiplication
Part 7 — Multiplication of negative numbers
Part 8 — Multiple and GCD
Part 9 — Conditional operator
Part 10 — Sort
Part 11 — Counting sort
Part 12 — Exponentation
Part 13 — Factorial
Part 14 — Comparing real numbers
Part 15 — Basic set operations
Part 16 — Solving cube riddle
Part 17 — Solving Lonpos 505 Puzzle
Part 18 — Students Placement Problem Part 1 — Introduction
Part 19 — Students Placement Problem Part 2 — Necessary constraints
Part 20 — Students Placement Problem Part 3 — Useful constraints
Part 21 — Students Placement Problem Part 4 — Basic cost function
Part 22 — Students Placement Problem Part 5 — Continuous Classes
Part 23 — Students Placement Problem Part 6 — Days off
Part 24 — Students Placement Problem Part 7 — Teams
Part 25 — Students Placement Problem Part 8 — Unlucky person
Part 27 — Students Placement Problem Part 9 — Coefficients
Part 27 — Einstein’s five houses riddle
Part 28 — Using ILP in .NET
Part 29 — Nonograms
Part 30 — Sudoku
Part 31 — Students Placement Problem Part 10 — Fixing plan
Part 32 — Wolf, goat, cabbage, and farmer
Part 33 — Lexicographical comparisons
Part 34 — Special Ordered Set Type 1 and 2
Part 35 — Approximation
Part 36 — Various goal types
Part 37 — Send more money
Part 38 — Arrays in ILP
Part 39 — Non-deterministic Turing Machine
Part 40 — Ternary logic
Part 41 — Rubik’s cube
Part 42 — Fifteen puzzle
Part 43 — Maximum revisited
Part 44 — Pizza riddle simplified
Part 45 — Deadline 24 2017 Election
Part 46 — Gray Code
Part 47 — Battleship puzzle
Part 48 — Shapes and colors
Part 49 — Deadline24 2018 — Flow
Part 50 — MST, vertex cover and edge cover
Part 51 — Linear regression
Part 52 — Unsigned magnitude decomposition for real variables
Part 53 — Max flow
Part 54 — Graph connectivity
Part 55 — Shortest path
Part 56 – Factorization benchmarking
Part 57 – SPOJ Wpłaty
Part 58 – Kantoriiroodo
Part 59 – Pętliczek
Part 60 – Fencing Match
Part 61 – Sudomino
Part 62 – Maximally attacking chessboard
Part 63 – Surasshupakku
Part 64 – BFS, graph connectivity, spanning tree
Part 65 – Fancy sudoku
Part 66 – Knight on dominoes
Part 67 — Parcelacja
Part 68 — War card game
Part 69 — Krypto 3 po 3
Part 70 — Elements reordering
Part 71 — Typo
Part 72 — Self-descriptive numbers
Part 73 — Matchstick puzzle
Part 74 — Absolute value for real numbers
Part 75 — 100 and 13
Part 76 — Dead ends
Part 77 — Stained glass
Part 78 — Tic-Tac-Toe
Part 79 — Complex constraints and comparisons
Part 80 — Islanders
Part 81 — Kakuro
Part 82 — S and P
Part 83 — Concatenation
Part 84 — Na koń
Part 85 — Lying riddle
Part 86 — Skyscrapers
Part 87 — Sequence of squares
Part 88 — Magical Tangram
Part 89 — Poles
Part 90 — Turkey
Part 91 — Golf
Part 92 — Crossing
Part 93 — Squared Poland
Part 94 — Horrendum
Part 95 — Yin and Yang
Part 96 — Rook it!
Part 97 — Rook it advanced
Part 98 — Horrendum 2
Part 99 — MacMahon Squares
Part 100 — Literowce
Part 101 — Polyominoes
Part 102 — Gamic Square
Part 103 — 600
Part 104 — 12 stones riddle
Part 105 — Sudoku Cube
Part 106 — Golden waste

If you are interested in the topic see the talk page

See my book Applied Integer Linear Programming on Amazon.com

Today we are going to implement Boolean algebra in ILP!

ILP – what’s that

Integer Linear Programming (ILP) is a way of formulating optimization problems. We define a set of variables, their upper and lower bounds, a set of constraints, and a cost function which we use to evaluate possible solutions. The main idea here is to use only linear functions (so we are not allowed to multiply variables), and require variables to be integers. If only some of the variables need to be integer, we have a Mixed Integer Linear Programming problem.

Why bother with ILP

This branch of mathematics is widely used in allocation problems. If we need to optimize production in factories, then ILP is a good way to go. It is a very well explored concept and there are papers describing in detail how to solve ILP programs. There are also enterprise solvers like CPLEX or Gurobi, which are highly optimized and scalable. Considering that, it is relatively easy to solve an ILP problem, and because ILP is NP-Complete, we are able to use it to represent lots of problems (starting with sorting and finishing with Hamiltonian path).

Let’s go

We are going to implement Boolean algebra in ILP. We are going to define constraints which will allow us to represent logical operators in ILP, so we will be able to create logical expressions.

Notation

In examples we will use the following notation:

We have three binary variables. We’ll use first two ( and ) as arguments for logical operator, will usually represent the result of the operation. Let’s go.

Conjunction

We will start with conjunction. As you probably remember from school, it is defined in the following way:

Basically, the result is equal to one if and only if both arguments are equal to one. In ILP we can use the following formula:

These two inequalities fulfill the requirements. When both and are equal to zero then cannot be equal to one (because the left inequality would not hold) and must be zero. When either or is equal to one the situation doesn’t change. However, if both and are non-zero, then cannot be zero (because right inequality would not hold).

We can easily generalize this formula for multiple variables. Assuming that are binary variables, we can do the following:

You can conduct similar reasoning to proof that it is corrent.

Disjunction

Disjunction is very similar to conjunction. Basically, we need to swap bounds:

Indeed, if is zero then must be zero too. However, if any of and is equal to one then cannot be zero (because the right inequality would not be true) and it must be one. Generalization is simple.

Other operators

Negation is easy as pie:

To define implication we can use the identity:

Exclusive or (XOR) goes this way:

More operators

You can implement other operators using identities or by stacking already defined ones. As an example try to define Sheffer stroke (also known as NAND gate).

Summary

As we can see, implementing Boolean algebra is really straightforward and can be done without hacks or magical tricks. What’s more, solvers are aware of this construct and are able to recognize the logical relations (e.g., CPLEX has this ability) which probably leads to more efficient solving.
In the next part we are going to multiply variables in ILP.