| |||||||||||
| |||||||||||
Python notebooks Description Python notebooks available in the GitHub repository python-notebooks.
Source Files By clicking on a file name, a preview is opened at the bottom of this page. inscribed_square.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# **Inscribed square problem with Xpress NonLinear and Xpress Global**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"***inscribed_square.ipynb***\n",
"\n",
"This example shows how to use FICO® Xpress NonLinear (SLP) or FICO® Xpress Global to solve an instance of the inscribed square problem.\n",
"\n",
"<!--*This example requires a license for the FICO® Xpress Global solver. Click on [this link](https://www.fico.com/en/fico-xpress-trial-and-licensing-options) for more information about trial and licensing options.*-->\n",
"\n",
"© Copyright 2025 Fair Isaac Corporation\n",
"\n",
"Licensed under the Apache License, Version 2.0 (the \"License\"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0.\n",
" \n",
"Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
"\n",
"This example uses FICO® Xpress software. By running it, you agree to the Community License terms of the [Xpress Shrinkwrap License Agreement](https://community.fico.com/s/contentdocument/06980000002h0i5AAA) with respect to the FICO® Xpress software. See the [licensing options](https://www.fico.com/en/fico-xpress-trial-and-licensing-options) overview for additional details and information about obtaining a paid license."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Install the xpress package\n",
"%pip install -q xpress"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The inscribed square problem, also known as the square peg problem or the Toeplitz' conjecture, is an unsolved question in geometry: Does every plane simple closed curve contain all four vertices of some square? The problem was proposed by [Otto Toeplitz in 1911](https://en.wikipedia.org/wiki/Inscribed_square_problem).\n",
"The next example is a special instance of the problem, and computes a **maximal inscribing square** for the curve defined by: \n",
"\n",
"$$(\\sin(t) \\cdot \\cos(t), \\sin(t) \\cdot t), t \\in [-\\pi,\\pi]$$\n",
"\n",
"[Source in MINLPLIB](https://www.minlplib.org/inscribedsquare01.html)\n",
"\n",
"The problem is formulated using decision variables $t_i, \\forall i = 1..4$, with values in the range $[-\\pi,\\pi]$, corresponding to the four values of the parameter $t$. Then, $x$ and $y$ are the coordinates of the first corner of the square, while ($a, b$) is a vector pointing to a second vertex. The remaining vertices are given by combining $x, y, a, b$. The length of the vector ($a, b$) is exactly the side length of the square, which we aim at maximizing.\n",
"\n",
"The first two constraints define $x$ and $y$ as the coordinates of the first point:\n",
"$$\n",
"\\begin{array}{llll}\n",
"& \\qquad \\sin(t_1) \\cdot \\cos(t_1) = x \\\\\n",
"& \\qquad \\sin(t_1) \\cdot t_1 = y \\\\\n",
"\\end{array}\n",
"$$\n",
"\n",
"The next two constraints define the coordinates of the second vertex by adding the pointed vector ($a$, $b$) to the first point ($x$, $y$):\n",
"$$\n",
"\\begin{array}{llll}\n",
"& \\qquad \\sin(t_2) \\cdot \\cos(t_2) = x + a\\\\\n",
"& \\qquad \\sin(t_2) \\cdot t_2 = y + b \\\\\n",
"\\end{array}\n",
"$$\n",
"\n",
"The remaining four constraints make sure that we define a square by defining its remaining two vertices as combinations of ($x$, $y$) and the vector ($a$, $b$):\n",
"$$\n",
"\\begin{array}{llll}\n",
"& \\qquad \\sin(t_3) \\cdot \\cos(t_3) = x - b \\\\\n",
"& \\qquad \\sin(t_3) \\cdot t_3 = y + a \\\\\n",
"& \\qquad \\sin(t_4) \\cdot \\cos(t_4) = x + a - b \\\\\n",
"& \\qquad \\sin(t_4) \\cdot t_4 = y + a + b \\\\\n",
"\\end{array}\n",
"$$\n",
"\n",
"The objective is to maximize the length of one (or each) side of the square:\n",
"$$\n",
"\\begin{array}{llll}\n",
"& \\qquad \\max a^2 + b^2\n",
"\\end{array}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import xpress as xp\n",
"import math\n",
"import numpy as np\n",
"from matplotlib import pyplot as plt\n",
"from collections import namedtuple\n",
"\n",
"p = xp.problem()\n",
"\n",
"# Add the variables, note that we force the (a, b) vector to have positive components to break symmetry.\n",
"t1 = p.addVariable(name=\"t1\", lb=-math.pi, ub=math.pi) # t1..t4 are the four values of the parameter t.\n",
"t2 = p.addVariable(name=\"t2\", lb=-math.pi, ub=math.pi)\n",
"t3 = p.addVariable(name=\"t3\", lb=-math.pi, ub=math.pi)\n",
"t4 = p.addVariable(name=\"t4\", lb=-math.pi, ub=math.pi)\n",
"x = p.addVariable(name=\"x\") # x and y are the (x,y) coordinates of the first corner of the square.\n",
"y = p.addVariable(name=\"y\")\n",
"a = p.addVariable(name=\"a\", lb=0) # (a, b) is a vector pointing to a second vertex, all the other vertices are given by a combination of x..b.\n",
"b = p.addVariable(name=\"b\", lb=0) \n",
"\n",
"# set initial values for the local solvers\n",
"p.nlpsetinitval([t1, t2, t4, x, y, a, b], [-math.pi, -math.pi/2, math.pi/2, 0, 0, 1, 1])\n",
"\n",
"# the first two constraints define x and y as the coordinates of the first point\n",
"p.addConstraint(xp.sin(t1) * xp.cos(t1) == x)\n",
"p.addConstraint(xp.sin(t1) * t1 == y)\n",
"# the next two constraints define the coordinates of the second vertex by adding the pointed vector (a,b) to the first point (x,y).\n",
"p.addConstraint(xp.sin(t2) * xp.cos(t2) == x + a)\n",
"p.addConstraint(xp.sin(t2) * t2 == y + b)\n",
"# the remaining four constraints make sure that we define a square by defining its remaining two vertices as combinations of (x,y) and the vector (a,b)\n",
"p.addConstraint(xp.sin(t3) * xp.cos(t3) == x - b)\n",
"p.addConstraint(xp.sin(t3) * t3 == y + a)\n",
"p.addConstraint(xp.sin(t4) * xp.cos(t4) == x + a - b)\n",
"p.addConstraint(xp.sin(t4) * t4 == y + a + b)\n",
"\n",
"# the objective is to maximize the length of one (or each) side of the square\n",
"p.setObjective(a**2 + b**2,sense=xp.maximize)\n",
"\n",
"# choose between solving with a local or global solver\n",
"p.controls.nlpsolver = 1 # 1: local, 2: global, -1: solver decides based on license and user functions / multistart jobs (default)\n",
"# choose between solving with SLP or Knitro\n",
"p.controls.localsolver = 0 # 0: SLP, 1: Knitro, 2: use Optimizer (for convex QPs only), -1: automatic selection based on model characteristics and solver availability (default)\n",
"\n",
"p.optimize()\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The specific nonlinear solver can be chosen using the [NLPSOLVER](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/nonlinear/HTML/XSLP_NLPSOLVER.html) control:\n",
" - Setting a value of \"1\" will invoke a local solver, with it being either SLP or Knitro (**if a license is available. The community license does not include Knitro**). \n",
" - The control defaults to -1, which has Xpress choose the most appropriate solver. If there are user functions or multi-start jobs, or if there is no license available for Xpress Global, a local solver will be called. In all other cases, Xpress Global will be used to solve the problem.\n",
"\n",
"If a local solve is invoked, the [LOCALSOLVER](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/nonlinear/HTML/XSLP_SOLVER.html) control specify if either SLP or Knitro should be used by setting the control to \"1\" or \"2\" respectively. For convex QPs, setting the value to \"2\" will set Xpress Optimizer to solve the problem. By default (-1), an automatic selection is made based on model characteristics and solver availability.\n",
"\n",
"By running the previous code cell below with the NLPSOLVER control equal to 1, SLP or Knitro will be called and the problem is solved to local optimality. This can be confirmed by running the code cell again with NLPSOLVER equal to 2, which finds a larger (maximal) square.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Visualize solution\n",
"Point = namedtuple('Point', 'x y')\n",
"\n",
"def get_coords(t):\n",
"\n",
" x = np.sin(t) * np.cos(t)\n",
" y = np.sin(t) * t\n",
" return Point(x, y)\n",
"\n",
"# below code approximates the graph of the function\n",
"t = np.arange(-math.pi, math.pi, 0.01)\n",
"xs = np.sin(t) * np.cos(t)\n",
"ys = np.sin(t) * t\n",
"\n",
"# compute the x- and y-coordinates of the four vertices of the square\n",
"v1 = get_coords(p.getSolution(t1))\n",
"v2 = get_coords(p.getSolution(t2))\n",
"v3 = get_coords(p.getSolution(t3))\n",
"v4 = get_coords(p.getSolution(t4))\n",
"\n",
"# plot the graph and the square\n",
"fig, ax = plt.subplots()\n",
"cells = ax.plot(xs, ys)\n",
"plt.plot([v1.x, v2.x], [v1.y, v2.y], 'ro-')\n",
"plt.plot([v2.x, v4.x], [v2.y, v4.y], 'ro-')\n",
"plt.plot([v4.x, v3.x], [v4.y, v3.y], 'ro-')\n",
"plt.plot([v3.x, v1.x], [v3.y, v1.y], 'ro-')\n",
"\n",
"ax.set_aspect('equal', adjustable='box')\n",
"\n",
"plt.show()\n",
"\n",
"#print the variable values\n",
"print('solution: t1:', p.getSolution(t1), ', t2:', p.getSolution(t2), ', t3:', p.getSolution(t3), ', t4:', p.getSolution(t4), ', x:', p.getSolution(x), ', y:', p.getSolution(y), ', a:', p.getSolution(a), ', b:', p.getSolution(b))"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"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.12.9"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
| |||||||||||
| © Copyright 2025 Fair Isaac Corporation. |
