This is the first part of the ILP series. For your convenience you can find other parts using the links below (or by guessing the address):
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
If you are interested in the topic see the talk page
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).
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.
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.
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 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.
Negation is easy as pie:
To define implication we can use the identity:
Exclusive or (XOR) goes this way:
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).
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.