Prepared by: Yohannes Mariam (ymariam@nd.edu, ymariam1, 2024) and Oliver Harris (oharris2@nd.edu, @OliverHarris47, 2024)
# This code cell installs packages on Colab
import sys
if "google.colab" in sys.modules:
!wget "https://raw.githubusercontent.com/ndcbe/optimization/main/notebooks/helper.py"
import helper
helper.easy_install()
else:
sys.path.insert(0, "../")
import helper
helper.set_plotting_style()import pandas as pd
import pyomo.environ as pyo
import random
# Seed the random number generator so this notebook is reproducible
# (Pyomo style guide, section 8).
random.seed(0)Learning Objectives¶
Review syntax and components in Pyomo
Become acquainted with global solvers in Pyomo
Learn to use the GAMS file writer and access the NEOS server
Gain an introduction into Deterministic Global Optimization Algorithms
Uncover nuance in nonlinear, nonconvex programming problems
Introduction¶
Global optimization (GO) focuses on finding the global minimum or maximum of an objective function over a feasible domain, often characterized by numerous local optima. Unlike local optimization, GO addresses challenges in problems where local minima do not also guarantee global optimality. Recent advancements in algorithms, complexity analysis, and computational tools have driven significant growth in the field. Applications span diverse areas, including molecular conformation, distance geometry, packing, and trajectory planning.
Complexity analysis is critical in GO, as it evaluates the inherent difficulty of optimization problems. This assessment helps determine whether exact solutions are feasible or if approximate methods must be employed. Heuristics, such as metaheuristic frameworks and function modeling, are commonly used to navigate the search space efficiently, especially when function evaluations are computationally expensive. Branch-and-bound techniques provide systematic frameworks for exact solutions by iteratively dividing the problem space and calculating bounds to eliminate suboptimal regions. Lower bound computation, often via convex relaxations, is integral to both exact (deterministic) and heuristic methods, offering guarantees on the quality of solutions and improving algorithmic
This notebook will focus on deterministic approaches to GO problems, particularly the ‘Spatial Branch and Bound’ algorithm and the BARON and Couenne solvers which take this approach. This method is valid under certain qualifying assumptions that are revealed in the complexity analysis of a GO problem. Additional reading for complexity analysis, heuristics, lower bound computation, and branch and bound methods can be found at:
https://
Global Optimization¶
Given a function how do we ensure that the optimum we find is a global optimum?
Do we have a method to solve optimization problems with nonlinear objects or constraints with poor initialization?
Review
Let be defined as the feasible region
A point is a global minimizer if for all
Theorem 4.3 If is convex and is convex, then every local minimum in is a global minimum. If is strictly convex in , then a local minimum is the unique global minimum.
(Biegler, 2010, Chapter 4)
Spatial Branch and Bound Algorithm¶
Main Idea: Spatial branch-and-bound is a divide-and-conquer technique for global optimization. It systematically partitions a problem’s feasible space into sub-spaces, computes bounds for solutions, and prunes infeasible regions.
Algorithm:
Figure source: https://
Proof of convergence:
A branch-and-bound method that uses exact selection rules will eventually converge, because at each iteration it discards regions of the solution space that cannot contain a better solution than the current best one. The remaining “qualified” subregions always include the global optimum, ensuring that—given infinite time—the method will find it.
It is noted that the spatial branch and bound algorithm does not guarantee convergence in a finite number of steps
Figure source: https://
Example:
Figure source: https://
Circle Packing Example Revisited¶
What is the smallest rectangle you can use to enclose three given circles? Reference: Example 4.4 in Biegler (2010).
Propose an Optimization Model¶
The following optimization model is given in Biegler (2010):
Implement in Pyomo¶
First, we will define functions to create and intialize the model.
import random
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
def create_circle_model(circle_radii):
"""Create circle optimization model in Pyomo
Arguments:
circle_radii: dictionary with keys=circle name and value=radius (float)
Returns:
model: Pyomo model
"""
# Number of circles to consider
n = len(circle_radii)
# Create a concrete Pyomo model.
model = pyo.ConcreteModel()
# Initialize index for circles
model.CIRCLES = pyo.Set(initialize=circle_radii.keys())
# Create parameter
model.R = pyo.Param(
model.CIRCLES, domain=pyo.PositiveReals, initialize=circle_radii
)
# Create variables for box
model.a = pyo.Var(domain=pyo.PositiveReals)
model.b = pyo.Var(domain=pyo.PositiveReals)
# Set objective
model.obj = pyo.Objective(expr=2 * (model.a + model.b), sense=pyo.minimize)
# Create variables for circle centers
model.x = pyo.Var(model.CIRCLES, domain=pyo.PositiveReals)
model.y = pyo.Var(model.CIRCLES, domain=pyo.PositiveReals)
# "In the box" constraints
def left_x(m, c):
return m.x[c] >= model.R[c]
model.left_x_con = pyo.Constraint(model.CIRCLES, rule=left_x)
def left_y(m, c):
return m.y[c] >= model.R[c]
model.left_y_con = pyo.Constraint(model.CIRCLES, rule=left_y)
def right_x(m, c):
return m.x[c] <= m.b - model.R[c]
model.right_x_con = pyo.Constraint(model.CIRCLES, rule=right_x)
def right_y(m, c):
return m.y[c] <= m.a - model.R[c]
model.right_y_con = pyo.Constraint(model.CIRCLES, rule=right_y)
# No overlap constraints
def no_overlap(m, c1, c2):
if c1 < c2:
return (m.x[c1] - m.x[c2]) ** 2 + (m.y[c1] - m.y[c2]) ** 2 >= (
model.R[c1] + model.R[c2]
) ** 2
else:
return pyo.Constraint.Skip
model.no_overlap_con = pyo.Constraint(model.CIRCLES, model.CIRCLES, rule=no_overlap)
return model
def initialize_circle_model(model, a_init=25, b_init=25):
"""Initialize the x and y coordinates using uniform distribution
Arguments:
a_init: initial value for a (default=25)
b_init: initial value for b (default=25)
Returns:
Nothing. But per Pyomo scoping rules, the input argument `model`
can be modified in this function.
"""
# Initialize
model.a = a_init
model.b = b_init
for i in model.CIRCLES:
# Adding circle radii ensures the circle remains in the >0, >0 quadrant
model.x[i] = random.uniform(0, 10) + model.R[i]
model.y[i] = random.uniform(0, 10) + model.R[i]Next, we will create a dictionary containing the circle names and radii values.
# Create dictionary with circle data
circle_data = {"A": 10.0, "B": 5.0, "C": 3.0}
circle_data{'A': 10.0, 'B': 5.0, 'C': 3.0}# Access the keys
circle_data.keys()dict_keys(['A', 'B', 'C'])Now let’s create the model.
# Create model
model = create_circle_model(circle_data)
model.pprint()1 Set Declarations
CIRCLES : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 3 : {'A', 'B', 'C'}
1 Param Declarations
R : Size=3, Index=CIRCLES, Domain=PositiveReals, Default=None, Mutable=False
Key : Value
A : 10.0
B : 5.0
C : 3.0
4 Var Declarations
a : Size=1, Index=None
Key : Lower : Value : Upper : Fixed : Stale : Domain
None : 0 : None : None : False : True : PositiveReals
b : Size=1, Index=None
Key : Lower : Value : Upper : Fixed : Stale : Domain
None : 0 : None : None : False : True : PositiveReals
x : Size=3, Index=CIRCLES
Key : Lower : Value : Upper : Fixed : Stale : Domain
A : 0 : None : None : False : True : PositiveReals
B : 0 : None : None : False : True : PositiveReals
C : 0 : None : None : False : True : PositiveReals
y : Size=3, Index=CIRCLES
Key : Lower : Value : Upper : Fixed : Stale : Domain
A : 0 : None : None : False : True : PositiveReals
B : 0 : None : None : False : True : PositiveReals
C : 0 : None : None : False : True : PositiveReals
1 Objective Declarations
obj : Size=1, Index=None, Active=True
Key : Active : Sense : Expression
None : True : minimize : 2*(a + b)
5 Constraint Declarations
left_x_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : 10.0 : x[A] : +Inf : True
B : 5.0 : x[B] : +Inf : True
C : 3.0 : x[C] : +Inf : True
left_y_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : 10.0 : y[A] : +Inf : True
B : 5.0 : y[B] : +Inf : True
C : 3.0 : y[C] : +Inf : True
no_overlap_con : Size=3, Index=CIRCLES*CIRCLES, Active=True
Key : Lower : Body : Upper : Active
('A', 'B') : 225.0 : (x[A] - x[B])**2 + (y[A] - y[B])**2 : +Inf : True
('A', 'C') : 169.0 : (x[A] - x[C])**2 + (y[A] - y[C])**2 : +Inf : True
('B', 'C') : 64.0 : (x[B] - x[C])**2 + (y[B] - y[C])**2 : +Inf : True
right_x_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : -Inf : x[A] - (b - 10.0) : 0.0 : True
B : -Inf : x[B] - (b - 5.0) : 0.0 : True
C : -Inf : x[C] - (b - 3.0) : 0.0 : True
right_y_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : -Inf : y[A] - (a - 10.0) : 0.0 : True
B : -Inf : y[B] - (a - 5.0) : 0.0 : True
C : -Inf : y[C] - (a - 3.0) : 0.0 : True
12 Declarations: CIRCLES R a b obj x y left_x_con left_y_con right_x_con right_y_con no_overlap_con
And let’s initialize the model.
# Initialize model
initialize_circle_model(model)
model.pprint()1 Set Declarations
CIRCLES : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 3 : {'A', 'B', 'C'}
1 Param Declarations
R : Size=3, Index=CIRCLES, Domain=PositiveReals, Default=None, Mutable=False
Key : Value
A : 10.0
B : 5.0
C : 3.0
4 Var Declarations
a : Size=1, Index=None
Key : Lower : Value : Upper : Fixed : Stale : Domain
None : 0 : 25 : None : False : False : PositiveReals
b : Size=1, Index=None
Key : Lower : Value : Upper : Fixed : Stale : Domain
None : 0 : 25 : None : False : False : PositiveReals
x : Size=3, Index=CIRCLES
Key : Lower : Value : Upper : Fixed : Stale : Domain
A : 0 : 18.444218515250483 : None : False : False : PositiveReals
B : 0 : 9.205715808308451 : None : False : False : PositiveReals
C : 0 : 8.112747213686085 : None : False : False : PositiveReals
y : Size=3, Index=CIRCLES
Key : Lower : Value : Upper : Fixed : Stale : Domain
A : 0 : 17.579544029403024 : None : False : False : PositiveReals
B : 0 : 7.589167502929634 : None : False : False : PositiveReals
C : 0 : 7.049341374504143 : None : False : False : PositiveReals
1 Objective Declarations
obj : Size=1, Index=None, Active=True
Key : Active : Sense : Expression
None : True : minimize : 2*(a + b)
5 Constraint Declarations
left_x_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : 10.0 : x[A] : +Inf : True
B : 5.0 : x[B] : +Inf : True
C : 3.0 : x[C] : +Inf : True
left_y_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : 10.0 : y[A] : +Inf : True
B : 5.0 : y[B] : +Inf : True
C : 3.0 : y[C] : +Inf : True
no_overlap_con : Size=3, Index=CIRCLES*CIRCLES, Active=True
Key : Lower : Body : Upper : Active
('A', 'B') : 225.0 : (x[A] - x[B])**2 + (y[A] - y[B])**2 : +Inf : True
('A', 'C') : 169.0 : (x[A] - x[C])**2 + (y[A] - y[C])**2 : +Inf : True
('B', 'C') : 64.0 : (x[B] - x[C])**2 + (y[B] - y[C])**2 : +Inf : True
right_x_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : -Inf : x[A] - (b - 10.0) : 0.0 : True
B : -Inf : x[B] - (b - 5.0) : 0.0 : True
C : -Inf : x[C] - (b - 3.0) : 0.0 : True
right_y_con : Size=3, Index=CIRCLES, Active=True
Key : Lower : Body : Upper : Active
A : -Inf : y[A] - (a - 10.0) : 0.0 : True
B : -Inf : y[B] - (a - 5.0) : 0.0 : True
C : -Inf : y[C] - (a - 3.0) : 0.0 : True
12 Declarations: CIRCLES R a b obj x y left_x_con left_y_con right_x_con right_y_con no_overlap_con
Activity
Compare the initial values forx and y with and without initialization. What is the default initial value in Pyomo?Visualize Initial Point¶
Next, we’ll define a function to plot the solution (or initial point)
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
def plot_circles(m):
"""Plot circles using data in Pyomo model with updated style
Arguments:
m: Pyomo concrete model
Returns:
Nothing (but makes a figure)
"""
# Create figure with specified size and DPI
fig, ax = plt.subplots(figsize=(4, 6.4), dpi=300)
# Define padding
padding = 2 # Minimum padding of 2 units
# Adjust axes based on box dimensions with padding
ax.set_xlim(0 - padding, m.b.value + padding)
ax.set_ylim(0 - padding, m.a.value + padding)
ax.set_aspect("equal", adjustable="box")
# Draw box
box = mpatches.Rectangle(
(0, 0),
width=m.b.value,
height=m.a.value,
fill=False,
edgecolor="#0072B2", # Okabe-Ito blue
linewidth=1,
)
ax.add_patch(box)
# Draw circles (with shading, no outline) and mark centers
for i in m.CIRCLES:
circle = mpatches.Circle(
(m.x[i].value, m.y[i].value),
radius=m.R[i],
facecolor="#E69F00", # Okabe-Ito orange
alpha=0.5,
linewidth=0,
) # No outline
ax.add_patch(circle)
ax.scatter(
m.x[i].value,
m.y[i].value,
color="#D55E00", # Okabe-Ito vermillion
marker="x",
s=4**2,
) # An x, not a dot: the centres must read without colour
# Update axis ticks and labels
ax.tick_params(
axis="both", which="major", labelsize=15, direction="in", length=6, width=2
)
ax.tick_params(
axis="both", which="minor", labelsize=15, direction="in", length=3, width=1.5
)
# Add grid with adjusted transparency
# ax.grid(True, linestyle='--', alpha=0.5)
# Update title
ax.set_title("Circle Arrangement", fontsize=16, fontweight="bold")
# Update axis labels
ax.set_xlabel("B", fontsize=16, fontweight="bold") # Label for x-axis
ax.set_ylabel("A", fontsize=16, fontweight="bold") # Label for y-axis
# Show plot
plt.show()Solve and Inspect the Solution¶
# Specify the solver
solver = pyo.SolverFactory("ipopt")
# Solve the model
results = solver.solve(model, tee=True)
assert pyo.check_optimal_termination(results), (
f"Solve failed: status={results.solver.status}, "
f"termination={results.solver.termination_condition}"
)Ipopt 3.14.19:
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit https://github.com/coin-or/Ipopt
******************************************************************************
This is Ipopt version 3.14.19, running with linear solver MUMPS 5.8.2.
Number of nonzeros in equality constraint Jacobian...: 0
Number of nonzeros in inequality constraint Jacobian.: 30
Number of nonzeros in Lagrangian Hessian.............: 12
Total number of variables............................: 8
variables with only lower bounds: 8
variables with lower and upper bounds: 0
variables with only upper bounds: 0
Total number of equality constraints.................: 0
Total number of inequality constraints...............: 15
inequality constraints with only lower bounds: 9
inequality constraints with lower and upper bounds: 0
inequality constraints with only upper bounds: 6
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
0 1.0000000e+02 6.25e+01 1.05e+00 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0
1 1.0046267e+02 4.59e+01 1.05e+01 -1.0 2.67e+01 0.0 1.52e-01 5.64e-02h 1
2 1.0446269e+02 2.46e+01 2.54e+00 -1.0 5.43e+00 -0.5 5.62e-01 3.57e-01h 1
3 1.1075999e+02 0.00e+00 4.40e+00 -1.0 4.83e+00 -1.0 6.87e-01 1.00e+00h 1
4 1.0931790e+02 0.00e+00 4.22e+00 -1.0 6.13e+01 -1.4 3.27e-01 2.76e-02f 3
5 1.0505265e+02 0.00e+00 8.83e-01 -1.0 2.84e+00 -1.0 1.00e+00 9.20e-01f 1
6 1.0163361e+02 0.00e+00 1.15e+00 -1.0 1.96e+00 -1.5 4.90e-01 9.10e-01h 1
7 9.9775211e+01 0.00e+00 1.90e-01 -1.0 2.12e+00 -1.1 1.00e+00 8.60e-01f 1
8 9.8947266e+01 0.00e+00 8.86e-01 -1.0 1.23e+02 - 3.86e-01 5.70e-02f 1
9 9.8937271e+01 0.00e+00 2.06e-02 -1.0 7.04e-01 -1.5 1.00e+00 1.00e+00h 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
10 9.8325956e+01 0.00e+00 6.43e-03 -2.5 3.75e+00 - 9.93e-01 9.37e-01f 1
11 9.8301250e+01 0.00e+00 2.66e-03 -2.5 4.81e+01 - 4.81e-01 1.00e+00h 1
12 9.8301257e+01 0.00e+00 5.36e-04 -2.5 2.99e+01 - 1.00e+00 1.00e+00h 1
13 9.8301256e+01 0.00e+00 2.96e-05 -2.5 2.59e+01 - 1.00e+00 1.00e+00h 1
14 9.8301256e+01 0.00e+00 1.40e-06 -2.5 2.48e+00 - 1.00e+00 1.00e+00h 1
15 9.8285159e+01 0.00e+00 2.69e-07 -3.8 3.80e-02 - 1.00e+00 1.00e+00h 1
16 9.8284281e+01 0.00e+00 9.89e-10 -5.7 2.05e-03 - 1.00e+00 1.00e+00h 1
17 9.8284270e+01 0.00e+00 9.89e-13 -8.6 1.62e-04 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 17
(scaled) (unscaled)
Objective...............: 9.8284270438747257e+01 9.8284270438747257e+01
Dual infeasibility......: 9.8878042171958667e-13 9.8878042171958667e-13
Constraint violation....: 0.0000000000000000e+00 0.0000000000000000e+00
Variable bound violation: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 2.5165074041745097e-09 2.5165074041745097e-09
Overall NLP error.......: 2.5165074041745097e-09 2.5165074041745097e-09
Number of objective function evaluations = 22
Number of objective gradient evaluations = 18
Number of equality constraint evaluations = 0
Number of inequality constraint evaluations = 22
Number of equality constraint Jacobian evaluations = 0
Number of inequality constraint Jacobian evaluations = 18
Number of Lagrangian Hessian evaluations = 17
Total seconds in IPOPT = 0.407
EXIT: Optimal Solution Found.
Next, we can inspect the solution. Because Pyomo is a Python extension, we can use Python (for loops, etc.) to programmatically inspect the solution.
# Print variable values
print("Name\tValue")
for c in model.component_data_objects(pyo.Var):
print(c.name, "\t", pyo.value(c))
# Plot solution
plot_circles(model)Name Value
a 19.999999803189603
b 29.14213541618403
x[A] 19.14213551493119
x[B] 4.999999951252128
x[C] 5.517274811159313
y[A] 9.999999901937443
y[B] 4.999999953543125
y[C] 15.729315741741795
# Print constraints
for c in model.component_data_objects(pyo.Constraint):
print(
c.name,
"\t",
pyo.value(c.lower),
"\t",
pyo.value(c.body),
"\t",
pyo.value(c.upper),
)left_x_con[A] 10.0 19.14213551493119 None
left_x_con[B] 5.0 4.999999951252128 None
left_x_con[C] 3.0 5.517274811159313 None
left_y_con[A] 10.0 9.999999901937443 None
left_y_con[B] 5.0 4.999999953543125 None
left_y_con[C] 3.0 15.729315741741795 None
right_x_con[A] None 9.87471615587765e-08 0.0
right_x_con[B] None -19.1421354649319 0.0
right_x_con[C] None -20.624860605024715 0.0
right_y_con[A] None 9.874784012708915e-08 0.0
right_y_con[B] None -9.999999849646478 0.0
right_y_con[C] None -1.2706840614478079 0.0
no_overlap_con[A,B] 225.0 224.99999778541928 None
no_overlap_con[A,C] 169.0 218.46188918942016 None
no_overlap_con[B,C] 64.0 115.38579056358121 None
Take Away Messages¶
Nonlinear programs may be nonconvex. For nonconvex problems, there often exist many local optima that are not also global optima.
We defined convexity and analyzed this property in Chapter 7.
Initialization is really important in optimization problems with nonlinear objectives or constraints!
There are specialized solvers for linear programs, quadratic programs, and convex programs. In this class, we focused on more general algorithms for (non)convex nonlinear programs including the algorithms used by the
ipoptsolver.
Deterministic global optimization solvers¶
Couenne Solver¶
# Create model
model = create_circle_model(circle_data)
# model.pprint()# Initialize model
initialize_circle_model(model)
# model.pprint()# Specify the solver
solver = pyo.SolverFactory("couenne")
# Solve the model
results = solver.solve(model, tee=True)
assert pyo.check_optimal_termination(results), (
f"Solve failed: status={results.solver.status}, "
f"termination={results.solver.termination_condition}"
)Couenne 0.5.8 -- an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: couenne@list.coin-or.org
Instructions: http://www.coin-or.org/Couenne
couenne:
ANALYSIS TEST: NLP0012I
Num Status Obj It time Location
NLP0014I 1 OPT 98.28427 16 0.001838
Couenne: new cutoff value 9.8284270824e+01 (0.025699 seconds)
Loaded instance "/var/folders/3w/vr4xmyqs451dg23xk88pqcg00000gq/T/tmp8zjvshh9.pyomo.nl"
Constraints: 15
Variables: 8 (0 integer)
Auxiliaries: 16 (0 integer)
Coin0506I Presolve 40 (0) rows, 21 (-3) columns and 87 (-3) elements
Clp0006I 0 Obj 80 Primal inf 980.53922 (21)
Clp0006I 17 Obj 80
Clp0000I Optimal - objective value 80
Clp0032I Optimal objective 80 - 17 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value 80
Cbc0012I Integer solution of 98.284271 found by Couenne Rounding NLP after 0 iterations and 0 nodes (0.00 seconds)
NLP Heuristic: NLP0014I 2 OPT 98.28427 11 0.001074
no solution.
Clp0000I Optimal - objective value 80
Optimality Based BT: 0 improved bounds
Probing: 2 improved bounds
NLP Heuristic: no solution.
Cbc0031I 4 added rows had average density of 2
Cbc0013I At root node, 4 cuts changed objective from 80 to 89.142135 in 10 passes
Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 20 row cuts average 2.0 elements, 1 column cuts (1 active)
Cbc0010I After 0 nodes, 1 on tree, 98.284271 best solution, best possible 89.142135 (0.01 seconds)
Optimality Based BT: 0 improved bounds
Optimality Based BT: 0 improved bounds
Optimality Based BT: 0 improved bounds
Optimality Based BT: 1 improved bounds
Optimality Based BT: 1 improved bounds
Optimality Based BT: 0 improved bounds
Optimality Based BT: 2 improved bounds
Optimality Based BT: 1 improved bounds
Cbc0001I Search completed - best objective 98.28427082376189, took 104 iterations and 10 nodes (0.04 seconds)
Cbc0035I Maximum depth 3, 0 variables fixed on reduced cost
"Finished"
Linearization cuts added at root node: 40
Linearization cuts added in total: 40 (separation time: 4.7e-05s)
Total solve time: 0.040569s (0.040569s in branch-and-bound)
Lower bound: 98.2843
Upper bound: 98.2843 (gap: 0.00%)
Branch-and-bound nodes: 10
Performance of FBBT: 0.000195s, 29 runs. fix: 0 shrnk: 0.941872 ubd: 1.12987 2ubd: 0.233766 infeas: 0
Performance of OBBT: 0.009983s, 9 runs. fix: 0 shrnk: 0.197819 ubd: 0 2ubd: 0 infeas: 0
# Print variable values
print("Name\tValue")
for c in model.component_data_objects(pyo.Var):
print(c.name, "\t", pyo.value(c))
# Plot solution
plot_circles(model)Name Value
a 20.0
b 29.14213541188094
x[A] 19.142135511875942
x[B] 5.0
x[C] 6.437244649845617
y[A] 10.0
y[B] 14.99999985001312
y[C] 6.840357665094204
# Print constraints
for c in model.component_data_objects(pyo.Constraint):
print(
c.name,
"\t",
pyo.value(c.lower),
"\t",
pyo.value(c.body),
"\t",
pyo.value(c.upper),
)left_x_con[A] 10.0 19.142135511875942 None
left_x_con[B] 5.0 5.0 None
left_x_con[C] 3.0 6.437244649845617 None
left_y_con[A] 10.0 10.0 None
left_y_con[B] 5.0 14.99999985001312 None
left_y_con[C] 3.0 6.840357665094204 None
right_x_con[A] None 9.999500250046367e-08 0.0
right_x_con[B] None -19.14213541188094 0.0
right_x_con[C] None -19.704890762035323 0.0
right_y_con[A] None 0.0 0.0
right_y_con[B] None -1.4998687980494196e-07 0.0
right_y_con[C] None -10.159642334905797 0.0
no_overlap_con[A,B] 225.0 224.99999533639385 None
no_overlap_con[A,C] 169.0 171.3975915006306 None
no_overlap_con[B,C] 64.0 68.64543276941818 None
BARON Solver (via NEOS Server)¶
BARON is a global optimization solver that uses a spatial branch-and-bound algorithm to solve Mixed-Integer Nonlinear Programs. Pyomo does ship a BARON interface (pyo.SolverFactory("baron")), but BARON is commercial software and is not part of the course environment, so we do not have a local baron executable for it to drive. Instead you can use the GAMS file writer and upload the .gms model to the NEOS BARON server, which hosts a licensed copy.
Step 1: Reinitialize your model
Step 2: Import the ProblemWriter_gams class, which is a Pyomo plugin for writing optimization models to a file in GAMS (General Algebraic Modeling System) format. More information here: https://
Step 3: Write and export the model to a .gms file name of your choice.
Step 4: Open https://
Step 5: Upload the ‘solve.log’ file to the session storage and use the script below to read the file and print the results.
# Be sure to Re-initialize before writing writting GAMS file
initialize_circle_model(model)# Import the GAMS writer from Pyomo's representation plugins
from pyomo.repn.plugins.gams_writer import ProblemWriter_gams
# Write the Pyomo model to a file in GAMS format
# - 'circles_1.gms' is the output file name
# - io_options specifies that symbolic names (instead of numerical labels) should be used
model.write("circles_1.gms", io_options={"symbolic_solver_labels": True})('circles_1.gms', 5151436352)# Specify the file path
# file_path = "/content/solve.log" # Adjust this path if the file location differs
# Open and read the file
# with open(file_path, 'r') as file:
# content = file.read()
# Print the file content
# print(content)Reinitialize¶
def initialize_circle_model(model, a_init=25, b_init=50):
"""Initialize the x and y coordinates with specific positions
Arguments:
a_init: initial value for a (default=25)
b_init: initial value for b (default=50)
Returns:
Nothing. Updates the model in-place.
"""
# Set box dimensions
model.a = a_init
model.b = b_init
# Place circles as described
circle_positions = {
"A": (10, 13), # Largest circle on the left
"B": (25, 13), # Middle circle in the center
"C": (33, 13), # Smallest circle on the right
}
for i in model.CIRCLES:
model.x[i] = circle_positions[i][0]
model.y[i] = circle_positions[i][1]# Create model
model = create_circle_model(circle_data)
# model.pprint()# Initialize model
initialize_circle_model(model)
# model.pprint()# Print variable values
print("Name\tValue")
for c in model.component_data_objects(pyo.Var):
print(c.name, "\t", pyo.value(c))
# Plot solution
plot_circles(model)Name Value
a 25
b 50
x[A] 10
x[B] 25
x[C] 33
y[A] 13
y[B] 13
y[C] 13
Solve with IPOPT¶
solver = pyo.SolverFactory("ipopt")
# Solve the model
results = solver.solve(model, tee=True)
assert pyo.check_optimal_termination(results), (
f"Solve failed: status={results.solver.status}, "
f"termination={results.solver.termination_condition}"
)Ipopt 3.14.19:
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit https://github.com/coin-or/Ipopt
******************************************************************************
This is Ipopt version 3.14.19, running with linear solver MUMPS 5.8.2.
Number of nonzeros in equality constraint Jacobian...: 0
Number of nonzeros in inequality constraint Jacobian.: 30
Number of nonzeros in Lagrangian Hessian.............: 12
Total number of variables............................: 8
variables with only lower bounds: 8
variables with lower and upper bounds: 0
variables with only upper bounds: 0
Total number of equality constraints.................: 0
Total number of inequality constraints...............: 15
inequality constraints with only lower bounds: 9
inequality constraints with lower and upper bounds: 0
inequality constraints with only upper bounds: 6
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
0 1.5000000e+02 0.00e+00 1.29e+00 -1.0 0.00e+00 - 0.00e+00 0.00e+00 0
1 1.5000039e+02 3.22e-01 6.27e+01 -1.0 1.30e+00 2.0 9.89e-01 4.86e-01h 1
2 1.5000046e+02 3.24e-01 1.11e+02 -1.0 6.11e-01 2.4 1.00e+00 1.32e-02h 1
3 1.5000998e+02 0.00e+00 8.72e+02 -1.0 1.23e+00 2.9 1.00e+00 1.00e+00h 1
4 1.5001088e+02 0.00e+00 2.63e+01 -1.0 7.14e-04 4.2 9.85e-01 1.00e+00f 1
5 1.5001143e+02 0.00e+00 3.69e+01 -1.0 7.29e-03 3.7 1.00e+00 1.00e+00f 1
6 1.5001269e+02 0.00e+00 2.97e+00 -1.0 1.76e-03 3.2 1.00e+00 1.00e+00f 1
7 1.5001228e+02 0.00e+00 4.35e+00 -1.0 7.73e-03 2.7 1.00e+00 1.00e+00f 1
8 1.5000705e+02 0.00e+00 1.25e+00 -1.0 6.65e-03 2.3 1.00e+00 1.00e+00f 1
9 1.4998080e+02 0.00e+00 1.09e+00 -1.0 1.75e-02 1.8 1.00e+00 1.00e+00f 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
10 1.4988739e+02 0.00e+00 6.40e-01 -1.0 3.07e-02 1.3 1.00e+00 1.00e+00f 1
11 1.4954477e+02 0.00e+00 6.61e-01 -1.7 9.53e-02 0.8 1.00e+00 1.00e+00f 1
12 1.4852695e+02 0.00e+00 6.61e-01 -1.7 2.86e-01 0.4 1.00e+00 1.00e+00f 1
13 1.4551829e+02 0.00e+00 6.60e-01 -1.7 8.56e-01 -0.1 1.00e+00 1.00e+00f 1
14 1.3934296e+02 0.00e+00 6.56e-01 -1.7 2.54e+00 -0.6 1.00e+00 6.88e-01f 1
15 1.3668831e+02 0.00e+00 5.30e-01 -1.7 7.74e-01 -0.2 1.00e+00 1.00e+00f 1
16 1.3161005e+02 0.00e+00 5.03e-01 -1.7 2.21e+00 -0.6 6.60e-01 5.90e-01f 1
17 1.3002225e+02 0.00e+00 1.29e+00 -1.7 6.57e+00 -1.1 1.00e+00 1.15e-01f 1
18 1.1225586e+02 0.00e+00 7.53e-01 -1.7 1.96e+01 -1.6 1.00e+00 4.52e-01f 1
19 1.1203039e+02 0.00e+00 9.81e-01 -1.7 4.24e+01 -2.1 2.06e-01 7.45e-03f 1
iter objective inf_pr inf_du lg(mu) ||d|| lg(rg) alpha_du alpha_pr ls
20 1.1152482e+02 0.00e+00 2.06e-01 -1.7 2.58e+00 -1.6 1.00e+00 1.00e+00f 1
21 1.1027843e+02 0.00e+00 1.54e-01 -1.7 2.17e+00 -1.2 1.00e+00 1.00e+00h 1
22 1.1012781e+02 0.00e+00 8.89e-01 -1.7 1.59e+01 -1.7 1.00e+00 3.93e-02h 1
23 1.0991634e+02 0.00e+00 1.31e-03 -1.7 3.43e-01 - 1.00e+00 1.00e+00h 1
24 1.0978925e+02 0.00e+00 1.73e-03 -3.8 6.98e-01 - 1.00e+00 9.10e-01h 1
25 1.0977740e+02 0.00e+00 1.01e-06 -3.8 3.48e-02 - 1.00e+00 1.00e+00h 1
26 1.0977622e+02 0.00e+00 8.12e-09 -5.7 8.90e-03 - 1.00e+00 1.00e+00h 1
27 1.0977620e+02 0.00e+00 1.14e-12 -8.6 1.07e-04 - 1.00e+00 1.00e+00h 1
Number of Iterations....: 27
(scaled) (unscaled)
Objective...............: 1.0977620379629022e+02 1.0977620379629022e+02
Dual infeasibility......: 1.1404551404018306e-12 1.1404551404018306e-12
Constraint violation....: 0.0000000000000000e+00 0.0000000000000000e+00
Variable bound violation: 0.0000000000000000e+00 0.0000000000000000e+00
Complementarity.........: 2.5111950448758505e-09 2.5111950448758505e-09
Overall NLP error.......: 2.5111950448758505e-09 2.5111950448758505e-09
Number of objective function evaluations = 28
Number of objective gradient evaluations = 28
Number of equality constraint evaluations = 0
Number of inequality constraint evaluations = 28
Number of equality constraint Jacobian evaluations = 0
Number of inequality constraint Jacobian evaluations = 28
Number of Lagrangian Hessian evaluations = 27
Total seconds in IPOPT = 0.790
EXIT: Optimal Solution Found.
# Print variable values
print("Name\tValue")
for c in model.component_data_objects(pyo.Var):
print(c.name, "\t", pyo.value(c))
# Plot solution
print("Perimeter: ", 2 * pyo.value(model.a) + 2 * pyo.value(model.b))
plot_circles(model)Name Value
a 19.99999980319163
b 34.88810209495348
x[A] 9.999999901252709
x[B] 24.14213546828912
x[C] 31.888102123700754
y[A] 9.999999901252576
y[B] 14.99999984015795
y[C] 16.999999828328722
Perimeter: 109.77620379629022
Solve with Couenne¶
# Specify the solver
solver = pyo.SolverFactory("couenne")
# Solve the model
results = solver.solve(model, tee=True)
assert pyo.check_optimal_termination(results), (
f"Solve failed: status={results.solver.status}, "
f"termination={results.solver.termination_condition}"
)
model.display()Couenne 0.5.8 -- an Open-Source solver for Mixed Integer Nonlinear Optimization
Mailing list: couenne@list.coin-or.org
Instructions: http://www.coin-or.org/Couenne
couenne:
ANALYSIS TEST: NLP0012I
Num Status Obj It time Location
NLP0014I 1 OPT 98.28427 30 0.003027
Couenne: new cutoff value 9.8284270824e+01 (0.026304 seconds)
Loaded instance "/var/folders/3w/vr4xmyqs451dg23xk88pqcg00000gq/T/tmpeuo9cdgb.pyomo.nl"
Constraints: 15
Variables: 8 (0 integer)
Auxiliaries: 16 (0 integer)
Coin0506I Presolve 40 (0) rows, 21 (-3) columns and 87 (-3) elements
Clp0006I 0 Obj 80 Primal inf 980.53922 (21)
Clp0006I 17 Obj 80
Clp0000I Optimal - objective value 80
Clp0032I Optimal objective 80 - 17 iterations time 0.002, Presolve 0.00
Clp0000I Optimal - objective value 80
Cbc0012I Integer solution of 98.284271 found by Couenne Rounding NLP after 0 iterations and 0 nodes (0.00 seconds)
NLP Heuristic: NLP0014I 2 OPT 98.28427 16 0.00194
no solution.
Clp0000I Optimal - objective value 80
Optimality Based BT: 0 improved bounds
Probing: 2 improved bounds
NLP Heuristic: no solution.
Cbc0031I 4 added rows had average density of 2
Cbc0013I At root node, 4 cuts changed objective from 80 to 89.142135 in 10 passes
Cbc0014I Cut generator 0 (Couenne convexifier cuts) - 20 row cuts average 2.0 elements, 1 column cuts (1 active)
Cbc0010I After 0 nodes, 1 on tree, 98.284271 best solution, best possible 89.142135 (0.01 seconds)
Optimality Based BT: 0 improved bounds
Optimality Based BT: 0 improved bounds
Optimality Based BT: 0 improved bounds
Optimality Based BT: 1 improved bounds
Optimality Based BT: 1 improved bounds
Optimality Based BT: 0 improved bounds
Couenne: new cutoff value 9.8284170804e+01 (0.055828 seconds)
Optimality Based BT: 2 improved bounds
Cbc0001I Search completed - best objective 98.28427082376298, took 84 iterations and 8 nodes (0.03 seconds)
Cbc0035I Maximum depth 2, 0 variables fixed on reduced cost
"Finished"
Linearization cuts added at root node: 40
Linearization cuts added in total: 40 (separation time: 4.3e-05s)
Total solve time: 0.033262s (0.033262s in branch-and-bound)
Lower bound: 98.2842
Upper bound: 98.2842 (gap: 0.00%)
Branch-and-bound nodes: 8
Performance of FBBT: 0.000148s, 26 runs. fix: 0 shrnk: 0.000798964 ubd: 1.16 2ubd: 0.24 infeas: 0
Performance of OBBT: 0.008481s, 8 runs. fix: 0 shrnk: 0.150101 ubd: 0 2ubd: 0 infeas: 0
Model unknown
Variables:
a : Size=1, Index=None
Key : Lower : Value : Upper : Fixed : Stale : Domain
None : 0 : 20.0 : None : False : False : PositiveReals
b : Size=1, Index=None
Key : Lower : Value : Upper : Fixed : Stale : Domain
None : 0 : 29.142085401919054 : None : False : False : PositiveReals
x : Size=3, Index=CIRCLES
Key : Lower : Value : Upper : Fixed : Stale : Domain
A : 0 : 19.14208540191905 : None : False : False : PositiveReals
B : 0 : 5.0 : None : False : False : PositiveReals
C : 0 : 6.379299717016568 : None : False : False : PositiveReals
y : Size=3, Index=CIRCLES
Key : Lower : Value : Upper : Fixed : Stale : Domain
A : 0 : 10.0 : None : False : False : PositiveReals
B : 0 : 15.0 : None : False : False : PositiveReals
C : 0 : 7.065784152449445 : None : False : False : PositiveReals
Objectives:
obj : Size=1, Index=None, Active=True
Key : Active : Value
None : True : 98.28417080383811
Constraints:
left_x_con : Size=3
Key : Lower : Body : Upper
A : 10.0 : 19.14208540191905 : None
B : 5.0 : 5.0 : None
C : 3.0 : 6.379299717016568 : None
left_y_con : Size=3
Key : Lower : Body : Upper
A : 10.0 : 10.0 : None
B : 5.0 : 15.0 : None
C : 3.0 : 7.065784152449445 : None
right_x_con : Size=3
Key : Lower : Body : Upper
A : None : -3.552713678800501e-15 : 0.0
B : None : -19.142085401919054 : 0.0
C : None : -19.762785684902486 : 0.0
right_y_con : Size=3
Key : Lower : Body : Upper
A : None : 0.0 : 0.0
B : None : 0.0 : 0.0
C : None : -9.934215847550554 : 0.0
no_overlap_con : Size=3
Key : Lower : Body : Upper
('A', 'B') : 225.0 : 224.9985795151719 : None
('A', 'C') : 169.0 : 171.49832107876856 : None
('B', 'C') : 64.0 : 64.85424882488437 : None
# Print variable values
print("Name\tValue")
for c in model.component_data_objects(pyo.Var):
print(c.name, "\t", pyo.value(c))
# Plot solution
print("Perimeter: ", 2 * pyo.value(model.a) + 2 * pyo.value(model.b))
plot_circles(model)Name Value
a 20.0
b 29.142085401919054
x[A] 19.14208540191905
x[B] 5.0
x[C] 6.379299717016568
y[A] 10.0
y[B] 15.0
y[C] 7.065784152449445
Perimeter: 98.28417080383811
Solve with Baron¶
# Initialize Before Accessing GAMS Writer
initialize_circle_model(model)# Import the GAMS writer from Pyomo's representation plugins
from pyomo.repn.plugins.gams_writer import ProblemWriter_gams
# Write the Pyomo model to a file in GAMS format
# - 'circles_2.gms' is the output file name
# - io_options specifies that symbolic names (instead of numerical labels) should be used
model.write("circles_2.gms", io_options={"symbolic_solver_labels": True})('circles_2.gms', 5155515728)Here is the contents of circles_2.gms:
$offlisting
$offdigit
EQUATIONS
left_x_con_A__lo
left_x_con_B__lo
left_x_con_C__lo
left_y_con_A__lo
left_y_con_B__lo
left_y_con_C__lo
right_x_con_A__hi
right_x_con_B__hi
right_x_con_C__hi
right_y_con_A__hi
right_y_con_B__hi
right_y_con_C__hi
no_overlap_con_A_B__lo
no_overlap_con_A_C__lo
no_overlap_con_B_C__lo
obj;
POSITIVE VARIABLES
x_A_
x_B_
x_C_
y_A_
y_B_
y_C_
b
a;
VARIABLES
GAMS_OBJECTIVE
;
left_x_con_A__lo.. 10 =l= x_A_ ;
left_x_con_B__lo.. 5 =l= x_B_ ;
left_x_con_C__lo.. 3 =l= x_C_ ;
left_y_con_A__lo.. 10 =l= y_A_ ;
left_y_con_B__lo.. 5 =l= y_B_ ;
left_y_con_C__lo.. 3 =l= y_C_ ;
right_x_con_A__hi.. x_A_ - (b + (-10)) =l= 0 ;
right_x_con_B__hi.. x_B_ - (b + (-5)) =l= 0 ;
right_x_con_C__hi.. x_C_ - (b + (-3)) =l= 0 ;
right_y_con_A__hi.. y_A_ - (a + (-10)) =l= 0 ;
right_y_con_B__hi.. y_B_ - (a + (-5)) =l= 0 ;
right_y_con_C__hi.. y_C_ - (a + (-3)) =l= 0 ;
no_overlap_con_A_B__lo.. 225 =l= power((x_A_ - x_B_), 2) + power((y_A_ - y_B_), 2) ;
no_overlap_con_A_C__lo.. 169 =l= power((x_A_ - x_C_), 2) + power((y_A_ - y_C_), 2) ;
no_overlap_con_B_C__lo.. 64 =l= power((x_B_ - x_C_), 2) + power((y_B_ - y_C_), 2) ;
obj.. GAMS_OBJECTIVE =e= 2*(a + b) ;
x_A_.l = 10;
x_B_.l = 25;
x_C_.l = 33;
y_A_.l = 13;
y_B_.l = 13;
y_C_.l = 13;
b.l = 50;
a.l = 25;
MODEL GAMS_MODEL /all/ ;
option solprint=off;
option limrow=0;
option limcol=0;
option solvelink=5;
SOLVE GAMS_MODEL USING nlp minimizing GAMS_OBJECTIVE;
Scalars MODELSTAT 'model status', SOLVESTAT 'solve status';
MODELSTAT = GAMS_MODEL.modelstat;
SOLVESTAT = GAMS_MODEL.solvestat;
Scalar OBJEST 'best objective', OBJVAL 'objective value';
OBJEST = GAMS_MODEL.objest;
OBJVAL = GAMS_MODEL.objval;
Scalar NUMVAR 'number of variables';
NUMVAR = GAMS_MODEL.numvar
Scalar NUMEQU 'number of equations';
NUMEQU = GAMS_MODEL.numequ
Scalar NUMDVAR 'number of discrete variables';
NUMDVAR = GAMS_MODEL.numdvar
Scalar NUMNZ 'number of nonzeros';
NUMNZ = GAMS_MODEL.numnz
Scalar ETSOLVE 'time to execute solve statement';
ETSOLVE = GAMS_MODEL.etsolve# Specify the file path
# file_path = "/content/BARON_Output1.log" # Adjust this path if the file location differs
# Open and read the file
# with open(file_path, 'r') as file:
# content = file.read()
# Print the file content
# print(content)Here is the log file generated by GAMS/NEOS:
--- Job MODEL.gms Start 12/10/24 16:25:29 47.6.0 c2de9d6d LEX-LEG x86 64bit/Linux
--- Applying:
--- GAMS Parameters defined
Input /var/lib/condor/execute/dir_1446120/gamsexec/MODEL.gms
Output /var/lib/condor/execute/dir_1446120/gamsexec/solve.lst
PageWidth 79
PageSize 0
ScrDir /var/lib/condor/execute/dir_1446120/neos-1446125/
SysDir /opt/gams/47.6.0/
CurDir /var/lib/condor/execute/dir_1446120/gamsexec/
LogOption 4
LogFile /var/lib/condor/execute/dir_1446120/gamsexec/solve.log
AppendOut 1
AppendLog 0
Suppress 0
CErr 10
LimRow 0
LimCol 0
IDE 1
GDX /var/lib/condor/execute/dir_1446120/gamsexec/out.gdx
ExecMode 3
gdxCompress 1
Solver baron
Licensee: NEOS Server License G241014+0003Ac-GEN
Wisconsin Institutes for Discovery DCE1890
/opt/gams/47.6.0/gamslice.txt
node:90046401
Evaluation license: Not for commercial or production use
The evaluation period of the license will expire on Dec 08, 2025
Processor information: 2 socket(s), 32 core(s), and 64 thread(s) available
GAMS 47.6.0 Copyright (C) 1987-2024 GAMS Development. All rights reserved
--- Starting compilation
--- MODEL.gms(96) 2 Mb[FIL:"/var/lib/condor/execute/dir_1446120/gamsexec/MODEL.gms",96,0]
--- Starting execution: elapsed 0:00:00.015[LST:10]
--- MODEL.gms(71) 3 Mb[FIL:"/var/lib/condor/execute/dir_1446120/gamsexec/MODEL.gms",71,0]
--- Generating NLP model GAMS_MODEL[LST:10]
--- MODEL.gms(72) 5 Mb[FIL:"/var/lib/condor/execute/dir_1446120/gamsexec/MODEL.gms",72,0]
--- Reset Solvelink = 2
--- 16 rows 9 columns 33 non-zeroes
--- 30 nl-code 12 nl-non-zeroes
--- Range statistics (absolute non-zero finite values)
--- RHS [min, max] : [ 3.000E+00, 2.250E+02] - Zero values observed as well
--- Bound [min, max] : [ NA, NA] - Zero values observed as well
--- Matrix [min, max] : [ 1.000E+00, 4.600E+01] - Zero values observed as well
--- MODEL.gms(72) 3 Mb[FIL:"/var/lib/condor/execute/dir_1446120/gamsexec/MODEL.gms",72,0]
--- Executing BARON (Solvelink=2): elapsed 0:00:00.017[LST:23]
GAMS/BARON 47.6.0 c2de9d6d Sep 12, 2024 LEG x86 64bit/Linux
===========================================================================
BARON version 24.5.8. Built: LNX-64 Wed May 8 10:06:40 EDT 2024
Running on machine prod-exec-7.neos-server.org
BARON is a product of The Optimization Firm.
For information on BARON, see https://minlp.com/about-baron
If you publish work using this software, please cite publications from
https://minlp.com/baron-publications, such as:
Khajavirad, A. and N. V. Sahinidis,
A hybrid LP/NLP paradigm for global optimization relaxations,
Mathematical Programming Computation, 10, 383-421, 2018.
===========================================================================
This BARON run may utilize the following subsolver(s)
For LP/MIP/QP: CLP/CBC, ILOG CPLEX
For NLP: MINOS, SNOPT, External NLP, IPOPT, FILTERSQP
===========================================================================
Starting solution is feasible with a value of 150.000
Doing local search
Preprocessing found feasible solution with value 98.2843
Solving bounding LP
Starting multi-start local search
Done with local search
===========================================================================
Iteration Open nodes Time (s) Lower bound Upper bound
1 1 0.04 80.0000 98.2843
11 0 0.08 98.2843 98.2843
*** Normal completion ***
Wall clock time: 0.09
Total CPU time used: 0.08
Total no. of BaR iterations: 11
Best solution found at node: -1
Max. no. of nodes in memory: 3
All done
===========================================================================
Solution = 98.2842712474619 best solution found during preprocessing
Best possible = 98.2842712474619
Absolute gap = 0 optca = 1E-9
Relative gap = 0 optcr = 0.0001
--- Reading solution for model GAMS_MODEL[LST:35]
***
*** Solver did not provide marginals for model GAMS_MODEL
***
--- Executing after solve: elapsed 0:00:00.134[LST:89]
--- MODEL.gms(95) 3 Mb[FIL:"/var/lib/condor/execute/dir_1446120/gamsexec/MODEL.gms",95,0]
--- GDX File /var/lib/condor/execute/dir_1446120/gamsexec/out.gdx[FIL:"/var/lib/condor/execute/dir_1446120/gamsexec/out.gdx",0,0]
*** Status: Normal completion[LST:105]
--- Job MODEL.gms Stop 12/10/24 16:25:29 elapsed 0:00:00.134
Takeaway Messages¶
A global solution for a nonconvex, nonlinear program can often be found given the problem meets certain criteria.
Solvers like Couenne or BARON have the capability to find the global optima of certain NLPs.
Methods like Spatial branch and bound can guarantee the optimality of solutions found for nonlinear programs with poor initialization given the complexity of the GO problem falls within certain assumptions.
Spatial branch and bound methods guarantee convergence but not in a finite number of steps.
Spatial Branch and Bound Methods partition the feasible region into subregions and enumerate each subregion’s optimal solution. These solutions converge to a globally optimal solution.
Future work ideas:
Experiment with different settings in Couenne
Add instructions on running BARON on the CRC
Show how solver time (Couenne versus Ipopt) changes with the number of circles.
References¶
Biegler, L. T. (2010). Nonlinear programming: concepts, algorithms, and applications to chemical processes. Society for Industrial and Applied Mathematics.
Locatelli, M., & Schoen, F. (Eds.). (2013). Global optimization: theory, algorithms, and applications. Society for Industrial and Applied Mathematics.
NEOS Server. (n.d.). BARON solver for GAMS. NEOS Server. Retrieved December 9, 2024, from https://
Pyomo Documentation. (n.d.). ProblemWriter_gams — Pyomo documentation (version 6.8.0). Retrieved December 9, 2024, from https://
https://
- Locatelli, M., & Schoen, F. (2013). Global Optimization: Theory, Algorithms, and Applications. Society for Industrial. 10.1137/1.9781611972672