Optimization tools and Gurobi

Optimization problems solutions/algorithms:

• Simplex is great for small to medium-sized problems where you need a quick, reliable solution.

• Interior-point methods (including Barrier methods) are best suited for large-scale problems where performance scaling is critical.

• Dual Simplex is useful when you need to make small changes to an existing feasible solution.

• Revised Simplex is ideal for very large LP problems where memory and computational efficiency are a concern.

Commercial products:

• CPLEX and Gurobi are the leaders in the commercial solver space, offering the best performance and flexibility, especially for large-scale problems.

CPLEX is an old IBM product. The tech people left IBM and found Gurobi.

• CBC is a solid open-source alternative for mixed-integer programming but may struggle with performance for large problems.

• DASH and MOSEK are specialized solvers suited for distributed computing and quadratic/conic programming, respectively.

• XPRESS is a good option for industrial-scale problems but might be less popular than CPLEX and Gurobi.

How to use Gurobi in ORTools?

To use Gurobi on a desktop

Download and install gurobi Gurobi-11.0.1-win64.msi

Copy paste the license file to c:\gurobi, this is the default folder for searching the license file

The license file is something like gurobi.lic:

    TOKENSERVER=<ip address>

Just pointing to the license server. It can be a VM or a server somewhere (setup required in advance).

Once the license is setup.

Then, install the Python API:

pip install gurobipy

When using ortools, just use the GUROBI solver.

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

Performance wise, some optimization problems with 10,000+ decision variables and took one hour using SCIP in ORTools, took only 5 seconds using the Gurobi solver. Very impressive.

For running optimization within the cloud, a different gurobi licence is needed, e.g. the WLS license.

The script in the cloud only needs the pip install gurobipy

The license can be pointing to an external license server, or a license hosted by gurobi.

Simplex / Barrier /etc

The Method parameter controls the algorithm Gurobi uses:

Value, Method

-1

Automatic (default — Gurobi chooses)

0

Primal Simplex

1

Dual Simplex

2

Barrier (Interior Point Method)

3

Concurrent (tries multiple in parallel)

4

Deterministic Concurrent (for LP only)

model.setParam('Method', 2) #to nominate barrier as the method

An MIP example - using gurobi lib and status handling

from gurobipy import Model, GRB

# Create a new MIP model

model = Model("WIP_MIP_Example")

# Decision variables (integer)

A = model.addVar(vtype=GRB.INTEGER, name="ProductA")

B = model.addVar(vtype=GRB.INTEGER, name="ProductB")

# Objective: Maximize profit

model.setObjective(40 * A + 30 * B, GRB.MAXIMIZE)

# Constraints

model.addConstr(3 * A + 2 * B <= 240, "LaborConstraint")

model.addConstr(4 * A + 3 * B <= 200, "MaterialConstraint")

model.addConstr(A >= 0, "A_nonnegative")

model.addConstr(B >= 0, "B_nonnegative")

# Optimize

model.optimize()

# =============================

#     Status Handling Logic

# =============================

status = model.status

status_str = ""

# Optimal solution

if status == GRB.OPTIMAL:

    status_str = "OPTIMAL"

    print("===== Optimal solution found =====")

# Feasible but not proven optimal (due to limits or tolerances)

elif status in [

    GRB.TIME_LIMIT,

    GRB.NODE_LIMIT,

    GRB.SOLUTION_LIMIT,

    GRB.INTERRUPTED,

    GRB.SUBOPTIMAL,

    GRB.USER_OBJ_LIMIT,

    GRB.WORK_LIMIT,

    GRB.MEM_LIMIT,

]:

    if model.SolCount > 0:

        status_str = "FEASIBLE"

        print("===== Feasible solution found (not proven optimal) =====")

    else:

        status_str = "NO_SOLUTION"

        print("===== No feasible solution found under limits =====")

# Infeasible or unbounded

elif status == GRB.INFEASIBLE:

    status_str = "INFEASIBLE"

    print("===== Model is infeasible =====")

elif status == GRB.UNBOUNDED:

    status_str = "UNBOUNDED"

    print("===== Model is unbounded =====")

elif status == GRB.INF_OR_UNBD:

    status_str = "INF_OR_UNBOUNDED"

    print("===== Model is infeasible or unbounded =====")

# Any other unknown or error status

else:

    status_str = "UNKNOWN"

    print(f"===== Optimization ended with status code {status} =====")

# =============================

#     Solution Display

# =============================

# Show solution if one exists

if model.SolCount > 0:

    print(f"Status: {status_str}")

    print(f"Produce {A.X} units of Product A")

    print(f"Produce {B.X} units of Product B")

    print(f"Objective value (Profit): ${model.ObjVal}")

Gurobi can handle non-linear constraints e.g. sin / cos / exp / max / min as well

Use the corresponding add constraint method as below: