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!

Table of Contents

# 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:

## Other 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.