import math
from dataclasses import dataclass
from plot import draw_comparison, draw_layout, draw_layouts
from report import report_counts, report_layout
@dataclass
class Field:
width: float
length: float
segment_length: float
min_segments: int
max_segments: int
machine_cost: float
segment_cost: float
operating_cost: float
margin: float
@property
def area(self):
return self.width * self.length
@dataclass
class Layout:
npv: float
x: list
y: list
segments: list
@property
def num_machines(self):
return len(self.segments)
def radius(field, segments):
return segments * field.segment_length
def covered_area(field, segments):
return sum(math.pi * radius(field, s) ** 2 for s in segments)
def coverage(field, layout):
return covered_area(field, layout.segments) / field.area
def net_present_value(field, segments):
margin = covered_area(field, segments) * field.margin
machines_cost = len(segments) * field.machine_cost
segments_cost = sum(s - 1 for s in segments) * field.segment_cost
return margin - machines_cost - segments_cost - field.operating_costPivot Irrigators
Lay out centre-pivot irrigation machines in a field to maximize the net present value of the investment, a circle-packing problem with discrete radii.
Introduction
We consider the problem of designing the layout of center-pivot irrigation machines in a field, which can be modeled as a circle packing problem.
Pivot irrigators are commonly used by crop farmers to supplement natural rainfall. For example, large areas of the mid-west USA are covered with these machines. The machines are almost always arranged in a simple grid pattern, which is not an efficient design in terms of coverage.
We consider the following situation:
- In a semi-arid region, only irrigated areas are productive.
- We consider a rectangular field in this region, with sides of 914.400 by 442.570 metres, with a total area of 40.4686 hectares (exactly 100 acres).
- The water distribution system of the field, composed of pivot irrigators, is worn out, so we need to replace it with the same type of machines.
- The machines are composed of a pivot mechanism and 20 metre long segments.
To maximize crop yield, it is important that we irrigate as much of the area as possible. However, we need to account for the cost of the machines, along with the operational and maintenance costs over their lifetime.
This example is based on this post.
Here is the grid layout of eight identical machines, and the layout the model finds for the same eight:
Both cover the same field with the same number of machines, and on the numbers below the grid is not merely worse. It loses money. Letting the machines differ in size and sit where they fit turns that loss into a profit.
Investment characteristics
Each machine costs $43,606 to purchase, install and for its maintenance over 15 years (its expected lifetime). A machine consists of the pivot mechanism and a single 20 metre long built-in segment.
Additional 20 metre long segments cost $15,803 each all included. A machine may have up to a total of eight segments (including the built-in segment).
We have fixed operating costs of $2,009,094 for 15 years, covering costs for other machinery and staff associated with working the field.
The planned crop will yield an average gross margin of $10.268 per square metre per year, allowing for all variable costs (planting, harvesting, etc).
A positive Net Present Value (NPV) would indicate that this is a worthwhile investment, while a negative one would indicate that the investment is a loss.
Furthermore, we note that larger machines are more profitable. Specifically, the cost of a machine is a linear function of the number of segments, while the yield from a machine is a function of the coverage area, which increases with the square of the number of segments. Therefore, all else being equal, larger machines are better.
In particular, a machine with only one or two segments makes a loss, while larger machines make a positive contribution to the NPV. Therefore, we only consider machines with at least 3 segments (including the built-in segment).
Problem description
Input
- \(S_{\text{size}}\) the length of each irrigation machine segment
- \(S^{\text{min}}\) the minimum number of segments per machine
- \(S^{\text{max}}\) the maximum number of segments per machine
- \(W\) the width of the field
- \(L\) the length of the field
- \(C_{\text{operating}}\) the operating cost (over 15 years)
- \(C_{\text{machine}}\) the cost of each irrigation machine (all included)
- \(C_{\text{segment}}\) the cost of each additional irrigation machine segment (all included)
- \(Y\) the yield per square metre irrigated
Problem:
Create a layout by choosing:
- the number of machines
- the number of segments of each machine
- the position of each machine’s pivot in the field
such that:
- the circle covered by each machine is within the field’s boundaries
- the circles covered by two machines cannot overlap
Objective:
Maximize the overall NPV of our investment.
This is a variant of a circle packing problem, where the radii of the circles are decision variables that must take values in a discrete set.
Mixed-integer nonlinear model
We simplify the model by making the number of machines an exogenous input \(N\). Otherwise, we would need an additional binary variable for each machine to decide whether we use it or not, which would unnecessarily complicate the model. We can instead solve the model iteratively over a reasonable range for the number of machines.
For a given number of machines \(N\), the model needs to decide, for each machine, the number of segments and the position of the machine’s pivot.
Variables
- \(s_i \in \mathbb{N}\), \(S^{\text{min}} \le s_i \le S^{\text{max}}\), \(i = 1, \dots, N\), the number of segments of machine \(i\) (including the built-in segment)
- \(x_i \in \mathbb{R}\), \(i = 1, \dots, N\), the \(x\) position of machine \(i\)’s pivot
- \(y_i \in \mathbb{R}\), \(i = 1, \dots, N\), the \(y\) position of machine \(i\)’s pivot
Objective: maximize the NPV, i.e. the total yield of the irrigated areas minus the cost of the machines, the cost of the additional segments and the operating cost
\[ \max \quad \left( \sum_{i=1}^N \pi \cdot (S_{\text{size}} \cdot s_i)^2 \right) \cdot Y - N \cdot C_{\text{machine}} - \left( \sum_{i=1}^N (s_i - 1) \right) \cdot C_{\text{segment}} - C_{\text{operating}} \]
Note that the cost part of the NPV calculation is linear. But the yield is a function of the area covered by each machine, which depends on the squared number of segments of the machine: the objective is therefore nonlinear (quadratic).
Constraints
- Irrigation circles are within the field’s boundaries:
\[ \forall i = 1, \dots, N, \qquad S_{\text{size}} \cdot s_i \le x_i \le W - S_{\text{size}} \cdot s_i \]
\[ \forall i = 1, \dots, N, \qquad S_{\text{size}} \cdot s_i \le y_i \le L - S_{\text{size}} \cdot s_i \]
- Irrigation circles must not overlap, i.e. the distance between two pivots must be at least the sum of the radii of the two irrigation circles:
\[ \forall i, j = 1, \dots, N, \; i<j, \qquad (x_i - x_j)^2 + (y_i - y_j)^2 \ge \left( S_{\text{size}} \cdot (s_i + s_j) \right)^2 \]
These non-overlap constraints are nonconvex quadratic constraints, which makes this problem a nonconvex mixed-integer nonlinear program (MINLP).
Input data
A Field is the field and the money. It holds how big the field is, how long a segment is, how many segments a machine may carry, what a machine and a segment cost, what running the field costs, and what a square metre yields in a year. A Layout is where each machine stands and how many segments it carries, together with the net present value that layout earns.
net_present_value is the objective written out in plain code, so a layout that was never solved for can be priced the same way as one that was.
The field is 914.400 by 442.570 metres, machines are built from 20 metre segments and carry between 3 and 8 of them, and the costs and yield are the ones listed above, in dollars over the fifteen year lifetime. grid_layout is the arrangement farms actually use, four machines by two, every one the same size and as large as the spacing allows.
field = Field(
width=914.400,
length=442.570,
segment_length=20,
min_segments=3,
max_segments=8,
machine_cost=43606.07950630836,
segment_cost=15803.03975315418,
operating_cost=2009094.3111355049,
margin=10.268207333516287,
)
def grid_layout(field, segments=5):
reach = radius(field, segments)
columns = [reach + k * (field.width - 2 * reach) / 3 for k in range(4)]
rows = [reach, field.length - reach]
counts = [float(segments)] * (4 * len(rows))
x = [column for _ in rows for column in columns]
y = [row for row in rows for _ in columns]
return Layout(net_present_value(field, counts), x, y, counts)A layout is the field seen from above, each machine a disc as wide as its reach. The dashed rings inside a disc are its segments, so a bigger machine is both wider and more finely drawn, and the number at the center is how many it carries. Ground no disc covers is ground that earns nothing.
Eight machines on a grid is the arrangement to beat. It leaves the four corners, the gaps between neighbours and a strip right across the middle dry, and on these numbers it does not merely earn less than it could. It loses money.
report_layout(field, grid_layout(field))8 machines, net present value -$282,958, covering 62.1% of the field
machine segments reach x y covered share
------------------------------------------------------------------
1 5 100m 100.0 100.0 31,416 7.8%
2 5 100m 338.1 100.0 31,416 7.8%
3 5 100m 576.3 100.0 31,416 7.8%
4 5 100m 814.4 100.0 31,416 7.8%
5 5 100m 100.0 342.6 31,416 7.8%
6 5 100m 338.1 342.6 31,416 7.8%
7 5 100m 576.3 342.6 31,416 7.8%
8 5 100m 814.4 342.6 31,416 7.8%
Margin $2,580,682 less $348,849 of machines, $505,697 of segments,
$2,009,094 to operatedraw_layout(field, grid_layout(field), "Eight machines on a grid")Model implementation
import pyomo.environ as pyo
SOLVER_NAME = "knitroampl"maximize_npv(field, num_machines) builds the model, solves it with Knitro, and returns a Layout. The objective and the non-overlap constraints multiply two variables, and Objective and Constraint take them as written.
Since the problem is a nonconvex MINLP, we enable Knitro’s MIP multistart, which helps find good solutions, and we set a node limit on the branch-and-bound to bound the resolution time.
def maximize_npv(field, num_machines, *, multistart=1, max_nodes=2**14):
model = pyo.ConcreteModel()
reach = radius(field, field.min_segments)
bounds = (field.min_segments, field.max_segments)
model.Machines = pyo.RangeSet(0, num_machines - 1)
model.s = pyo.Var(model.Machines, within=pyo.Integers, bounds=bounds)
model.x = pyo.Var(model.Machines, bounds=(reach, field.width - reach))
model.y = pyo.Var(model.Machines, bounds=(reach, field.length - reach))
def objective_rule(model):
area = sum(math.pi * radius(field, model.s[i]) ** 2 for i in model.Machines)
margin = field.margin * area
machines_cost = num_machines * field.machine_cost
segments_cost = field.segment_cost * sum(model.s[i] - 1 for i in model.Machines)
return margin - machines_cost - segments_cost - field.operating_cost
model.obj = pyo.Objective(rule=objective_rule, sense=pyo.maximize)
def x_lower_rule(model, i):
return model.x[i] >= model.s[i] * field.segment_length
model.x_lower = pyo.Constraint(model.Machines, rule=x_lower_rule)
def x_upper_rule(model, i):
return model.x[i] <= field.width - model.s[i] * field.segment_length
model.x_upper = pyo.Constraint(model.Machines, rule=x_upper_rule)
def y_lower_rule(model, i):
return model.y[i] >= model.s[i] * field.segment_length
model.y_lower = pyo.Constraint(model.Machines, rule=y_lower_rule)
def y_upper_rule(model, i):
return model.y[i] <= field.length - model.s[i] * field.segment_length
model.y_upper = pyo.Constraint(model.Machines, rule=y_upper_rule)
def no_overlap_rule(model, i, j):
if i >= j:
return pyo.Constraint.Skip
dx = model.x[i] - model.x[j]
dy = model.y[i] - model.y[j]
radii = (model.s[i] + model.s[j]) * field.segment_length
return dx**2 + dy**2 >= radii**2
model.no_overlap = pyo.Constraint(
model.Machines, model.Machines, rule=no_overlap_rule
)
solver = pyo.SolverFactory(SOLVER_NAME)
solver.options["mip_multistart"] = multistart
solver.options["mip_maxnodes"] = max_nodes
solver.solve(model, tee=True)
npv = model.obj()
x = [model.x[i]() for i in model.Machines]
y = [model.y[i]() for i in model.Machines]
s = [model.s[i]() for i in model.Machines]
return Layout(npv, x, y, s)Solving for eight machines
Eight is the number the grid uses, so it is the first thing to ask for, the same field and the same count with the machines free to move and free to differ in size.
layout_8 = maximize_npv(field, 8)Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 24 | 24
bounds: lower upper range | lower upper range
0 0 24 | 0 0 24
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
16 0 8 | 16 0 8
Number of constraints: 60 | 60
eq. ineq. range | eq. ineq. range
linear: 0 32 0 | 0 32 0
quadratic: 0 28 0 | 0 28 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 8 64 | 8 64
quadratic: 8 168 108 | 8 168 108
total: 8 232 108 | 8 232 108
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.68170e+06 14400.9 0.211068 0.019
1 -2.16662e+06 4168.94 0.883468 0.019
2 -2.26549e+06 1092.99 2.17355 0.020
3 -2.26807e+06 339.753 2.54056 0.020
4 -2.26491e+06 260.932 2.65815 0.020
5 -2.26283e+06 218.536 2.70606 0.021
6 -2.26142e+06 192.766 2.73660 0.021
7 -2.26055e+06 169.998 2.75323 0.021
8 -2.26013e+06 152.644 2.76265 0.022
9 -2.25975e+06 137.853 2.77337 0.022
10 -2.25951e+06 123.626 2.78079 0.022
11 -2.26022e+06 128.740 2.76929 0.023
12 -2.26036e+06 110.239 2.76954 0.023
13 -2.26062e+06 100.133 2.76746 0.023
14 -2.26147e+06 97.2033 2.75282 0.024
15 -2.26227e+06 86.6805 2.73710 0.024
16 -2.26340e+06 82.5117 2.71494 0.025
17 -2.26488e+06 68.6615 2.68155 0.025
18 -2.26605e+06 64.0655 2.65265 0.025
19 -2.26688e+06 55.3387 2.62733 0.026
20 -2.26779e+06 45.5852 2.59725 0.026
30 -2.23557e+06 9.53453 4.36023 0.029
40 -1.65424e+06 232.595 4.82700 0.032
50 -1.11012e+06 152.262 9.92205 0.035
60 -747654. 0.00000e+00 18.6515 0.037
70 -366752. 0.00000e+00 32.0751 0.039
80 -47698.0 0.00000e+00 1.38662 0.041
90 194786. 0.00000e+00 11.4787 0.044
100 224245. 0.00000e+00 2.09363e-03 0.045
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.096
1 2 26723.6 LS inf 0.104
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.168
31 31 201572. FCRD inf 0.225
39 39 276093. LS inf 0.232
78 59 324807. FCRD inf 0.284
586 234 353513. FCRD inf 0.814
7893 466 353513. inf 12.374
15825 538 353513. inf 26.231
16384 543 353513. inf 27.108
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.53513363574206363e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16384 (211.279s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16637 (212.100s)
Total program time (secs) = 27.11084 (215.465 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 2 / 1 / 0.103s
Rounding heuristic = 235 / 11 / 0.660s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.108s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 353513.36357420636; optimality
gap Infinity; 16384 nodes; 16637 subproblem solvesShow the full outputHide the full output
report_layout(field, layout_8)8 machines, net present value $353,513, covering 78.6% of the field
machine segments reach x y covered share
------------------------------------------------------------------
1 3 60m 426.4 380.4 11,310 2.8%
2 4 80m 832.1 359.8 20,106 5.0%
3 5 100m 641.7 341.4 31,416 7.8%
4 4 80m 85.3 358.1 20,106 5.0%
5 7 140m 140.0 140.0 61,575 15.2%
6 8 160m 453.8 160.0 80,425 19.9%
7 7 140m 774.4 140.0 61,575 15.2%
8 5 100m 268.7 342.6 31,416 7.8%
Margin $3,264,563 less $348,849 of machines, $553,106 of segments,
$2,009,094 to operatedraw_layout(field, layout_8)Solving for every count
The number of machines is an input to the model rather than something it decides, so the question of how many to buy is answered by solving once for each count in a reasonable range.
counts = range(3, 15)layouts = [maximize_npv(field, num_machines) for num_machines in counts]Show the full outputHide the full output
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 9 | 9
bounds: lower upper range | lower upper range
0 0 9 | 0 0 9
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
6 0 3 | 6 0 3
Number of constraints: 15 | 15
eq. ineq. range | eq. ineq. range
linear: 0 12 0 | 0 12 0
quadratic: 0 3 0 | 0 3 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 3 24 | 3 24
quadratic: 3 18 18 | 3 18 18
total: 3 42 18 | 3 42 18
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.88632e+06 14400.5 0.501635 0.046
1 -2.06819e+06 4167.22 0.842228 0.046
2 -2.10427e+06 1234.37 3.39503 0.046
3 -2.10698e+06 111.217 1.26369 0.047
4 -2.10695e+06 59.7654 1.26369 0.047
5 -2.10642e+06 92.8391 6.41785 0.047
6 -2.09065e+06 13.1853 2.33209 0.047
7 -2.08488e+06 3.70580 2.26512 0.047
8 -2.04651e+06 2.10497 3.51711 0.047
9 -1.97529e+06 1.99335 5.37828 0.047
10 -1.90748e+06 1.92130 6.61155 0.047
11 -1.90118e+06 1.84598 6.68489 0.047
12 -1.79043e+06 0.00000e+00 25.4903 0.047
13 -1.88553e+06 0.00000e+00 20.5534 0.048
14 -1.83404e+06 0.00000e+00 20.7001 0.048
15 -1.88170e+06 0.00000e+00 23.5012 0.048
16 -1.79059e+06 0.00000e+00 26.2563 0.048
17 -1.63380e+06 1097.77 28.0065 0.048
18 -1.38461e+06 17.6110 8.43785 0.048
19 -1.09667e+06 618.684 10.7709 0.048
20 -849069. 303.318 23.1336 0.048
30 -1493.85 0.00000e+00 17.7717 0.049
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 1 5678.31 LEAF inf 0.051
200 0 5678.31 5678.31 0.00% 0.649
EXIT: Optimal solution found (assuming convexity).
Final Statistics for MIP
------------------------
Final objective value = 5.67831437182333320e+03
Final bound value = 5.67831437182333320e+03
Final optimality gap (abs / rel) = 0.00000e+00 / 0.00000e+00 (0.00%)
# of root cutting plane rounds = 0
# of restarts = 0
# of nodes processed = 200 (0.610s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 200 (0.610s)
Total program time (secs) = 0.64910 (0.644 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 0 / 0 / 0.000s
Rounding heuristic = 0 / 0 / 0.000s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 5 / 4 / 0.011s
===========================================================================
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 12 | 12
bounds: lower upper range | lower upper range
0 0 12 | 0 0 12
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
8 0 4 | 8 0 4
Number of constraints: 22 | 22
eq. ineq. range | eq. ineq. range
linear: 0 16 0 | 0 16 0
quadratic: 0 6 0 | 0 6 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 4 32 | 4 32
quadratic: 4 36 30 | 4 36 30
total: 4 68 30 | 4 68 30
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.84540e+06 14400.9 0.405803 0.050
1 -2.08787e+06 4168.14 0.807571 0.050
2 -2.13661e+06 1170.59 1.70845 0.051
3 -2.13934e+06 412.886 2.46895 0.051
4 -2.13865e+06 315.701 2.53609 0.051
5 -2.13823e+06 268.085 2.56761 0.051
6 -2.13791e+06 232.825 2.58594 0.051
7 -2.13772e+06 200.157 2.59659 0.051
8 -2.13774e+06 170.926 2.59645 0.051
9 -2.13788e+06 141.808 2.58998 0.052
10 -2.13823e+06 119.556 2.57123 0.052
11 -2.13883e+06 23.7446 2.53085 0.052
12 -2.13910e+06 2.50803 2.50803 0.052
13 -2.13961e+06 52.0198 1.67954 0.052
14 -2.13700e+06 55.2317 8.91996 0.052
15 -2.13410e+06 20.6321 6.36662 0.052
16 -2.12915e+06 36.5047 5.57905 0.052
17 -2.11475e+06 16.0126 4.18197 0.053
18 -2.05463e+06 1.93271 4.66114 0.053
19 -1.97220e+06 1.87812 6.75993 0.053
20 -1.81578e+06 1.82578 9.63717 0.053
30 -393714. 0.00000e+00 16.7042 0.054
40 20296.1 0.00000e+00 6.03313 0.055
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -56630.4 FCRD inf 0.060
3 4 43697.2 FCRD inf 0.068
Knitro deduced that the problem is non-convex.
13 10 46596.8 FCRD inf 0.082
6438 5 46596.8 inf 3.681
EXIT: Satisfactory solution found.
Final Statistics for MIP
------------------------
Final objective value = 4.65968443674487062e+04
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 6663 (23.865s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 6703 (23.964s)
Total program time (secs) = 4.05624 (25.026 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 1 / 1 / 0.011s
Rounding heuristic = 32 / 6 / 0.077s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 4 / 0.020s
===========================================================================
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 15 | 15
bounds: lower upper range | lower upper range
0 0 15 | 0 0 15
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
10 0 5 | 10 0 5
Number of constraints: 30 | 30
eq. ineq. range | eq. ineq. range
linear: 0 20 0 | 0 20 0
quadratic: 0 10 0 | 0 10 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 5 40 | 5 40
quadratic: 5 60 45 | 5 60 45
total: 5 100 45 | 5 100 45
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.80447e+06 14401.0 0.325242 0.010
1 -2.10756e+06 4168.43 0.812609 0.011
2 -2.16887e+06 1137.06 3.43957 0.011
3 -2.17160e+06 400.918 2.49868 0.011
4 -2.17061e+06 296.328 2.57022 0.011
5 -2.17028e+06 262.835 2.59699 0.011
6 -2.17000e+06 235.623 2.61645 0.012
7 -2.16973e+06 210.443 2.63277 0.012
8 -2.16955e+06 181.069 2.64461 0.012
9 -2.16965e+06 172.926 2.64238 0.012
10 -2.16971e+06 154.353 2.64316 0.012
11 -2.16997e+06 160.791 2.63243 0.012
12 -2.17021e+06 151.746 2.62253 0.013
13 -2.17034e+06 132.233 2.61898 0.013
14 -2.17108e+06 132.136 2.57786 0.013
15 -2.17123e+06 131.574 2.56734 0.013
16 -2.17148e+06 130.268 2.54818 0.013
17 -2.17118e+06 118.390 2.53168 0.013
18 -2.16638e+06 88.2926 2.50191 0.013
19 -2.16220e+06 80.8362 2.47693 0.014
20 -2.11676e+06 54.5914 3.93852 0.014
30 -1.66705e+06 511.526 6.17690 0.015
40 -747510. 0.00000e+00 56.5714 0.017
50 -457676. 0.00000e+00 11.3599 0.018
60 4426.14 0.00000e+00 30.8073 0.019
70 198100. 0.00000e+00 7.91531e-05 0.020
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -15711.9 FCRD inf 0.025
Knitro deduced that the problem is non-convex.
5 6 159137. FP inf 0.047
29 19 159137. FCRD inf 0.071
48 27 159137. FCRD inf 0.092
7933 95 159137. inf 5.717
15931 114 159137. inf 11.175
16387 115 159137. inf 11.462
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 1.59136573975202627e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16387 (88.074s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16544 (88.462s)
Total program time (secs) = 11.46296 (91.149 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 1 / 1 / 0.011s
Rounding heuristic = 148 / 9 / 0.372s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 10 / 5 / 0.036s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 159136.57397520263; optimality
gap Infinity; 16387 nodes; 16544 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 18 | 18
bounds: lower upper range | lower upper range
0 0 18 | 0 0 18
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
12 0 6 | 12 0 6
Number of constraints: 39 | 39
eq. ineq. range | eq. ineq. range
linear: 0 24 0 | 0 24 0
quadratic: 0 15 0 | 0 15 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 6 48 | 6 48
quadratic: 6 90 63 | 6 90 63
total: 6 138 63 | 6 138 63
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.76355e+06 14400.9 0.309700 0.012
1 -2.12725e+06 4168.71 0.825003 0.012
2 -2.20109e+06 1116.69 2.55192 0.012
3 -2.20372e+06 380.694 2.52326 0.012
4 -2.20162e+06 301.184 2.63173 0.013
5 -2.20027e+06 253.939 2.67807 0.013
6 -2.19910e+06 225.481 2.71462 0.013
7 -2.19822e+06 197.827 2.73975 0.013
8 -2.19798e+06 157.203 2.74807 0.013
9 -2.19794e+06 116.356 2.75150 0.014
10 -2.20015e+06 117.185 2.69775 0.014
11 -2.20058e+06 94.9885 2.68577 0.014
12 -2.20151e+06 69.9709 2.65798 0.014
13 -2.20216e+06 13.0110 2.63593 0.014
14 -2.20472e+06 7.96774 2.48351 0.015
15 -2.20438e+06 9.23421 4.46614 0.015
16 -2.20397e+06 4.37353 5.31762 0.015
17 -2.19688e+06 99.5102 22.9065 0.015
18 -2.19168e+06 23.3763 2.59914 0.015
19 -2.18321e+06 83.7613 4.79058 0.015
20 -2.16916e+06 25.8680 2.47774 0.016
30 -1.61086e+06 363.544 49.1107 0.017
40 -515446. 0.00000e+00 9.46295 0.019
50 -189972. 0.00000e+00 1.58248 0.020
60 103406. 0.00000e+00 8.91541 0.022
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 48113.8 FCRD inf 0.027
Knitro deduced that the problem is non-convex.
15 16 148441. FCRD inf 0.057
54 47 200055. FCRD inf 0.099
7853 187 200055. inf 7.567
15814 246 200055. inf 14.970
16386 248 200055. inf 15.477
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 2.00055103970827535e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16386 (119.654s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16611 (120.225s)
Total program time (secs) = 15.47940 (123.054 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 1 / 0 / 0.002s
Rounding heuristic = 221 / 10 / 0.591s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 5 / 0.043s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 200055.10397082753; optimality
gap Infinity; 16386 nodes; 16611 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 21 | 21
bounds: lower upper range | lower upper range
0 0 21 | 0 0 21
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
14 0 7 | 14 0 7
Number of constraints: 49 | 49
eq. ineq. range | eq. ineq. range
linear: 0 28 0 | 0 28 0
quadratic: 0 21 0 | 0 21 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 7 56 | 7 56
quadratic: 7 126 84 | 7 126 84
total: 7 182 84 | 7 182 84
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.72262e+06 14400.9 0.244790 0.015
1 -2.14694e+06 4168.80 0.853542 0.015
2 -2.23330e+06 1102.75 2.16985 0.016
3 -2.23585e+06 338.041 2.53484 0.016
4 -2.23247e+06 205.204 2.66089 0.016
5 -2.23059e+06 150.239 2.70685 0.016
6 -2.22955e+06 123.198 2.72925 0.017
7 -2.22899e+06 102.116 2.74276 0.017
8 -2.22865e+06 80.7539 2.75485 0.017
9 -2.22870e+06 65.5838 2.75857 0.017
10 -2.22907e+06 50.7054 2.75526 0.018
11 -2.23189e+06 37.6813 2.69621 0.018
12 -2.23242e+06 23.0712 2.68541 0.018
13 -2.23356e+06 49.2455 2.65545 0.018
14 -2.23677e+06 37.1895 2.52062 0.018
15 -2.23677e+06 32.3409 7.56834 0.019
16 -2.23428e+06 26.7500 3.22402 0.019
17 -2.22477e+06 50.4409 2.30554 0.019
18 -2.20441e+06 14.6173 2.29534 0.019
19 -2.18891e+06 13.1769 2.79701 0.019
20 -2.11495e+06 11.9943 4.69835 0.020
30 -1.06835e+06 0.00000e+00 9.43860 0.022
40 -570241. 659.182 5.93091 0.024
50 -180137. 0.00000e+00 9.54394 0.026
60 69174.2 0.00000e+00 3.32023 0.028
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -11295.3 FCRD inf 0.032
Knitro deduced that the problem is non-convex.
3 4 66125.2 FCRD inf 0.050
7 8 140646. LS inf 0.062
13 14 169352. FCRD inf 0.073
28 29 189360. FCRD inf 0.096
36 37 240974. FCRD inf 0.104
146 114 312595. FCRD inf 0.194
7846 218 312595. inf 8.253
15592 289 312595. inf 16.722
16388 295 312595. inf 17.679
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.12594833578581456e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (136.829s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16581 (137.315s)
Total program time (secs) = 17.68055 (140.356 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 2 / 0 / 0.039s
Rounding heuristic = 178 / 15 / 0.455s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.077s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 312594.83357858146; optimality
gap Infinity; 16388 nodes; 16581 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 24 | 24
bounds: lower upper range | lower upper range
0 0 24 | 0 0 24
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
16 0 8 | 16 0 8
Number of constraints: 60 | 60
eq. ineq. range | eq. ineq. range
linear: 0 32 0 | 0 32 0
quadratic: 0 28 0 | 0 28 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 8 64 | 8 64
quadratic: 8 168 108 | 8 168 108
total: 8 232 108 | 8 232 108
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.68170e+06 14400.9 0.211068 0.019
1 -2.16662e+06 4168.94 0.883468 0.019
2 -2.26549e+06 1092.99 2.17355 0.020
3 -2.26807e+06 339.753 2.54056 0.020
4 -2.26491e+06 260.932 2.65815 0.020
5 -2.26283e+06 218.536 2.70606 0.020
6 -2.26142e+06 192.766 2.73660 0.021
7 -2.26055e+06 169.998 2.75323 0.021
8 -2.26013e+06 152.644 2.76265 0.021
9 -2.25975e+06 137.853 2.77337 0.022
10 -2.25951e+06 123.626 2.78079 0.022
11 -2.26022e+06 128.740 2.76929 0.022
12 -2.26036e+06 110.239 2.76954 0.023
13 -2.26062e+06 100.133 2.76746 0.023
14 -2.26147e+06 97.2033 2.75282 0.023
15 -2.26227e+06 86.6805 2.73710 0.024
16 -2.26340e+06 82.5117 2.71494 0.024
17 -2.26488e+06 68.6615 2.68155 0.025
18 -2.26605e+06 64.0655 2.65265 0.025
19 -2.26688e+06 55.3387 2.62733 0.026
20 -2.26779e+06 45.5852 2.59725 0.026
30 -2.23557e+06 9.53453 4.36023 0.031
40 -1.65424e+06 232.595 4.82700 0.035
50 -1.11012e+06 152.262 9.92205 0.038
60 -747654. 0.00000e+00 18.6515 0.042
70 -366752. 0.00000e+00 32.0751 0.045
80 -47698.0 0.00000e+00 1.38662 0.049
90 194786. 0.00000e+00 11.4787 0.052
100 224245. 0.00000e+00 2.09363e-03 0.055
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.060
1 2 26723.6 LS inf 0.064
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.098
31 31 201572. FCRD inf 0.142
39 39 276093. LS inf 0.147
78 59 324807. FCRD inf 0.200
586 234 353513. FCRD inf 0.735
7893 466 353513. inf 12.204
15825 538 353513. inf 25.883
16384 543 353513. inf 26.752
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.53513363574206363e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16384 (209.095s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16637 (209.781s)
Total program time (secs) = 26.75425 (213.134 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 2 / 1 / 0.054s
Rounding heuristic = 235 / 11 / 0.635s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.083s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 353513.36357420636; optimality
gap Infinity; 16384 nodes; 16637 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 27 | 27
bounds: lower upper range | lower upper range
0 0 27 | 0 0 27
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
18 0 9 | 18 0 9
Number of constraints: 72 | 72
eq. ineq. range | eq. ineq. range
linear: 0 36 0 | 0 36 0
quadratic: 0 36 0 | 0 36 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 9 72 | 9 72
quadratic: 9 216 135 | 9 216 135
total: 9 288 135 | 9 288 135
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.64077e+06 14401.0 0.209474 0.035
1 -2.18631e+06 4169.00 0.972220 0.036
2 -2.29768e+06 1085.58 2.17634 0.036
3 -2.30019e+06 332.058 2.54598 0.036
4 -2.29609e+06 208.243 2.66660 0.037
5 -2.29362e+06 154.106 2.71494 0.037
6 -2.29202e+06 129.462 2.74536 0.037
7 -2.29101e+06 114.596 2.76314 0.038
8 -2.29033e+06 94.6734 2.77424 0.038
9 -2.29020e+06 58.7190 2.77658 0.038
10 -2.29405e+06 74.2433 2.71926 0.039
11 -2.29449e+06 58.6296 2.71225 0.039
12 -2.29534e+06 41.7538 2.69742 0.039
13 -2.29655e+06 2.67403 2.67403 0.040
14 -2.29757e+06 9.85655 2.65300 0.040
15 -2.29832e+06 14.5454 2.63608 0.041
16 -2.29907e+06 18.9549 2.61714 0.041
17 -2.29986e+06 19.1783 2.59476 0.041
18 -2.30040e+06 18.9224 2.57703 0.042
19 -2.30103e+06 68.2573 2.55290 0.044
20 -2.30138e+06 40.6419 2.53644 0.045
30 -2.27459e+06 1.94848 25.0990 0.048
40 -2.21166e+06 1.65880 40.6006 0.051
50 -1.16443e+06 1.69438e-02 7.01353 0.055
60 -292557. 0.00000e+00 7.57059 0.058
70 -92475.1 0.00000e+00 13.7865 0.061
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -204634. FCRD inf 0.066
Knitro deduced that the problem is non-convex.
3 4 -130114. FP inf 0.085
15 16 -9778.33 FCRD inf 0.112
22 23 271197. FCRD inf 0.130
111 71 317011. FCRD inf 0.264
271 134 322811. FCRD inf 0.455
7227 484 322811. inf 15.300
14604 686 322811. inf 30.464
16388 719 322811. inf 34.113
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.22810693957703654e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (267.721s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16690 (268.502s)
Total program time (secs) = 34.11502 (272.084 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 1 / 1 / 0.004s
Rounding heuristic = 298 / 14 / 0.817s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 12 / 5 / 0.095s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 322810.69395770365; optimality
gap Infinity; 16388 nodes; 16690 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 30 | 30
bounds: lower upper range | lower upper range
0 0 30 | 0 0 30
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
20 0 10 | 20 0 10
Number of constraints: 85 | 85
eq. ineq. range | eq. ineq. range
linear: 0 40 0 | 0 40 0
quadratic: 0 45 0 | 0 45 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 10 80 | 10 80
quadratic: 10 270 165 | 10 270 165
total: 10 350 165 | 10 350 165
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.59985e+06 14401.0 0.237159 0.072
1 -2.20600e+06 4169.18 0.947036 0.072
2 -2.32986e+06 1080.05 2.17851 0.073
3 -2.33210e+06 320.093 2.55558 0.073
4 -2.32617e+06 247.255 2.69173 0.074
5 -2.32286e+06 210.928 2.74728 0.074
6 -2.32054e+06 189.619 2.77817 0.074
7 -2.31899e+06 171.477 2.79361 0.075
8 -2.31814e+06 154.914 2.79851 0.075
9 -2.31782e+06 130.244 2.79963 0.076
10 -2.31802e+06 115.010 2.79937 0.076
11 -2.31920e+06 120.375 2.78645 0.076
12 -2.31894e+06 103.102 2.79148 0.077
13 -2.31914e+06 93.7453 2.79123 0.077
14 -2.31954e+06 85.7147 2.78857 0.078
15 -2.32020e+06 77.5530 2.78276 0.078
16 -2.32126e+06 70.6128 2.77192 0.078
17 -2.32234e+06 63.0897 2.76009 0.079
18 -2.32347e+06 57.5711 2.74661 0.079
19 -2.32484e+06 51.8753 2.72906 0.080
20 -2.32658e+06 49.5184 2.70419 0.080
30 -2.33494e+06 17.9013 2.49491 0.084
40 -1.85422e+06 0.465946 72.0767 0.089
50 -343240. 0.00000e+00 8.51260 0.094
60 -5174.53 0.00000e+00 6.30000 0.097
70 83941.5 0.00000e+00 2.69830 0.100
80 107140. 1.45519e-11 9.46702e-13 0.103
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 59846.6 FCRD inf 0.106
Knitro deduced that the problem is non-convex.
23 24 76954.6 FCRD inf 0.208
38 39 102761. FCRD inf 0.238
46 47 160174. FCRD inf 0.251
108 100 208888. FCRD inf 0.359
147 135 208888. FCRD inf 0.413
171 152 208888. FCRD inf 0.445
233 202 231795. FCRD inf 0.531
4786 609 260502. FCRD inf 13.479
6730 614 260502. inf 19.545
12628 967 312116. FCRD inf 35.551
13936 998 312116. inf 38.749
16391 1045 312116. inf 44.749
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.12115584394109435e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16391 (352.012s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16805 (353.116s)
Total program time (secs) = 44.75274 (356.865 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 3 / 1 / 0.071s
Rounding heuristic = 400 / 16 / 1.087s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 5 / 0.137s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 312115.58439410944; optimality
gap Infinity; 16391 nodes; 16805 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 33 | 33
bounds: lower upper range | lower upper range
0 0 33 | 0 0 33
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
22 0 11 | 22 0 11
Number of constraints: 99 | 99
eq. ineq. range | eq. ineq. range
linear: 0 44 0 | 0 44 0
quadratic: 0 55 0 | 0 55 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 11 88 | 11 88
quadratic: 11 330 198 | 11 330 198
total: 11 418 198 | 11 418 198
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.55892e+06 14401.0 0.184312 0.044
1 -2.22568e+06 4169.14 1.24444 0.044
2 -2.36204e+06 1075.25 2.18026 0.045
3 -2.36435e+06 316.479 2.55796 0.045
4 -2.35903e+06 195.818 2.68101 0.045
5 -2.35599e+06 157.615 2.72959 0.046
6 -2.35425e+06 127.053 2.75960 0.046
7 -2.35352e+06 96.8355 2.77302 0.047
8 -2.35371e+06 57.8037 2.77449 0.047
9 -2.35922e+06 105.574 2.70194 0.048
10 -2.35970e+06 76.7210 2.69532 0.048
11 -2.36024e+06 5.71021 2.68824 0.048
12 -2.36218e+06 2.65386 2.65386 0.049
13 -2.36683e+06 2.51510 4.55570 0.049
14 -2.35529e+06 2.48982 34.7539 0.050
15 -2.35419e+06 21.2098 5.68532 0.050
16 -2.35044e+06 29.0164 4.85545 0.051
17 -2.34107e+06 61.5293 2.53126 0.051
18 -2.32874e+06 47.4339 2.70344 0.051
19 -2.29618e+06 31.7195 3.99136 0.052
20 -2.23371e+06 31.6614 5.45247 0.052
30 -2.15081e+06 1.21544 61.5441 0.059
40 -1.78506e+06 0.372527 85.7464 0.063
50 -1.14209e+06 0.00000e+00 8.44370 0.068
60 -260542. 0.00000e+00 5.74022 0.071
70 -152791. 0.00000e+00 0.443641 0.075
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -223125. FCRD inf 0.082
Knitro deduced that the problem is non-convex.
3 4 -131496. FCRD inf 0.125
7 8 -102790. LS inf 0.151
35 36 46251.9 FCRD inf 0.241
60 58 169487. FCRD inf 0.296
217 180 175286. FCRD inf 0.691
225 185 201093. FCRD inf 0.707
610 322 224000. FCRD inf 1.573
1402 506 249807. FCRD inf 3.416
1416 511 252706. FCRD inf 3.446
5991 750 252706. FCRD inf 18.750
6762 769 252706. inf 21.444
7258 805 252706. FCRD inf 23.047
13699 1042 252706. inf 43.716
16384 1145 252706. inf 52.164
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 2.52706465134647675e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16384 (410.581s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16771 (411.805s)
Total program time (secs) = 52.16780 (416.189 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 1 / 0 / 0.057s
Rounding heuristic = 376 / 17 / 1.187s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 18 / 6 / 0.191s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 252706.46513464767; optimality
gap Infinity; 16384 nodes; 16771 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 36 | 36
bounds: lower upper range | lower upper range
0 0 36 | 0 0 36
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
24 0 12 | 24 0 12
Number of constraints: 114 | 114
eq. ineq. range | eq. ineq. range
linear: 0 48 0 | 0 48 0
quadratic: 0 66 0 | 0 66 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 12 96 | 12 96
quadratic: 12 396 234 | 12 396 234
total: 12 492 234 | 12 492 234
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.51800e+06 14401.0 0.173121 0.023
1 -2.24537e+06 4169.21 0.909667 0.024
2 -2.39422e+06 1071.62 2.18168 0.024
3 -2.39643e+06 312.026 2.56144 0.025
4 -2.39125e+06 218.641 2.68525 0.026
5 -2.38771e+06 175.826 2.73442 0.026
6 -2.38589e+06 150.937 2.75803 0.027
7 -2.38474e+06 130.566 2.76823 0.027
8 -2.38390e+06 114.545 2.77471 0.028
9 -2.38326e+06 102.220 2.78188 0.028
10 -2.38316e+06 91.6032 2.78313 0.029
11 -2.38388e+06 95.5451 2.77599 0.029
12 -2.38371e+06 85.8699 2.77754 0.030
13 -2.38376e+06 77.1747 2.77662 0.031
14 -2.38383e+06 69.3538 2.77515 0.031
15 -2.38403e+06 62.3258 2.77216 0.032
16 -2.38433e+06 56.6964 2.76791 0.032
17 -2.38480e+06 51.6220 2.76186 0.033
18 -2.38547e+06 47.2041 2.75444 0.034
19 -2.38752e+06 48.7163 2.73194 0.037
20 -2.38905e+06 17.6810 2.71391 0.038
30 -2.38111e+06 8.95845 6.32155 0.044
40 -2.32117e+06 2.10445 93.9809 0.051
50 -2.34003e+06 1.81585 34.9506 0.056
60 -2.15105e+06 1.14059 54.6783 0.060
70 -1.19408e+06 0.00000e+00 8.04973 0.065
80 -353016. 0.00000e+00 0.126411 0.069
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -434475. FCRD inf 0.074
Knitro deduced that the problem is non-convex.
2 3 38456.4 FCRD inf 0.092
153 127 64263.2 FCRD inf 0.624
279 236 138784. FCRD inf 0.963
2971 772 141684. FCRD inf 10.153
6974 795 141684. inf 28.277
9090 848 167491. FCRD inf 37.567
14213 1095 167491. inf 59.926
16388 1184 167491. inf 68.972
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 1.67490526095575653e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (544.554s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16844 (545.934s)
Total program time (secs) = 68.97519 (550.689 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 4 / 0 / 0.142s
Rounding heuristic = 435 / 11 / 1.305s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 12 / 4 / 0.163s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 167490.52609557565; optimality
gap Infinity; 16388 nodes; 16844 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 39 | 39
bounds: lower upper range | lower upper range
0 0 39 | 0 0 39
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
26 0 13 | 26 0 13
Number of constraints: 130 | 130
eq. ineq. range | eq. ineq. range
linear: 0 52 0 | 0 52 0
quadratic: 0 78 0 | 0 78 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 13 104 | 13 104
quadratic: 13 468 273 | 13 468 273
total: 13 572 273 | 13 572 273
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.47707e+06 14401.0 0.166195 0.030
1 -2.26506e+06 4169.30 0.965946 0.031
2 -2.42640e+06 1068.55 2.18285 0.032
3 -2.42851e+06 309.861 2.56371 0.032
4 -2.42217e+06 211.140 2.69012 0.033
5 -2.41793e+06 166.044 2.73688 0.033
6 -2.41522e+06 139.636 2.76427 0.034
7 -2.41337e+06 117.480 2.78109 0.035
8 -2.41213e+06 106.345 2.79019 0.035
9 -2.41134e+06 94.2232 2.79510 0.036
10 -2.41056e+06 83.6854 2.80014 0.036
11 -2.41154e+06 87.0391 2.79196 0.037
12 -2.41177e+06 76.7426 2.79024 0.037
13 -2.41281e+06 55.7265 2.78149 0.038
14 -2.41456e+06 21.6990 2.76571 0.038
15 -2.41862e+06 31.4924 2.72643 0.039
16 -2.42001e+06 2.71057 2.71057 0.040
17 -2.42249e+06 17.2079 2.68177 0.040
18 -2.43024e+06 2.55984 2.55984 0.041
19 -2.43265e+06 2.48224 2.48224 0.041
20 -2.43284e+06 2.46570 3.19946 0.042
30 -2.41618e+06 2.10380 16.9443 0.050
40 -2.38005e+06 1.85691 26.5290 0.055
50 -1.89258e+06 8.52838 76.1391 0.060
60 -1.67016e+06 0.262945 89.7709 0.064
70 -1.43632e+06 64.1767 25.8866 0.070
80 -406908. 1.11210e-02 17.7552 0.075
90 -298248. 0.00000e+00 2.07183 0.079
100 -259616. 0.00000e+00 2.73540 0.084
110 -229454. 0.00000e+00 0.210249 0.088
120 -212184. 0.00000e+00 0.824945 0.093
130 -39569.3 0.00000e+00 22.6505 0.098
140 -1743.95 0.00000e+00 17.3926 0.103
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -121280. FCRD inf 0.110
Knitro deduced that the problem is non-convex.
31 32 -101273. FCRD inf 0.300
70 71 -98373.2 FCRD inf 0.408
70 71 -23852.3 LS inf 0.425
163 163 1954.50 FCRD inf 0.657
340 325 4854.13 FCRD inf 1.073
346 331 24861.7 FCRD inf 1.095
416 391 30660.9 FCRD inf 1.265
757 607 50668.5 FCRD inf 2.237
867 658 99382.5 FCRD inf 2.571
1042 713 108081. FCRD inf 3.170
7896 855 108081. inf 40.451
9264 938 108081. FCRD inf 47.175
15884 1009 108081. inf 82.586
16386 1032 108081. inf 84.903
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 1.08081406836112961e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16386 (671.536s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16780 (672.822s)
Total program time (secs) = 84.90565 (677.740 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 3 / 1 / 0.138s
Rounding heuristic = 378 / 16 / 1.206s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 18 / 6 / 0.275s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 108081.40683611296; optimality
gap Infinity; 16386 nodes; 16780 subproblem solves
Artelys Knitro 16.0.0: mip_multistart=1
mip_maxnodes=16384
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
datacheck 0
feastol 1e-06
feastol_abs 1e-06
findiff_numthreads 1
hessian_no_f 1
hessopt 1
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 42 | 42
bounds: lower upper range | lower upper range
0 0 42 | 0 0 42
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
28 0 14 | 28 0 14
Number of constraints: 147 | 147
eq. ineq. range | eq. ineq. range
linear: 0 56 0 | 0 56 0
quadratic: 0 91 0 | 0 91 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 14 112 | 14 112
quadratic: 14 546 315 | 14 546 315
total: 14 658 315 | 14 658 315
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [4e+02, 9e+02] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.43615e+06 14401.0 0.147938 0.020
1 -2.28474e+06 4169.33 0.935687 0.021
2 -2.45857e+06 1065.93 2.18384 0.021
3 -2.46060e+06 302.345 2.56566 0.022
4 -2.45284e+06 195.548 2.69730 0.023
5 -2.44834e+06 150.776 2.74373 0.023
6 -2.44555e+06 117.964 2.77136 0.024
7 -2.44344e+06 104.265 2.78716 0.025
8 -2.44230e+06 95.5991 2.79528 0.025
9 -2.44128e+06 86.1724 2.80190 0.026
10 -2.44082e+06 79.5361 2.80420 0.026
11 -2.44162e+06 81.0669 2.79810 0.027
12 -2.44169e+06 72.7681 2.79656 0.028
13 -2.44211e+06 61.4529 2.79224 0.028
14 -2.44307e+06 61.0703 2.78366 0.029
15 -2.44389e+06 57.8645 2.77816 0.030
16 -2.44459e+06 54.6550 2.77366 0.030
17 -2.44738e+06 85.7540 2.74999 0.034
18 -2.45079e+06 133.913 2.78977 0.035
19 -2.45331e+06 153.460 3.19698 0.036
20 -2.45604e+06 175.298 2.66331 0.036
30 -2.46578e+06 281.448 3.56960 0.044
40 -2.35207e+06 223.194 10.4373 0.051
50 -2.17742e+06 1.15763 8.11516 0.058
60 -1.70267e+06 0.353133 10.7827 0.063
70 -1.48107e+06 0.259413 5.09665 0.069
80 -1.09963e+06 2.92108e-02 16.2952 0.074
90 -719284. 16.9179 8.32178 0.079
100 -515044. 3.32305e-06 2.74269 0.084
110 -261805. 0.00000e+00 6.33684 0.089
120 -3411.72 0.00000e+00 1.26966 0.095
130 78821.8 0.00000e+00 0.523474 0.100
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -83261.4 FCRD inf 0.106
Knitro deduced that the problem is non-convex.
127 128 -80361.8 FCRD inf 0.542
174 173 -31647.8 FCRD inf 0.641
403 382 45772.7 FCRD inf 1.152
7817 902 45772.7 inf 41.650
13689 1134 68679.8 FCRD inf 74.494
15727 1143 68679.8 inf 86.380
16386 1151 68679.8 inf 90.415
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 6.86798476295596920e+04
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16386 (715.405s)
# of strong branching evaluations = 0 (0.000s)
# of function evaluations = 0 (0.000s)
# of gradient evaluations = 0 (0.000s)
# of hessian evaluations = 0 (0.000s)
# of hessian-vector evaluations = 0
# of subproblems processed = 16793 (716.481s)
Total program time (secs) = 90.41767 (721.780 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 2 / 0 / 0.120s
Rounding heuristic = 391 / 12 / 0.965s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 11 / 4 / 0.230s
===========================================================================
WARNING: Loading a SolverResults object with a warning status into
model.name="unknown";
- termination condition: maxIterations
- message from solver: Knitro 16.0.0\x3a MIP\x3a Node limit reached.
Integer feasible point found.; objective 68679.84762955969; optimality
gap Infinity; 16386 nodes; 16793 subproblem solvesreport_counts(field, layouts) machines segments covered net present value
--------------------------------------------------------
3 24 59.6% $5,678
4 27 62.4% $46,597
5 32 67.7% $159,137
6 35 70.5% $200,055
7 40 75.8% $312,595
best 8 43 78.6% $353,513
9 44 78.9% $322,811
10 47 80.4% $312,116
11 49 80.4% $252,706
12 51 79.8% $167,491
13 53 79.8% $108,081
14 57 81.0% $68,680
8 machines earn the most at $353,513
81.0% is the widest coverage, and it does not pay for itselfdraw_comparison(field, layouts)The layouts behind those two curves, in order:
draw_layouts(field, layouts)Conclusion
The best solution is the one with 8 machines.
Although cases with more than 8 machines cover a higher proportion of the field, they have increasingly higher initial and maintenance costs, so the extra machines are not worthwhile.
Note that, for some cases, it is possible to get higher objective function values by allowing machines with only 1 or 2 segments. But since machines with 1 or 2 segments make a loss, it doesn’t make sense to include them: removing those loss-making machines leads to solutions with fewer machines that are uniformly worse than the solutions we’ve found.