Linear Programming#

Consider the following example,

Given system constraints:

2x + 4y >= 230
3x + 2y <= 190
x >= 0
y >= 0,

Maximize objective function:

f(x) = 5x + 3y

You need to find real 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 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": [37.50083870322277, 38.7492566784616],
                "dual_solution": [0.12490361527659652, -1.7498895880181375],
                "solver_time": 74.0,
                "primal_objective": 303.75196355149865,
                "dual_objective": 303.7511902098289,
                "vars": {"x": 37.50083870322277, "y": 38.7492566784616},
                "lp_statistics": {
                    "primal_residual": 0.0016550243746766345,
                    "dual_residual": 0.00013846649878068717,
                    "gap": 0.000773341669741967,
                    "reduced_cost": [0.0, 0.00016471492988889835]
                }
            }
        },
        "perf_times": "None",
        "total_solve_time": "None"
    },
    "reqId": "c423d695-7042-4453-a182-f812feeacbcf"
}