Mixed Integer Linear Programming#
Consider the following example,
Given system constraints:
2x + 4y >= 230
3x + 2y <= 190
x >= 0, x is integer
y >= 0, y is continuious
Maximize objective function:
f(x) = 5x + 3y
You need to find numbers for x and y in such a way that it satisfies constraints and maximizes the objective function.
problem_data = {}
Set Constraint Matrix#
If the constraints are:
2x + 4y >= 230
3x + 2y <= 190
Constraints are depicted in CSR format. The constraints can be transformed to the CSR matrix as follows:
offsets = [0, 2, 4]
indices = [0, 1, 0, 1]
coefficients = [2.0, 4.0, 3.0, 2.0]
problem_data["csr_constraint_matrix"] = {
"offsets" : offsets,
"indices" : indices,
"values" :coefficients
}
The offsets indicate the length of the constraint and indices indicate variables.
Set Constraint Bounds#
If the constraints are as follows:
2x + 4y >= 230
3x + 2y <= 190
You need to define upper_bounds
and lower_bounds
of all the
constraints, each value signifies the upper or lower bound of each
constraint respective to its index.
upper_bounds = ["inf", 190.0]
lower_bounds = [230.0, "ninf"]
problem_data["constraint_bounds"] = {
"upper_bounds" : upper_bounds,
"lower_bounds" : lower_bounds
}
inf
- infinity and ninf
- negative infinity are used when there
is no explict upper or lower bound.
Set Variable Bounds#
Variables:
x >= 0
y >= 0
Define the variable bounds similar to constraint bounds.
var_upper_bounds = ["inf", "inf"]
var_lower_bounds = [0.0, 0.0]
problem_data["variable_bounds"] = {
"upper_bounds" : var_upper_bounds,
"lower_bounds" : var_lower_bounds
}
Set Objective Data#
Objective:
f(x) = 5x + 3y
Pass coefficents for objective data and also set whether it needs to be maximized or minimized.
objective_coefficients = [5.0, 3.0]
maximize = True
problem_data["objective_data"] = {
"coefficients" : objective_coefficients,
"scalability_factor" : 1.0,
"offset" : 0.0
}
problem_data["maximize"] = maximize
Set Variable Names#
This is optional, but it helps users to navigate the result.
problem_data["variable_names"] = ["x", "y"]
Set Variable Types#
Set variable types, I - Integer
and C - Continuous
problem_data["variable_types"] = ["I", "C"]
Set Solver Configuration#
The solver configuration can be fine-tuned for optimization and runtimes.
solver_config = {
"time_limit" : 1.0,
"tolerances": {
"optimality" : 0.0001
}
}
problem_data["solver_config"] = solver_config
Solve the Problem#
For managed service, cuOpt endpoints can be triggered as shown in the thin client example for managed service.
For self-hosted, cuOpt endpoints can be triggered as shown in the thin client example for self-hosted.
Use this data and invoke the cuOpt endpoint, which would return values
for x
and y
.
The following example is using a locally hosted server:
from cuopt_sh_client import CuOptServiceSelfHostClient
import json
# If cuOpt is not running on localhost:5000, edit ip and port parameters
cuopt_service_client = CuOptServiceSelfHostClient(
ip="localhost",
port=5000
)
solution = cuopt_service_client.get_LP_solve(problem_data, response_type="dict")
print(json.dumps(solution, indent=4))
Status - 1
corresponds to Optimal solution is available
.
{
"response": {
"solver_response": {
"status": 1,
"solution": {
"primal_solution": [
0.0,
57.5
],
"dual_solution": [],
"solver_time": 0.0,
"primal_objective": -172.49999999999997,
"dual_objective": -172.49999999999997,
"vars": {
"x": 0.0,
"y": 57.5
},
"lp_statistics": {
"primal_residual": 0.0,
"dual_residual": 0.0,
"gap": 0.0,
"reduced_cost": []
}
}
},
"perf_times": null,
"total_solve_time": null
},
"reqId": "260e0957-4977-4626-b42d-0d3b8912d925"
}