Integer Linear Program

An integer linear program (ILP) is an optimization problem where the goal is to maximize or minimize a linear objective function subject to linear equality and inequality constraints, where the variables are restricted to integers.

A simple example in standard form:

Maximize: z = 3x + 4y

Subject to: x + y <= 5 x - y >= 1 x, y >= 0 and integers

An ILP can be solved using techniques like branch and bound to find optimal integer solutions.

Java example encoding knapsack as ILP:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

ILP ilp = new ILP();

// Variables 
for (Item item : items) {
  ilp.addVariable("x_" + item.id, true, 0, 1); // binary
}

// Objective  
ilp.setObjectiveMax(true);
for (Item item : items) {
  ilp.addObjective("x_" + item.id, item.value);
}

// Constraints
ilp.addConstraint(LTE, totalWeight);
for (Item item : items) {
  ilp.addConstraint("x_" + item.id, item.weight);  
}

ilp.solve();

C++ example for warehouse location:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Variables, constraints, objective

ILP ilp;
ilp.setObjectiveMin(true);

// Set binary constraints
for (string loc: locations) {
  ilp.setVarType(loc, INT, 0, 1); 
}

ilp.solve();

Python example for sports scheduling:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Encode teams, games, schedule constraints as ILP

model = pywraplp.Solver('ILP', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Variables 

# Constraints

# Objective 

model.maximize()
solution = model.Solve()

ILP provides a flexible way to model optimization problems with discrete variables and linear constraints.

Integer Linear Programming (ILP) is a mathematical optimization technique where the objective function and the constraints are both linear equations. The key difference from Linear Programming (LP) is that variables in ILP must take integer values. It is commonly used in scheduling, routing, and other optimization problems where the solutions must be discrete.

Algorithm

1. Objective Function: Formulate the objective function to maximize or minimize.
2. Constraints: Define the linear constraints that restrict the variables.
3. Integer Requirement: Specify that variables must be integers.
4. Solver: Use a solver to find the optimal solution that satisfies all constraints.

Actual implementations usually involve using specialized libraries or solvers because solving ILP is an NP-hard problem.

Java Code

Java does not have native support for ILP. Libraries like Gurobi or CPLEX are used.

1

// Use Gurobi or CPLEX libraries to implement ILP

C++ Code

C++ also relies on third-party libraries like Gurobi.

1

// Use Gurobi or CPLEX libraries to implement ILP

Python Code

Python has libraries like PuLP or SciPy.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

from pulp import LpMaximize, LpProblem, LpVariable

# Create the model
model = LpProblem(name="small-problem", sense=LpMaximize)

# Initialize the decision variables
x = LpVariable(name="x", lowBound=0, cat='Integer')
y = LpVariable(name="y", lowBound=0, cat='Integer')

# Add the constraints to the model
model += (2 * x + 3 * y <= 20, "constraint_1")

# Add the objective function to the model
model += 4 * x + 3 * y, "objective"

# Solve the problem
model.solve()

In the Python example, we use the PuLP library to create a simple ILP model with one constraint. The variables x and y are both constrained to be integers.

These examples rely on third-party libraries because ILP problems are computationally intensive to solve from scratch. The libraries handle the underlying complexities.