\n",
"**Note:**\n",
"Degeneracy Hunter requires a suitable MILP solver. This example uses the open-source solver SCIP (https://scipopt.org/), however users may specify another solver of their choice if they have one available.\n",
"

\n",
"\n",
"## What does Degeneracy Mean?\n",
"\n",
"In simple terms, a degenerate model contains one or more constraints that do not add any additional information that is not already included in other constraints in the model. The simplest example of this is the case where a constraint in the model is duplicated. For example, consider the model below:\n",
"\n",
"$$\\begin{align*}\n",
"& x_1 + x_2 = 1 \\\\\n",
"& x_1 + x_2 = 1 \\\\\n",
"\\end{align*} $$\n",
"\n",
"Notice the two equality constraints are identical and thus redundant. This means the constraint qualifications that solvers rely on (e.g., [Linear Independence Constraint Qualification or LICQ](https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions#Regularity_conditions_(or_constraint_qualifications))) do not hold which has three important implications:\n",
"\n",
"1. The optimal solution may not be mathematically well-defined (e.g., the dual variables are not unique)\n",
"2. The calculations performed by the optimization solver may become numerically poorly scaled\n",
"3. Theoretical convergence properties of optimization algorithms may not hold\n",
"\n",
"Put another way, for a deterministic (square) problem we required that the number of equality constraints be equal to the number of free variables. In this case, there appear to be two equality constraints but in reality there is effectively only one as the two constraints are the same. Thus, the problem is not well defined and there exist a family of solutions that can satisfy the constraints given; any combination of values for ``x1`` and ``x2`` that sum to one will satisfy the constraints as written.\n",
"\n",
"In practice, degeneracies are rarely as straight-forward as a duplicated constraint. A more common occurrence is a set of linearly dependent constraints; that is a system of constraints where one constraint in the set can be formed by a linear combination of other constraints in the set. For example:\n",
"\n",
"$$\\begin{align*}\n",
"& x_1 + x_2 + x_3 = 1 \\\\\n",
"& 2x_1 + 2x_2 + 2x_3 = 2 \\\\\n",
"\\end{align*} $$\n",
"\n",
"Here, the second constraint can be formed by multiplying the first constraint by two. Another common example of linearly dependent constraints is the combination of a set of material balances for all components in a system and an overall material balance. In this case, the overall material balances can be formed by adding all the individual component balances together. Depending on the number of components being modeled, this system of constraints can be quite large, but the end result is the same; the model effectively has one less constraint than it would appear to have.\n",
"\n",
"The absolute best defense against this is to detect degenerate equations and reformulate the model to remove them; this is the purpose of Degeneracy Hunter. Let's see it in action."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Setup\n",
"\n",
"We start by importing Pyomo and the IDAES Diagnostics Toolbox."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import pyomo.environ as pyo\n",
"\n",
"from idaes.core.util.model_diagnostics import DiagnosticsToolbox"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example: Linear Program with Redundant Equality Constraints"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's apply these tools to a poorly formulated optimization problem:\n",
"\n",
"$$\\begin{align*} \\min_{\\mathbf{x}} \\quad & \\sum_{i=\\{1,...,3\\}} x_i \\\\\n",
"\\mathrm{s.t.}~~& x_1 + x_2 \\geq 1 \\\\\n",
"& x_1 + x_2 + x_3 = 1 \\\\\n",
"& x_2 - 2 x_3 \\leq 1 \\\\\n",
"& x_1 + x_3 \\geq 1 \\\\\n",
"& x_1 + x_2 + x_3 = 1 \\\\\n",
"\\end{align*} $$\n",
"\n",
"As you can see, this is similar to our example above with duplicated equality constraints.\n",
"\n",
"The cell below shows how to construct this model in Pyomo."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"def build_example(include_redundant_constraint=True):\n",
" m = pyo.ConcreteModel()\n",
"\n",
" m.I = pyo.Set(initialize=[i for i in range(1, 4)])\n",
"\n",
" m.x = pyo.Var(m.I, bounds=(0, 5), initialize=1.0)\n",
"\n",
" m.con1 = pyo.Constraint(expr=m.x[1] + m.x[2] >= 1)\n",
" m.con2 = pyo.Constraint(expr=m.x[1] + m.x[2] + m.x[3] == 1)\n",
" m.con3 = pyo.Constraint(expr=m.x[2] - 2 * m.x[3] <= 1)\n",
" m.con4 = pyo.Constraint(expr=m.x[1] + m.x[3] >= 1)\n",
" \n",
" if include_redundant_constraint:\n",
" m.con5 = pyo.Constraint(expr=m.x[1] + m.x[2] + m.x[3] == 1)\n",
"\n",
" m.obj = pyo.Objective(expr=sum(m.x[i] for i in m.I))\n",
" \n",
" return m\n",
"\n",
"m = build_example()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Check for Structural Issues\n",
"\n",
"Before we try to solve the model, the first thing we should do is use the Diagnostics Toolbox to check for any structural issues in our model. The cell below creates an instance of the Diagnostics Toolbox and calls the ``report_structural_issues`` method."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"====================================================================================\n",
"Model Statistics\n",
"\n",
" Activated Blocks: 1 (Deactivated: 0)\n",
" Free Variables in Activated Constraints: 3 (External: 0)\n",
" Free Variables with only lower bounds: 0\n",
" Free Variables with only upper bounds: 0\n",
" Free Variables with upper and lower bounds: 3\n",
" Fixed Variables in Activated Constraints: 0 (External: 0)\n",
" Activated Equality Constraints: 2 (Deactivated: 0)\n",
" Activated Inequality Constraints: 3 (Deactivated: 0)\n",
" Activated Objectives: 1 (Deactivated: 0)\n",
"\n",
"------------------------------------------------------------------------------------\n",
"2 WARNINGS\n",
"\n",
" WARNING: 1 Degree of Freedom\n",
" WARNING: Structural singularity found\n",
" Under-Constrained Set: 3 variables, 2 constraints\n",
" Over-Constrained Set: 0 variables, 0 constraints\n",
"\n",
"------------------------------------------------------------------------------------\n",
"0 Cautions\n",
"\n",
" No cautions found!\n",
"\n",
"------------------------------------------------------------------------------------\n",
"Suggested next steps:\n",
"\n",
" display_underconstrained_set()\n",
"\n",
"====================================================================================\n"
]
}
],
"source": [
"dt = DiagnosticsToolbox(m)\n",
"dt.report_structural_issues()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As you can see, the toolbox is reporting one degree of freedom and a structural singularity. In this case, these are both expected as we are trying to solve an optimization problem with one degree of freedom so we can move on to the next step. \n",
"\n",
"### Evaluate the initial point\n",
"\n",
"Before we try to solve our degenerate model, it can often be useful to check the state of the model at the initial step seen by the solver. The cell below creates an instance of Ipopt and sets the iteration limit to 0 so that it terminates at the initial condition."
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ipopt 3.13.2: max_iter=0\n",
"\n",
"\n",
"******************************************************************************\n",
"This program contains Ipopt, a library for large-scale nonlinear optimization.\n",
" Ipopt is released as open source code under the Eclipse Public License (EPL).\n",
" For more information visit http://projects.coin-or.org/Ipopt\n",
"\n",
"This version of Ipopt was compiled from source code available at\n",
" https://github.com/IDAES/Ipopt as part of the Institute for the Design of\n",
" Advanced Energy Systems Process Systems Engineering Framework (IDAES PSE\n",
" Framework) Copyright (c) 2018-2019. See https://github.com/IDAES/idaes-pse.\n",
"\n",
"This version of Ipopt was compiled using HSL, a collection of Fortran codes\n",
" for large-scale scientific computation. All technical papers, sales and\n",
" publicity material resulting from use of the HSL codes within IPOPT must\n",
" contain the following acknowledgement:\n",
" HSL, a collection of Fortran codes for large-scale scientific\n",
" computation. See http://www.hsl.rl.ac.uk.\n",
"******************************************************************************\n",
"\n",
"This is Ipopt version 3.13.2, running with linear solver ma27.\n",
"\n",
"Number of nonzeros in equality constraint Jacobian...: 6\n",
"Number of nonzeros in inequality constraint Jacobian.: 6\n",
"Number of nonzeros in Lagrangian Hessian.............: 0\n",
"\n",
"Total number of variables............................: 3\n",
" variables with only lower bounds: 0\n",
" variables with lower and upper bounds: 3\n",
" variables with only upper bounds: 0\n",
"Total number of equality constraints.................: 2\n",
"Total number of inequality constraints...............: 3\n",
" inequality constraints with only lower bounds: 2\n",
" inequality constraints with lower and upper bounds: 0\n",
" inequality constraints with only upper bounds: 1\n",
"\n",
"iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls\n",
" 0 3.0000000e+00 2.00e+00 1.00e+00 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0\n",
"\n",
"Number of Iterations....: 0\n",
"\n",
" (scaled) (unscaled)\n",
"Objective...............: 3.0000000000000000e+00 3.0000000000000000e+00\n",
"Dual infeasibility......: 1.0000000000000000e+00 1.0000000000000000e+00\n",
"Constraint violation....: 2.0000000000000000e+00 2.0000000000000000e+00\n",
"Complementarity.........: 4.0000000499999997e+00 4.0000000499999997e+00\n",
"Overall NLP error.......: 4.0000000499999997e+00 4.0000000499999997e+00\n",
"\n",
"\n",
"Number of objective function evaluations = 1\n",
"Number of objective gradient evaluations = 1\n",
"Number of equality constraint evaluations = 1\n",
"Number of inequality constraint evaluations = 1\n",
"Number of equality constraint Jacobian evaluations = 1\n",
"Number of inequality constraint Jacobian evaluations = 1\n",
"Number of Lagrangian Hessian evaluations = 0\n",
"Total CPU secs in IPOPT (w/o function evaluations) = 0.000\n",
"Total CPU secs in NLP function evaluations = 0.000\n",
"\n",
"EXIT: Maximum Number of Iterations Exceeded.\n",
"WARNING: Loading a SolverResults object with a warning status into\n",
"model.name=\"unknown\";\n",
" - termination condition: maxIterations\n",
" - message from solver: Ipopt 3.13.2\\x3a Maximum Number of Iterations\n",
" Exceeded.\n"
]
},
{
"data": {
"text/plain": [
"{'Problem': [{'Lower bound': -inf, 'Upper bound': inf, 'Number of objectives': 1, 'Number of constraints': 5, 'Number of variables': 3, 'Sense': 'unknown'}], 'Solver': [{'Status': 'warning', 'Message': 'Ipopt 3.13.2\\\\x3a Maximum Number of Iterations Exceeded.', 'Termination condition': 'maxIterations', 'Id': 400, 'Error rc': 0, 'Time': 0.004778385162353516}], 'Solution': [OrderedDict([('number of solutions', 0), ('number of solutions displayed', 0)])]}"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solver = pyo.SolverFactory(\"ipopt\")\n",
"\n",
"# Specifying an iteration limit of 0 allows us to inspect the initial point\n",
"solver.options[\"max_iter\"] = 0\n",
"\n",
"# \"Solving\" the model with an iteration limit of 0 load the initial point and applies\n",
"# any preprocessors (e.g., enforces bounds)\n",
"solver.solve(m, tee=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Identify constraints with large residuals at the initial point\n",
"\n",
"With the solution at the initial point, we can then use the Diagnostics Toolbox to check the residuals of all constraints at the initial point."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"====================================================================================\n",
"The following constraint(s) have large residuals (>1.0E-05):\n",
"\n",
" con2: 2.00000E+00\n",
" con5: 2.00000E+00\n",
"\n",
"====================================================================================\n"
]
}
],
"source": [
"# Check for large residuals\n",
"dt.display_constraints_with_large_residuals()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can also check for variables which are close to (or outside of) their bounds."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"====================================================================================\n",
"The following variable(s) have values close to their bounds (abs=1.0E-04, rel=1.0E-04):\n",
"\n",
"\n",
"====================================================================================\n"
]
}
],
"source": [
"dt.display_variables_near_bounds()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Solve the optimization problem and extract the solution\n",
"\n",
"There appear to be no significant issues at the initial point, so let us move on to solving the optimization problem."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ipopt 3.13.2: max_iter=50\n",
"\n",
"\n",
"******************************************************************************\n",
"This program contains Ipopt, a library for large-scale nonlinear optimization.\n",
" Ipopt is released as open source code under the Eclipse Public License (EPL).\n",
" For more information visit http://projects.coin-or.org/Ipopt\n",
"\n",
"This version of Ipopt was compiled from source code available at\n",
" https://github.com/IDAES/Ipopt as part of the Institute for the Design of\n",
" Advanced Energy Systems Process Systems Engineering Framework (IDAES PSE\n",
" Framework) Copyright (c) 2018-2019. See https://github.com/IDAES/idaes-pse.\n",
"\n",
"This version of Ipopt was compiled using HSL, a collection of Fortran codes\n",
" for large-scale scientific computation. All technical papers, sales and\n",
" publicity material resulting from use of the HSL codes within IPOPT must\n",
" contain the following acknowledgement:\n",
" HSL, a collection of Fortran codes for large-scale scientific\n",
" computation. See http://www.hsl.rl.ac.uk.\n",
"******************************************************************************\n",
"\n",
"This is Ipopt version 3.13.2, running with linear solver ma27.\n",
"\n",
"Number of nonzeros in equality constraint Jacobian...: 6\n",
"Number of nonzeros in inequality constraint Jacobian.: 6\n",
"Number of nonzeros in Lagrangian Hessian.............: 0\n",
"\n",
"Total number of variables............................: 3\n",
" variables with only lower bounds: 0\n",
" variables with lower and upper bounds: 3\n",
" variables with only upper bounds: 0\n",
"Total number of equality constraints.................: 2\n",
"Total number of inequality constraints...............: 3\n",
" inequality constraints with only lower bounds: 2\n",
" inequality constraints with lower and upper bounds: 0\n",
" inequality constraints with only upper bounds: 1\n",
"\n",
"iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls\n",
" 0 3.0000000e+00 2.00e+00 1.00e+00 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0\n",
" 1 1.3934810e+00 3.93e-01 2.17e-01 -1.0 1.23e+00 - 7.90e-01 8.03e-01h 1\n",
" 2 1.0184419e+00 1.84e-02 1.26e-02 -1.7 7.02e-01 - 9.41e-01 9.53e-01h 1\n",
" 3 1.0011246e+00 1.12e-03 3.82e-02 -2.5 1.50e-02 - 1.00e+00 9.39e-01h 1\n",
" 4 1.0006914e+00 6.91e-04 3.12e+00 -2.5 3.17e-03 - 1.00e+00 3.85e-01h 1\n",
" 5 1.0002664e+00 2.66e-04 4.35e+00 -2.5 1.12e-03 - 1.00e+00 6.15e-01h 1\n",
" 6 1.0001115e+00 1.12e-04 1.07e+01 -2.5 4.99e-04 - 1.00e+00 5.82e-01h 1\n",
" 7 1.0000788e+00 7.88e-05 4.33e+01 -2.5 1.88e-04 - 1.00e+00 2.94e-01f 2\n",
" 8 1.0000153e+00 1.53e-05 2.19e+01 -2.5 6.85e-05 - 1.00e+00 8.08e-01h 1\n",
" 9 1.0000118e+00 1.18e-05 2.78e+02 -2.5 3.47e-05 - 1.00e+00 2.45e-01f 2\n",
"iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls\n",
" 10 1.0000014e+00 1.44e-06 2.83e-08 -2.5 7.79e-06 - 1.00e+00 1.00e+00h 1\n",
" 11 1.0000000e+00 1.39e-09 1.84e-11 -5.7 2.56e-06 - 1.00e+00 1.00e+00h 1\n",
" 12 1.0000000e+00 1.39e-09 1.24e+02 -8.6 1.16e-08 - 1.00e+00 9.54e-07h 21\n",
" 13 9.9999999e-01 9.82e-09 1.14e-13 -8.6 1.33e-08 - 1.00e+00 1.00e+00s 22\n",
" 14 9.9999999e-01 9.96e-09 6.46e-14 -8.6 2.29e-10 - 1.00e+00 1.00e+00s 22\n",
" 15 9.9999999e-01 9.96e-09 1.82e+02 -9.0 4.00e-11 - 1.00e+00 9.54e-07h 21\n",
" 16 9.9999999e-01 1.00e-08 1.52e-13 -9.0 5.89e-11 - 1.00e+00 1.00e+00s 22\n",
"\n",
"Number of Iterations....: 16\n",
"\n",
" (scaled) (unscaled)\n",
"Objective...............: 9.9999999000238915e-01 9.9999999000238915e-01\n",
"Dual infeasibility......: 1.5188693260016487e-13 1.5188693260016487e-13\n",
"Constraint violation....: 9.9976108502985994e-09 9.9976108502985994e-09\n",
"Complementarity.........: 9.2217032157601989e-10 9.2217032157601989e-10\n",
"Overall NLP error.......: 9.9976108502985994e-09 9.9976108502985994e-09\n",
"\n",
"\n",
"Number of objective function evaluations = 111\n",
"Number of objective gradient evaluations = 17\n",
"Number of equality constraint evaluations = 111\n",
"Number of inequality constraint evaluations = 111\n",
"Number of equality constraint Jacobian evaluations = 17\n",
"Number of inequality constraint Jacobian evaluations = 17\n",
"Number of Lagrangian Hessian evaluations = 16\n",
"Total CPU secs in IPOPT (w/o function evaluations) = 0.000\n",
"Total CPU secs in NLP function evaluations = 0.000\n",
"\n",
"EXIT: Optimal Solution Found.\n"
]
},
{
"data": {
"text/plain": [
"{'Problem': [{'Lower bound': -inf, 'Upper bound': inf, 'Number of objectives': 1, 'Number of constraints': 5, 'Number of variables': 3, 'Sense': 'unknown'}], 'Solver': [{'Status': 'ok', 'Message': 'Ipopt 3.13.2\\\\x3a Optimal Solution Found', 'Termination condition': 'optimal', 'Id': 0, 'Error rc': 0, 'Time': 0.04887509346008301}], 'Solution': [OrderedDict([('number of solutions', 0), ('number of solutions displayed', 0)])]}"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solver.options[\"max_iter\"] = 50\n",
"solver.solve(m, tee=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We got lucky here. Ipopt implements several algorithmic and numerical safeguards to handle (mildy) degenerate equations. Nevertheless, notice the last column of the Ipopt output labeled `ls`. This is the number of line search evaluations. For iterations 0 to 11, `ls` is 1, which means Ipopt is taking full steps. For iterations 12 to 16, however, `ls` is greater than 20. This means Ipopt is struggling (a little) to converge to the solution.\n",
"\n",
"The cell below shows the values of the variables at the solution."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"x : Size=3, Index=I\n",
" Key : Lower : Value : Upper : Fixed : Stale : Domain\n",
" 1 : 0 : 1.0000000099975996 : 5 : False : False : Reals\n",
" 2 : 0 : 0.0 : 5 : False : False : Reals\n",
" 3 : 0 : 0.0 : 5 : False : False : Reals\n"
]
}
],
"source": [
"m.x.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Check the rank of the Jacobian of the equality constraints\n",
"\n",
"One way to check for the presence of degenerate equations is to calculate the rank of the Jacobian matrix of the equality constraints. A singular value near 0 indicates the Jacobian is rank deficient, and for each near-zero singular value there is likely one degenerate constraint.\n",
"\n",
"The Diagnostics Toolbox contains a Singular Value Decomposition (SVD) toolbox which can be used to determine the number of small singular values in the Jacobian for a model as shown below."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"====================================================================================\n",
"\n",
"Number of Singular Values less than 1.0E-06 is 1\n",
"\n",
"====================================================================================\n"
]
}
],
"source": [
"svd = dt.prepare_svd_toolbox()\n",
"svd.display_rank_of_equality_constraints()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As can be seen above, there is one singular value less than 1e-6, suggesting we have one degenerate constraint."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Finding Irreducible Degenerate Sets (IDS)\n",
"\n",
"Next, we can use Degeneracy Hunter to identify irreducible degenerate sets; that is, the smallest set of constraints that contain a redundant constraint.\n",
"\n",
"Degeneracy Hunter first identifies candidate degenerate equations by solving a mixed integer linear program (MILP). It then iterates through the candidate equations and solves a second MILP for each to compute the irreducible degenerate set that must contain the candidate equation.\n",
"\n",
"\n",
"**Note:**\n",
"Degeneracy Hunter requires a suitable MILP solver, users can specify their solver of choice via a configuration argument. The default option is SCIP (https://scipopt.org/) which is an open-source solver.\n",
"

\n",
"\n",
"The cell below shows how to create an instance of Degeneracy Hunter and generate a report of the irreducible degenerate sets."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2023-11-17 14:33:20 [INFO] idaes.core.util.model_diagnostics: Searching for Candidate Equations\n",
"2023-11-17 14:33:20 [INFO] idaes.core.util.model_diagnostics: Building MILP model.\n",
"2023-11-17 14:33:20 [INFO] idaes.core.util.model_diagnostics: Solving Candidates MILP model.\n",
"2023-11-17 14:33:20 [INFO] idaes.core.util.model_diagnostics: Searching for Irreducible Degenerate Sets\n",
"2023-11-17 14:33:20 [INFO] idaes.core.util.model_diagnostics: Building MILP model to compute irreducible degenerate set.\n",
"Solving MILP 1 of 2.\n",
"2023-11-17 14:33:20 [INFO] idaes.core.util.model_diagnostics: Solving IDS MILP for constraint con2.\n",
"Solving MILP 2 of 2.\n",
"2023-11-17 14:33:20 [INFO] idaes.core.util.model_diagnostics: Solving IDS MILP for constraint con5.\n",
"====================================================================================\n",
"Irreducible Degenerate Sets\n",
"\n",
" Irreducible Degenerate Set 0\n",
" nu Constraint Name\n",
" 1.0 con2\n",
" -1.0 con5\n",
"\n",
" Irreducible Degenerate Set 1\n",
" nu Constraint Name\n",
" -1.0 con2\n",
" 1.0 con5\n",
"\n",
"====================================================================================\n"
]
}
],
"source": [
"dh = dt.prepare_degeneracy_hunter()\n",
"dh.report_irreducible_degenerate_sets()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As can be seen above, Degeneracy Hunter identified two constraints as potentially redundant (the duplicate constraints ``con2`` and ``con5``). Degeneracy Hunter then reports an Irreducible Degenerate Set for each of these constraints, which in the case as identical. More complex models may have partially overlapping IDS's.\n",
"\n",
"These results show us that ``con2`` and ``con5`` are mutually redundant; i.e., we can eliminate one of these with no effect on the model solution."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Reformulate Model to Remove Redundant Constraint\n",
"\n",
"Now let's reformulate the model by removing the redundant equality constraint ``con5`` and solve the reformulated model."
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Ipopt 3.13.2: max_iter=50\n",
"\n",
"\n",
"******************************************************************************\n",
"This program contains Ipopt, a library for large-scale nonlinear optimization.\n",
" Ipopt is released as open source code under the Eclipse Public License (EPL).\n",
" For more information visit http://projects.coin-or.org/Ipopt\n",
"\n",
"This version of Ipopt was compiled from source code available at\n",
" https://github.com/IDAES/Ipopt as part of the Institute for the Design of\n",
" Advanced Energy Systems Process Systems Engineering Framework (IDAES PSE\n",
" Framework) Copyright (c) 2018-2019. See https://github.com/IDAES/idaes-pse.\n",
"\n",
"This version of Ipopt was compiled using HSL, a collection of Fortran codes\n",
" for large-scale scientific computation. All technical papers, sales and\n",
" publicity material resulting from use of the HSL codes within IPOPT must\n",
" contain the following acknowledgement:\n",
" HSL, a collection of Fortran codes for large-scale scientific\n",
" computation. See http://www.hsl.rl.ac.uk.\n",
"******************************************************************************\n",
"\n",
"This is Ipopt version 3.13.2, running with linear solver ma27.\n",
"\n",
"Number of nonzeros in equality constraint Jacobian...: 3\n",
"Number of nonzeros in inequality constraint Jacobian.: 6\n",
"Number of nonzeros in Lagrangian Hessian.............: 0\n",
"\n",
"Total number of variables............................: 3\n",
" variables with only lower bounds: 0\n",
" variables with lower and upper bounds: 3\n",
" variables with only upper bounds: 0\n",
"Total number of equality constraints.................: 1\n",
"Total number of inequality constraints...............: 3\n",
" inequality constraints with only lower bounds: 2\n",
" inequality constraints with lower and upper bounds: 0\n",
" inequality constraints with only upper bounds: 1\n",
"\n",
"iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls\n",
" 0 3.0000000e+00 2.00e+00 6.30e-01 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0\n",
" 1 1.3934810e+00 3.93e-01 1.34e-01 -1.0 1.23e+00 - 7.90e-01 8.03e-01f 1\n",
" 2 1.0184419e+00 1.84e-02 9.15e-03 -1.7 7.02e-01 - 9.41e-01 9.53e-01h 1\n",
" 3 1.0011246e+00 1.12e-03 3.88e-02 -2.5 1.50e-02 - 1.00e+00 9.39e-01h 1\n",
" 4 1.0006914e+00 6.91e-04 3.12e+00 -2.5 3.17e-03 - 1.00e+00 3.85e-01h 1\n",
" 5 1.0002664e+00 2.66e-04 4.35e+00 -2.5 1.12e-03 - 1.00e+00 6.15e-01h 1\n",
" 6 1.0001115e+00 1.12e-04 1.07e+01 -2.5 5.00e-04 - 1.00e+00 5.81e-01h 1\n",
" 7 1.0000788e+00 7.88e-05 4.34e+01 -2.5 1.88e-04 - 1.00e+00 2.93e-01f 2\n",
" 8 1.0000154e+00 1.54e-05 2.26e+01 -2.5 6.89e-05 - 1.00e+00 8.04e-01h 1\n",
" 9 1.0000118e+00 1.18e-05 2.98e+02 -2.5 3.64e-05 - 1.00e+00 2.33e-01f 2\n",
"iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls\n",
" 10 1.0000020e+00 2.04e-06 1.33e+02 -2.5 9.72e-06 - 1.00e+00 8.28e-01h 1\n",
" 11 1.0000016e+00 1.61e-06 2.26e+03 -2.5 4.79e-06 - 1.00e+00 2.12e-01f 2\n",
" 12 1.0000002e+00 2.46e-07 8.72e+02 -2.5 1.20e-06 - 1.00e+00 8.47e-01h 1\n",
" 13 1.0000002e+00 1.95e-07 1.71e+04 -2.5 7.02e-07 - 1.00e+00 2.09e-01f 2\n",
" 14 1.0000000e+00 1.54e-08 3.23e+03 -2.5 1.50e-07 - 1.00e+00 9.21e-01h 1\n",
" 15 1.0000000e+00 1.15e-08 9.99e+04 -2.5 6.89e-08 - 1.00e+00 2.54e-01f 2\n",
" 16 1.0000000e+00 2.22e-16 2.83e-08 -2.5 8.21e-09 - 1.00e+00 1.00e+00h 1\n",
" 17 1.0000000e+00 2.22e-16 4.14e-11 -8.6 8.25e-16 - 1.00e+00 1.00e+00 0\n",
"\n",
"Number of Iterations....: 17\n",
"\n",
" (scaled) (unscaled)\n",
"Objective...............: 9.9999999999999978e-01 9.9999999999999978e-01\n",
"Dual infeasibility......: 4.1425156707686206e-11 4.1425156707686206e-11\n",
"Constraint violation....: 2.2204460492503131e-16 2.2204460492503131e-16\n",
"Complementarity.........: 2.6658012082875325e-09 2.6658012082875325e-09\n",
"Overall NLP error.......: 2.6658012082875325e-09 2.6658012082875325e-09\n",
"\n",
"\n",
"Number of objective function evaluations = 23\n",
"Number of objective gradient evaluations = 18\n",
"Number of equality constraint evaluations = 23\n",
"Number of inequality constraint evaluations = 23\n",
"Number of equality constraint Jacobian evaluations = 18\n",
"Number of inequality constraint Jacobian evaluations = 18\n",
"Number of Lagrangian Hessian evaluations = 17\n",
"Total CPU secs in IPOPT (w/o function evaluations) = 0.002\n",
"Total CPU secs in NLP function evaluations = 0.000\n",
"\n",
"EXIT: Optimal Solution Found.\n"
]
},
{
"data": {
"text/plain": [
"{'Problem': [{'Lower bound': -inf, 'Upper bound': inf, 'Number of objectives': 1, 'Number of constraints': 4, 'Number of variables': 3, 'Sense': 'unknown'}], 'Solver': [{'Status': 'ok', 'Message': 'Ipopt 3.13.2\\\\x3a Optimal Solution Found', 'Termination condition': 'optimal', 'Id': 0, 'Error rc': 0, 'Time': 0.006506204605102539}], 'Solution': [OrderedDict([('number of solutions', 0), ('number of solutions displayed', 0)])]}"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"m2 = build_example(include_redundant_constraint=False)\n",
"\n",
"solver.solve(m2, tee=True)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"First, let us check to see if the optimal solution has changed."
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"x : Size=3, Index=I\n",
" Key : Lower : Value : Upper : Fixed : Stale : Domain\n",
" 1 : 0 : 1.0000000005924994 : 5 : False : False : Reals\n",
" 2 : 0 : 0.0 : 5 : False : False : Reals\n",
" 3 : 0 : 4.55844318120227e-11 : 5 : False : False : Reals\n"
]
}
],
"source": [
"m2.x.display()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We get the same answer as before, but careful inspection of the Ipopt output reveals a subtle improvement. Notice `ls` is only 1 or 2 for all of the iterations, in contrast to more than 20 for the original model. This means Ipopt is taking (nearly) full steps for all iterations.\n",
"\n",
"Let's also compare the number of function evaluations.\n",
"\n",
"Original model (using Ipopt 3.13.2 with `ma27`):\n",
"```\n",
"Number of objective function evaluations = 111\n",
"Number of objective gradient evaluations = 17\n",
"Number of equality constraint evaluations = 111\n",
"Number of inequality constraint evaluations = 111\n",
"Number of equality constraint Jacobian evaluations = 17\n",
"Number of inequality constraint Jacobian evaluations = 17\n",
"Number of Lagrangian Hessian evaluations = 16\n",
"```\n",
"\n",
"Reformulated model (using Ipopt 3.13.2 with `ma27`):\n",
"```\n",
"Number of objective function evaluations = 23\n",
"Number of objective gradient evaluations = 18\n",
"Number of equality constraint evaluations = 23\n",
"Number of inequality constraint evaluations = 23\n",
"Number of equality constraint Jacobian evaluations = 18\n",
"Number of inequality constraint Jacobian evaluations = 18\n",
"Number of Lagrangian Hessian evaluations = 17\n",
"```\n",
"\n",
"Removing a **single redundant constraint** reduced the number of objective and constraint evaluations by a **factor of 5**!\n",
"\n",
"Often degenerate equations have a much worse impact on large-scale problems; for example, degenerate equations can cause Ipopt to require many more iterations or terminate at an infeasible point.\n"
]
}
],
"metadata": {
"celltoolbar": "Tags",
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.11.5"
}
},
"nbformat": 4,
"nbformat_minor": 3
}