"""
Module containing functions to diagnose unfeasible LP problems.
This module contains the following functions:
- `find_iis`: finds a set of constraints that when removed make the problem solvable.
- `handle_unsolved_problem`: fixes common issues that might be making the optimization problem
unsolvable (like variables without bounds, or with upper-bound smaller than its lower-bound).
- `fix_variables_limits`: Fixes issues caused when variables lower- and upper-bounds are wrongfully set.
"""
from __future__ import annotations
from datetime import datetime
from pathlib import Path
from typing import Dict
from typing import List
from typing import Tuple
import pulp
from wip.constants import OTM_OUTPUTS_FOLDER_PATH
from wip.logging_config import logger
from wip.utils import get_function_kwargs
__all__ = [
"find_iis",
"fix_variables_limits",
"analyze_unfeasible_problems",
"handle_unsolved_problem",
]
[docs]def handle_unsolved_problem(
problem: pulp.LpProblem,
errors: str = "raise",
**solver_kwargs,
) -> pulp.LpProblem:
"""Handle an unsolved problem.
This function handles an unsolved problem by fixing the variables' limits
and trying to solve the problem again.
Parameters
----------
problem : pulp.LpProblem
An unsolved LP problem defined using the PuLP library.
errors : str {'raise', 'ignore'}, default='raise'
How to handle errors. If 'raise', then an exception is raised.
If 'ignore', then the original problem is returned.
**solver_kwargs : Any
Optional keyword arguments to pass to the solver.
Either specify an input parameter named `solver` that's an instance
of a valid PuLP solver, or specify the solver's parameters as
keyword arguments.
Returns
-------
pulp.LpProblem
The fixed LP problem.
Raises
------
ValueError
If `resolve` is set to False and problem status is 'not solved'.
If `errors` is set to `'ignore'`, and the problem fails to be solved.
See Also
--------
fix_variables_limits : Fix the limits of the variables in the optimization problem.
"""
resolve = solver_kwargs.pop('resolve', True)
cbc_solver_kwargs, _ = get_function_kwargs(pulp.PULP_CBC_CMD, **solver_kwargs)
solver = solver_kwargs.pop('solver', pulp.PULP_CBC_CMD(**cbc_solver_kwargs))
if problem.status != pulp.constants.LpStatusNotSolved:
logger.info(
"The problem is not unsolved. Problem status: '%s'.",
pulp.LpStatus[problem.status],
)
return problem
if not resolve:
raise ValueError(
"The problem is not solved. Set 'resolve' to True to solve it."
)
try:
problem.solve(solver, **solver_kwargs)
return problem
except pulp.PulpSolverError as exc:
logger.exception(exc)
if errors == "ignore":
logger.error("Failed to solve the problem. Returning the original problem.")
return problem
raise ValueError("Failed to solve the problem.")
[docs]def find_iis(
infeasible_model: pulp.LpProblem, **solver_kwargs
) -> Tuple[pulp.LpProblem, set]:
"""
Compute the Irreducible Infeasible Set (IIS) of an infeasible LP problem.
An IIS is a minimal set of constraints that makes the problem infeasible.
This function computes the IIS of a given infeasible LP problem using the
PuLP library.
The function deactivates each constraint and checks if the problem is
still infeasible.
Then the function iterates over the deactivated constraints, adding them back
to the problem and checking whether it makes the problem infeasible.
If the problem becomes infeasible, then the constraint is added to
the IIS set and removed once more from the LP problem.
Parameters
----------
infeasible_model : pulp.LpProblem
An infeasible LP problem defined using the PuLP library.
**solver_kwargs : Any
Optional keyword arguments to pass to the solver.
Either specify an input parameter named `solver` that's an instance
of a valid PuLP solver, or specify the solver's parameters as
keyword arguments.
Returns
-------
Tuple[pulp.LpProblem, set]
The unfeasible relaxed problem and a set containing
the names of the constraints that form an IIS.
.. hint::
Because this function solves many iterations of the
optimization problem, a considerable number of logs are generated.
You can suppress these logs by including a parameter `msg=False`
to the function's input parameters.
"""
# The function begins by checking if the problem is unsolved.
# If it is unsolved, then it tries to solve it.
# Prior to trying to find the set of infeasible constraints.
infeasible_model = handle_unsolved_problem(infeasible_model, **solver_kwargs)
cbc_solver_kwargs, _ = get_function_kwargs(pulp.PULP_CBC_CMD, **solver_kwargs)
solver = solver_kwargs.pop("solver", pulp.PULP_CBC_CMD(**cbc_solver_kwargs))
# Check if the model is infeasible
if infeasible_model.status != pulp.constants.LpStatusInfeasible:
logger.info(
"Problem status is not 'unfeasible': '%s'.",
pulp.LpStatus[infeasible_model.status],
)
return infeasible_model, set()
# Initialize an empty set to store the IIS
iis = set()
# Create a new LP problem to store the modified version of the original problem
modified_model = pulp.LpProblem("modified_model", sense=infeasible_model.sense)
modified_model.addVariables(infeasible_model.variables())
modified_model.setObjective(infeasible_model.objective)
# Add lower and upper bound hard limits to the new problem for each variable
# These constraints will serve as safety nets in case the original variable
# was unconstrained
variables = modified_model.variables()
for index, variable in enumerate(variables):
modified_model.addConstraint(variable >= -100_000)
modified_model.addConstraint(variable <= 100_000)
modified_model._variables[index] = variable # pylint: disable=protected-access
# Iterate over each constraint in the original problem,
# deactivate each constraint and check if the problem is still infeasible.
# If the problem is still infeasible, add the constraint to the IIS set
# Otherwise, activate the constraint and move on to the next one
for constraint_name, constraint in infeasible_model.constraints.items():
try:
modified_model.addConstraint(constraint, name=constraint_name)
except pulp.PulpError:
name = constraint_name + datetime.now().strftime("%Y%m%d%H%M%S")
modified_model.addConstraint(constraint, name=name)
status = modified_model.solve(solver)
if status == pulp.constants.LpStatusInfeasible:
iis.add(constraint_name)
modified_model.constraints.pop(constraint_name)
return modified_model, iis # Return the modified model and the IIS set
[docs]def fix_variables_limits(prob: pulp.LpProblem, verbose: bool = True) -> pulp.LpProblem:
"""Fix the limits of the variables in the optimization problem.
This function fixes the following problems with the variables limits:
- Sets the lower-bound to -10,000 if it is not defined.
- Sets the upper-bound to 10,000 if it is not defined.
- Inverts the upper and lower bounds if the upper-bound is smaller than the
lower-bound.
The function only executes the fixes if the optimization problem status is
equal to 'Undefined' (-3), 'Unbounded' (-2) or 'Not Solved' (0).
Parameters
----------
prob : pulp.LpProblem
Optimization problem to fix the variables' limits.
verbose : bool, default=True
Whether to print the name of the variables that had their limits fixed.
Returns
-------
pulp.LpProblem
Optimization problem with the variables' limits fixed.
"""
if prob.status not in [-3, -2, 0]:
logger.info(
"Problem status not valid: %s. "
"Status must be either 'Undefined', 'Unbounded' or 'Not Solved'",
prob.status,
)
return prob
msg = ""
for name, lpvar in prob.variablesDict().items():
lb, ub = lpvar.lowBound, lpvar.upBound
if not isinstance(lb, (float, int)):
msg += f"{name}: variable's lower-bound not being defined. Setting it to -10,000.\n"
lpvar.lowBound = -10_000
if not isinstance(ub, (float, int)):
msg += f"{name}: variable's upper-bound not being defined. Setting it to 10,000.\n"
lpvar.upBound = 10_000
if lb > ub:
lpvar.lowBound = ub
lpvar.upBound = lb
msg += f"{name}: variable's upper-bound smaller than its lower-bound. Inverting them.\n"
if verbose and msg:
logger.warning(msg)
elif verbose:
logger.info("No problems found in the optimization variables...")
return prob
[docs]def analyze_unfeasible_problems(
outputs_folder_path: Path | str | None = None,
) -> Dict[str, List[pulp.LpConstraint]]:
"""Analyze unfeasible problems in the outputs folder.
Parameters
----------
outputs_folder_path : Path | str | None
Path to the outputs' folder. If None, the default outputs folder
is used :param:`wip.constants.OTM_OUTPUTS_FOLDER_PATH`.
The parameter :param:`outputs_folder_path` must contain the '.mps' files
that correspond to the optimization problems to analyze.
Returns
-------
Dict[str, List[pulp.LpConstraint]]
Returns a dictionary with the name of the problem as the key and a list
of the infeasible constraints as value.
"""
outputs_folder_path = outputs_folder_path or OTM_OUTPUTS_FOLDER_PATH
mps_files = list(Path(outputs_folder_path).glob("**/*.mps"))
solver = pulp.PULP_CBC_CMD(msg=False)
infeasible_constraints_summary = {}
for mps_file in mps_files:
problem_name = mps_file.with_suffix("").name
_, prob = pulp.LpProblem.fromMPS(str(mps_file))
lp_constraints = prob.constraints
try:
status = prob.solve(solver)
except pulp.PulpSolverError as exc:
logger.exception(exc)
logger.error("Failed to solve problem range: %s", problem_name)
status = None
if status == pulp.LpStatusInfeasible:
logger.warning(
"Problem '%s' is unfeasible, finding unfeasible constraints...",
problem_name,
)
_, infeasible_constraints = find_iis(prob, solver=solver)
logger.warning(
"Problem '%s' has %d unfeasible constraints: %s",
problem_name,
len(infeasible_constraints),
", ".join(infeasible_constraints),
)
infeasible_constraints_summary[problem_name] = [
lp_constraints[infeasible_constraint]
for infeasible_constraint in infeasible_constraints
]
return infeasible_constraints_summary