4  Integer Programming

Integer programming has a wide range of applications across various industries and domains. Some of the classical applications of integer programming include:

• Production Planning and Scheduling: Integer programming is widely used in production planning and scheduling to optimize the allocation of resources, such as machines, workers, and raw materials. It helps to minimize costs and maximize efficiency by determining the optimal production schedule.

• Network Optimization: Integer programming is used in network optimization problems such as routing, scheduling, and allocation of resources in transportation networks, telecommunication networks, and supply chain management.

• Facility Location: Integer programming is used in facility location problems, which involve determining the optimal location for a facility based on various factors such as demand, supply, and transportation costs. It is commonly used in logistics, transportation, and distribution industries.

• Portfolio Optimization: Integer programming is used in finance to optimize investment portfolios, where the goal is to maximize the returns on the investment while minimizing risk.

• Cutting Stock and Bin Packing: Integer programming is used in cutting stock and bin packing problems where items of varying sizes must be packed into containers or cut from a stock. This is commonly used in the packaging and manufacturing industries.

• Crew Scheduling: Integer programming is used in crew scheduling problems, where the goal is to optimize the allocation of crew members to different shifts, duties, or activities. It is commonly used in industries such as airlines, railways, and public transportation.

• Timetabling: Integer programming is used in timetabling problems such as scheduling classes, exams, and events in academic institutions. It helps to minimize scheduling conflicts and maximize resource utilization.

This chapter explores the various methods that Google OR-Tools provides for modeling and solving (mixed) integer linear programming problems. The first step is to review the additional conditions that arise when modeling integer variables and solving integer programs. Following that, we use specific instances to demonstrate how these techniques are applied.

4.1 Modeling Capabilities

When modeling integer programs, there are two main tasks that require attention. The first is declaring integer variables, and the second is selecting a solver that is capable of solving integer programs.

4.1.1 Declaring Integer Variables

As reviewed in Chapter 3, Google OR-Tools provides two options to create integer variables:

• The Var(lb, ub, integer: bool, name) function
• The IntVar(lb, ub, name) function
• The Variable.SetInteger(integer: bool) function

In the code snippet below, we create three integer variables using all the aforementioned approaches:

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver.CreateSolver('SCIP')

# option 1
x = solver.Var(lb=0, ub=10, integer=True, name='x')

# option 2
y = solver.IntVar(lb=10, ub=20, name='y')

# option 3
z = solver.NumVar(lb=0, ub=5.5, name='z')
z.SetInteger(integer=True)

We can verify the types of variables \(x, y, z\):

print(f"x is integer? {x.integer()}")
print(f"y is integer? {y.integer()}")
print(f"z is integer? {z.integer()}")

x is integer? True
y is integer? True
z is integer? True

4.1.2 Selecting an Integer Solver

There are several solvers available for solving integer programs, and some options include:

• CBC_MIXED_INTEGER_PROGRAMMING or CBC
• BOP_INTEGER_PROGRAMMING or BOP
• SAT_INTEGER_PROGRAMMING or SAT or CP_SAT
• SCIP_MIXED_INTEGER_PROGRAMMING or SCIP
• GUROBI_MIXED_INTEGER_PROGRAMMING or GUROBI or GUROBI_MIP
• CPLEX_MIXED_INTEGER_PROGRAMMING or CPLEX or CPLEX_MIP
• XPRESS_MIXED_INTEGER_PROGRAMMING or XPRESS or XPRESS_MIP
• GLPK_MIXED_INTEGER_PROGRAMMING or GLPK or GLPK_MIP

It’s important to note that some of these solvers are open-source, while others require a commercial license. The code block above demonstrates how to create an instance of an integer solver. To do so, we simply need to specify the name of the solver in the Solver.CreateSolver() function.

solver = pywraplp.Solver.CreateSolver('CBC')