solve_linear_programming
Solve linear and mixed-integer programming problems with linear constraints using the HiGHS solver for optimization tasks.
Instructions
Solve linear and mixed-integer programming problems using HiGHS.
This tool is ideal for linear programming, mixed-integer linear programming,
and large-scale optimization problems with linear constraints.
Args:
sense: Optimization sense, either "minimize" or "maximize"
objective_coeffs: List of objective function coefficients
variables: List of variable definitions with optional bounds and types
constraint_matrix: 2D list representing the constraint matrix (dense format)
constraint_senses: List of constraint directions ("<=", ">=", "=")
rhs_values: List of right-hand side values for constraints
options: Optional solver options dictionary
description: Optional problem description
Returns:
Solution results including variable values and objective value
Example:
sense = "minimize"
objective_coeffs = [1.0, 2.0, 3.0]
variables = [
{"name": "x1", "lb": 0, "ub": 10, "type": "cont"},
{"name": "x2", "lb": 0, "ub": None, "type": "int"},
{"name": "x3", "lb": 0, "ub": 1, "type": "bin"}
]
constraint_matrix = [[1, 1, 0], [0, 1, 1]]
constraint_senses = ["<=", ">="]
rhs_values = [5, 3]Input Schema
TableJSON Schema
| Name | Required | Description | Default |
|---|---|---|---|
| constraint_matrix | Yes | ||
| constraint_senses | Yes | ||
| description | No | ||
| objective_coeffs | Yes | ||
| options | No | ||
| rhs_values | Yes | ||
| sense | Yes | ||
| variables | Yes |
Implementation Reference
- The main handler function for the 'solve_linear_programming' MCP tool. It handles input validation, constructs the HiGHSProblem model from arguments, calls the solver, and returns formatted results as TextContent.
@app.tool("solve_linear_programming") async def solve_linear_programming( sense: str, objective_coeffs: List[float], variables: List[dict[str, Any]], constraint_matrix: List[List[float]], constraint_senses: List[str], rhs_values: List[float], options: dict[str, Any] = None, description: str = "", ) -> List[TextContent]: """ Solve linear and mixed-integer programming problems using HiGHS. This tool is ideal for linear programming, mixed-integer linear programming, and large-scale optimization problems with linear constraints. Args: sense: Optimization sense, either "minimize" or "maximize" objective_coeffs: List of objective function coefficients variables: List of variable definitions with optional bounds and types constraint_matrix: 2D list representing the constraint matrix (dense format) constraint_senses: List of constraint directions ("<=", ">=", "=") rhs_values: List of right-hand side values for constraints options: Optional solver options dictionary description: Optional problem description Returns: Solution results including variable values and objective value Example: sense = "minimize" objective_coeffs = [1.0, 2.0, 3.0] variables = [ {"name": "x1", "lb": 0, "ub": 10, "type": "cont"}, {"name": "x2", "lb": 0, "ub": None, "type": "int"}, {"name": "x3", "lb": 0, "ub": 1, "type": "bin"} ] constraint_matrix = [[1, 1, 0], [0, 1, 1]] constraint_senses = ["<=", ">="] rhs_values = [5, 3] """ try: # Validate sense try: from ..models.highs_models import HiGHSSense problem_sense = HiGHSSense(sense) except ValueError: return [ TextContent( type="text", text=( f"Invalid sense: {sense}. " f"Must be one of: minimize, maximize" ), ) ] # Create objective from ..models.highs_models import HiGHSObjective objective = HiGHSObjective(linear=objective_coeffs) # Create variables problem_variables = [] for i, var in enumerate(variables): var_name = var.get("name", f"x{i+1}") var_lb = var.get("lb", 0.0) var_ub = var.get("ub", None) var_type_str = var.get("type", "cont") try: from ..models.highs_models import HiGHSVariableType var_type = HiGHSVariableType(var_type_str) except ValueError: return [ TextContent( type="text", text=( f"Invalid variable type: {var_type_str}. " f"Must be one of: cont, int, bin" ), ) ] from ..models.highs_models import HiGHSVariable problem_variables.append( HiGHSVariable(name=var_name, lb=var_lb, ub=var_ub, type=var_type) ) # Create constraints constraint_sense_enums = [] for sense_str in constraint_senses: try: from ..models.highs_models import HiGHSConstraintSense constraint_sense_enums.append(HiGHSConstraintSense(sense_str)) except ValueError: return [ TextContent( type="text", text=( f"Invalid constraint sense: {sense_str}. " f"Must be one of: <=, >=, =" ), ) ] from ..models.highs_models import HiGHSConstraints, HiGHSProblemSpec, HiGHSProblem, HiGHSOptions constraints = HiGHSConstraints( dense=constraint_matrix, sparse=None, sense=constraint_sense_enums, rhs=rhs_values, ) # Create problem specification problem_spec = HiGHSProblemSpec( sense=problem_sense, objective=objective, variables=problem_variables, constraints=constraints, ) # Create options if provided highs_options = None if options: highs_options = HiGHSOptions(**options) # Create full problem problem = HiGHSProblem(problem=problem_spec, options=highs_options) # Solve the problem result = solve_highs_problem(problem) match result: case Success(solution): return [ TextContent( type="text", text=json.dumps( { "values": solution.values, "objective_value": solution.objective_value, "status": solution.status.value, "solve_time": solution.solve_time, "dual_values": solution.dual_values, "reduced_costs": solution.reduced_costs, } ), ) ] case Failure(error): return [TextContent(type="text", text=f"Error solving problem: {error}")] except Exception as e: return [TextContent(type="text", text=f"Error in solve_linear_programming: {e!s}")] - Core solver implementation using the highspy library to solve linear/mixed-integer programs defined by the HiGHSProblem model.
def solve_highs_problem(problem: HiGHSProblem) -> Result[HiGHSProblem, str]: """Solve a HiGHs optimization problem.""" try: # Validate problem if not problem.validate(): return Failure("Invalid problem definition") start_time = time.time() # Create HiGHs instance h = highspy.Highs() # Always disable output for MCP server compatibility h.setOptionValue("output_flag", False) h.setOptionValue("log_to_console", False) # Apply options options_result = _apply_options(h, problem.options) if isinstance(options_result, Failure): return options_result problem_spec = problem.problem num_vars = len(problem_spec.variables) num_constraints = len(problem_spec.constraints.sense) # Set up objective obj_coeffs = np.array(problem_spec.objective.linear, dtype=float) if len(obj_coeffs) != num_vars: return Failure( f"Objective coefficients length ({len(obj_coeffs)}) doesn't match number of variables ({num_vars})" ) # Set up variable bounds var_lower = np.zeros(num_vars, dtype=float) var_upper = np.full(num_vars, highspy.kHighsInf, dtype=float) for i, var_spec in enumerate(problem_spec.variables): lb, ub = _get_variable_bounds(var_spec, i) var_lower[i] = lb var_upper[i] = ub # Build constraint matrix matrix_result = _build_constraint_matrix(problem_spec) if isinstance(matrix_result, Failure): return matrix_result rows, cols, values = matrix_result.unwrap() # Set up constraint bounds constraint_lower = np.zeros(num_constraints, dtype=float) constraint_upper = np.zeros(num_constraints, dtype=float) for i, (sense, rhs) in enumerate( zip( problem_spec.constraints.sense, problem_spec.constraints.rhs, strict=False, ) ): lb, ub = _convert_constraint_sense(sense, rhs) constraint_lower[i] = lb constraint_upper[i] = ub # Add variables h.addCols( num_vars, obj_coeffs, var_lower, var_upper, 0, np.array([]), np.array([]), np.array([]), ) # Set variable integrality constraints integrality = np.zeros(num_vars, dtype=int) # 0 = continuous for i, var_spec in enumerate(problem_spec.variables): if var_spec.type == HiGHSVariableType.BINARY: integrality[i] = 1 # 1 = integer (binary is integer with bounds 0-1) elif var_spec.type == HiGHSVariableType.INTEGER: integrality[i] = 1 # 1 = integer # else: continuous (already 0) # Apply integrality constraints if any variables are integer/binary if np.any(integrality > 0): h.changeColsIntegrality(num_vars, np.arange(num_vars), integrality) # Add constraints using sparse format if len(rows) > 0: # Convert to row-wise sparse format for HiGHs # Group by rows and create start array unique_rows = np.unique(rows) start_array = np.zeros(num_constraints + 1, dtype=int) for row in unique_rows: start_array[row] = np.sum(rows < row) start_array[-1] = len(rows) # Final start h.addRows( num_constraints, constraint_lower, constraint_upper, len(values), start_array, cols, values, ) else: # No constraints case h.addRows( num_constraints, constraint_lower, constraint_upper, 0, np.array([0]), np.array([]), np.array([]), ) # Set objective sense if problem_spec.sense == HiGHSSense.MAXIMIZE: h.changeObjectiveSense(highspy.ObjSense.kMaximize) else: h.changeObjectiveSense(highspy.ObjSense.kMinimize) # Solve the problem h.run() solve_time = time.time() - start_time # Get results model_status = h.getModelStatus() solution = h.getSolution() info = h.getInfo() # Convert status status = _convert_status(model_status) # Extract solution values solution_values = solution.col_value if hasattr(solution, "col_value") else [] dual_values = solution.row_dual if hasattr(solution, "row_dual") else [] reduced_costs = solution.col_dual if hasattr(solution, "col_dual") else [] # Get objective value objective_value = ( info.objective_function_value if hasattr(info, "objective_function_value") else 0.0 ) # Create solution with variable names values = {} for i, var_spec in enumerate(problem_spec.variables): var_name = var_spec.name or f"x{i}" values[var_name] = solution_values[i] if i < len(solution_values) else 0.0 # Create solver statistics solver_stats = { "solve_time": solve_time, "iterations": getattr(info, "simplex_iteration_count", 0), "num_variables": num_vars, "num_constraints": num_constraints, } solution = HiGHSProblem( problem=problem_spec, options=problem.options, values=values, objective_value=objective_value, status=status, is_optimal=status == HiGHSStatus.OPTIMAL, solve_time=solve_time, dual_values=dual_values, reduced_costs=reduced_costs, solver_stats=solver_stats, ) return Success(solution) except Exception as e: return Failure(f"Error solving HiGHs problem: {e}") - Pydantic models (HiGHSProblem, HiGHSProblemSpec, etc.) providing schema and validation for the linear programming problem inputs and outputs.
class HiGHSProblemSpec(BaseModel): """Problem specification for HiGHs.""" sense: HiGHSSense = Field(..., description="Optimization sense") objective: HiGHSObjective = Field(..., description="Objective function") variables: List[HiGHSVariable] = Field(..., description="Variable specifications") constraints: HiGHSConstraints = Field(..., description="Constraint specifications") class HiGHSProblem(BaseProblem): """Complete HiGHS optimization problem.""" problem: HiGHSProblemSpec = Field(..., description="Problem specification") options: Optional[HiGHSOptions] = Field(default=None, description="Solver options") # Base problem properties problem_type: ProblemType = Field(default=ProblemType.LINEAR_PROGRAMMING, description="Problem type") sense: OptimizationSense = Field(..., description="Optimization sense") description: str = Field(default="", description="Problem description") def get_variables(self) -> List[BaseVariable]: """Get all variables in the problem.""" return self.problem.variables