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,...,N\), the number of segments of machine \(i\) (including the built-in segment)
- \(x_i \in \mathbb{R}\), \(i=1,...,N\), the \(x\) position of machine \(i\)’s pivot
- \(y_i \in \mathbb{R}\), \(i=1,...,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,...,N, \qquad S_{\text{size}} \cdot s_i \le x_i \le W - S_{\text{size}} \cdot s_i \]
\[ \forall i=1,...,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,...,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.078
1 -2.16662e+06 4168.94 0.883468 0.078
2 -2.26549e+06 1092.99 2.17355 0.078
3 -2.26807e+06 339.753 2.54056 0.079
4 -2.26491e+06 260.932 2.65815 0.079
5 -2.26283e+06 218.536 2.70606 0.079
6 -2.26142e+06 192.766 2.73660 0.080
7 -2.26055e+06 169.998 2.75323 0.080
8 -2.26013e+06 152.644 2.76265 0.080
9 -2.25975e+06 137.853 2.77337 0.081
10 -2.25951e+06 123.626 2.78079 0.081
11 -2.26022e+06 128.740 2.76929 0.081
12 -2.26036e+06 110.239 2.76954 0.081
13 -2.26062e+06 100.133 2.76746 0.082
14 -2.26147e+06 97.2033 2.75282 0.082
15 -2.26227e+06 86.6805 2.73710 0.082
16 -2.26340e+06 82.5117 2.71494 0.083
17 -2.26488e+06 68.6615 2.68155 0.083
18 -2.26605e+06 64.0655 2.65265 0.083
19 -2.26688e+06 55.3387 2.62733 0.084
20 -2.26779e+06 45.5852 2.59725 0.084
30 -2.23557e+06 9.53453 4.36023 0.087
40 -1.65424e+06 232.595 4.82700 0.090
50 -1.11012e+06 152.262 9.92205 0.093
60 -747654. 0.00000e+00 18.6515 0.095
70 -366752. 0.00000e+00 32.0751 0.098
80 -47698.0 0.00000e+00 1.38662 0.103
90 194786. 0.00000e+00 11.4787 0.106
100 224245. 0.00000e+00 2.09363e-03 0.108
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.114
1 2 26723.6 LS inf 0.118
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.148
31 31 201572. FCRD inf 0.182
39 39 276093. LS inf 0.189
78 59 324807. FCRD inf 0.232
586 234 353513. FCRD inf 0.776
7893 466 353513. inf 13.467
15825 538 353513. inf 28.423
16384 543 353513. inf 29.348
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 (229.188s)
# 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 (229.894s)
Total program time (secs) = 29.35116 (233.350 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.053s
Rounding heuristic = 235 / 11 / 0.659s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.086s
===========================================================================
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.083
1 -2.06819e+06 4167.22 0.842228 0.084
2 -2.10427e+06 1234.37 3.39503 0.084
3 -2.10698e+06 111.217 1.26369 0.084
4 -2.10695e+06 59.7654 1.26369 0.084
5 -2.10642e+06 92.8391 6.41785 0.084
6 -2.09065e+06 13.1853 2.33209 0.084
7 -2.08488e+06 3.70580 2.26512 0.085
8 -2.04651e+06 2.10497 3.51711 0.085
9 -1.97529e+06 1.99335 5.37828 0.085
10 -1.90748e+06 1.92130 6.61155 0.085
11 -1.90118e+06 1.84598 6.68489 0.085
12 -1.79043e+06 0.00000e+00 25.4903 0.085
13 -1.88553e+06 0.00000e+00 20.5534 0.086
14 -1.83404e+06 0.00000e+00 20.7001 0.086
15 -1.88170e+06 0.00000e+00 23.5012 0.086
16 -1.79059e+06 0.00000e+00 26.2563 0.086
17 -1.63380e+06 1097.77 28.0065 0.086
18 -1.38461e+06 17.6110 8.43785 0.087
19 -1.09667e+06 618.684 10.7709 0.087
20 -849069. 303.318 23.1336 0.087
30 -1493.85 0.00000e+00 17.7717 0.089
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 1 5678.31 LEAF inf 0.091
200 0 5678.31 5678.31 0.00% 0.717
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.674s)
# 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.674s)
Total program time (secs) = 0.71703 (0.670 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.009s
===========================================================================
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.073
1 -2.08787e+06 4168.14 0.807571 0.073
2 -2.13661e+06 1170.59 1.70845 0.074
3 -2.13934e+06 412.886 2.46895 0.074
4 -2.13865e+06 315.701 2.53609 0.074
5 -2.13823e+06 268.085 2.56761 0.074
6 -2.13791e+06 232.825 2.58594 0.074
7 -2.13772e+06 200.157 2.59659 0.074
8 -2.13774e+06 170.926 2.59645 0.074
9 -2.13788e+06 141.808 2.58998 0.075
10 -2.13823e+06 119.556 2.57123 0.075
11 -2.13883e+06 23.7446 2.53085 0.075
12 -2.13910e+06 2.50803 2.50803 0.075
13 -2.13961e+06 52.0198 1.67954 0.075
14 -2.13700e+06 55.2317 8.91996 0.075
15 -2.13410e+06 20.6321 6.36662 0.075
16 -2.12915e+06 36.5047 5.57905 0.075
17 -2.11475e+06 16.0126 4.18197 0.076
18 -2.05463e+06 1.93271 4.66114 0.076
19 -1.97220e+06 1.87812 6.75993 0.076
20 -1.81578e+06 1.82578 9.63717 0.076
30 -393714. 0.00000e+00 16.7042 0.077
40 20296.1 0.00000e+00 6.03313 0.078
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -56630.4 FCRD inf 0.083
3 4 43697.2 FCRD inf 0.090
Knitro deduced that the problem is non-convex.
13 10 46596.8 FCRD inf 0.110
6438 5 46596.8 inf 4.308
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 (26.885s)
# 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 (26.997s)
Total program time (secs) = 4.75536 (28.064 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.010s
Rounding heuristic = 32 / 6 / 0.085s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 4 / 0.017s
===========================================================================
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.079
1 -2.10756e+06 4168.43 0.812609 0.079
2 -2.16887e+06 1137.06 3.43957 0.080
3 -2.17160e+06 400.918 2.49868 0.080
4 -2.17061e+06 296.328 2.57022 0.080
5 -2.17028e+06 262.835 2.59699 0.080
6 -2.17000e+06 235.623 2.61645 0.080
7 -2.16973e+06 210.443 2.63277 0.080
8 -2.16955e+06 181.069 2.64461 0.081
9 -2.16965e+06 172.926 2.64238 0.081
10 -2.16971e+06 154.353 2.64316 0.081
11 -2.16997e+06 160.791 2.63243 0.081
12 -2.17021e+06 151.746 2.62253 0.081
13 -2.17034e+06 132.233 2.61898 0.081
14 -2.17108e+06 132.136 2.57786 0.082
15 -2.17123e+06 131.574 2.56734 0.082
16 -2.17148e+06 130.268 2.54818 0.082
17 -2.17118e+06 118.390 2.53168 0.082
18 -2.16638e+06 88.2926 2.50191 0.082
19 -2.16220e+06 80.8362 2.47693 0.082
20 -2.11676e+06 54.5914 3.93852 0.083
30 -1.66705e+06 511.526 6.17690 0.084
40 -747510. 0.00000e+00 56.5714 0.085
50 -457676. 0.00000e+00 11.3599 0.087
60 4426.14 0.00000e+00 30.8073 0.088
70 198100. 0.00000e+00 7.91531e-05 0.089
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -15711.9 FCRD inf 0.093
Knitro deduced that the problem is non-convex.
5 6 159137. FP inf 0.108
29 19 159137. FCRD inf 0.133
48 27 159137. FCRD inf 0.150
7933 95 159137. inf 6.062
15931 114 159137. inf 11.483
16387 115 159137. inf 11.756
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 (89.842s)
# 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 (90.263s)
Total program time (secs) = 11.75758 (92.899 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.412s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 10 / 5 / 0.032s
===========================================================================
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.076
1 -2.12725e+06 4168.71 0.825003 0.076
2 -2.20109e+06 1116.69 2.55192 0.076
3 -2.20372e+06 380.694 2.52326 0.077
4 -2.20162e+06 301.184 2.63173 0.077
5 -2.20027e+06 253.939 2.67807 0.077
6 -2.19910e+06 225.481 2.71462 0.077
7 -2.19822e+06 197.827 2.73975 0.077
8 -2.19798e+06 157.203 2.74807 0.078
9 -2.19794e+06 116.356 2.75150 0.078
10 -2.20015e+06 117.185 2.69775 0.078
11 -2.20058e+06 94.9885 2.68577 0.078
12 -2.20151e+06 69.9709 2.65798 0.078
13 -2.20216e+06 13.0110 2.63593 0.079
14 -2.20472e+06 7.96774 2.48351 0.079
15 -2.20438e+06 9.23421 4.46614 0.079
16 -2.20397e+06 4.37353 5.31762 0.079
17 -2.19688e+06 99.5102 22.9065 0.079
18 -2.19168e+06 23.3763 2.59914 0.080
19 -2.18321e+06 83.7613 4.79058 0.080
20 -2.16916e+06 25.8680 2.47774 0.080
30 -1.61086e+06 363.544 49.1107 0.081
40 -515446. 0.00000e+00 9.46295 0.083
50 -189972. 0.00000e+00 1.58248 0.085
60 103406. 0.00000e+00 8.91541 0.086
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 48113.8 FCRD inf 0.092
Knitro deduced that the problem is non-convex.
15 16 148441. FCRD inf 0.130
54 47 200055. FCRD inf 0.196
7853 187 200055. inf 8.056
15814 246 200055. inf 16.239
16386 248 200055. inf 16.782
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 (128.914s)
# 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 (129.580s)
Total program time (secs) = 16.78404 (132.254 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.004s
Rounding heuristic = 221 / 10 / 0.687s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 5 / 0.039s
===========================================================================
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.080
1 -2.14694e+06 4168.80 0.853542 0.081
2 -2.23330e+06 1102.75 2.16985 0.081
3 -2.23585e+06 338.041 2.53484 0.081
4 -2.23247e+06 205.204 2.66089 0.081
5 -2.23059e+06 150.239 2.70685 0.081
6 -2.22955e+06 123.198 2.72925 0.082
7 -2.22899e+06 102.116 2.74276 0.082
8 -2.22865e+06 80.7539 2.75485 0.082
9 -2.22870e+06 65.5838 2.75857 0.082
10 -2.22907e+06 50.7054 2.75526 0.083
11 -2.23189e+06 37.6813 2.69621 0.083
12 -2.23242e+06 23.0712 2.68541 0.083
13 -2.23356e+06 49.2455 2.65545 0.083
14 -2.23677e+06 37.1895 2.52062 0.083
15 -2.23677e+06 32.3409 7.56834 0.084
16 -2.23428e+06 26.7500 3.22402 0.084
17 -2.22477e+06 50.4409 2.30554 0.084
18 -2.20441e+06 14.6173 2.29534 0.084
19 -2.18891e+06 13.1769 2.79701 0.085
20 -2.11495e+06 11.9943 4.69835 0.085
30 -1.06835e+06 0.00000e+00 9.43860 0.087
40 -570241. 659.182 5.93091 0.089
50 -180137. 0.00000e+00 9.54394 0.091
60 69174.2 0.00000e+00 3.32023 0.093
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -11295.3 FCRD inf 0.098
Knitro deduced that the problem is non-convex.
3 4 66125.2 FCRD inf 0.117
7 8 140646. LS inf 0.132
13 14 169352. FCRD inf 0.144
28 29 189360. FCRD inf 0.174
36 37 240974. FCRD inf 0.188
146 114 312595. FCRD inf 0.283
7846 218 312595. inf 9.067
15592 289 312595. inf 18.694
16388 295 312595. inf 19.684
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 (151.692s)
# 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 (152.257s)
Total program time (secs) = 19.68637 (155.141 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.053s
Rounding heuristic = 178 / 15 / 0.517s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.072s
===========================================================================
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.067
1 -2.16662e+06 4168.94 0.883468 0.067
2 -2.26549e+06 1092.99 2.17355 0.067
3 -2.26807e+06 339.753 2.54056 0.068
4 -2.26491e+06 260.932 2.65815 0.068
5 -2.26283e+06 218.536 2.70606 0.068
6 -2.26142e+06 192.766 2.73660 0.068
7 -2.26055e+06 169.998 2.75323 0.069
8 -2.26013e+06 152.644 2.76265 0.069
9 -2.25975e+06 137.853 2.77337 0.069
10 -2.25951e+06 123.626 2.78079 0.070
11 -2.26022e+06 128.740 2.76929 0.070
12 -2.26036e+06 110.239 2.76954 0.070
13 -2.26062e+06 100.133 2.76746 0.071
14 -2.26147e+06 97.2033 2.75282 0.071
15 -2.26227e+06 86.6805 2.73710 0.071
16 -2.26340e+06 82.5117 2.71494 0.072
17 -2.26488e+06 68.6615 2.68155 0.072
18 -2.26605e+06 64.0655 2.65265 0.072
19 -2.26688e+06 55.3387 2.62733 0.073
20 -2.26779e+06 45.5852 2.59725 0.073
30 -2.23557e+06 9.53453 4.36023 0.076
40 -1.65424e+06 232.595 4.82700 0.079
50 -1.11012e+06 152.262 9.92205 0.081
60 -747654. 0.00000e+00 18.6515 0.084
70 -366752. 0.00000e+00 32.0751 0.086
80 -47698.0 0.00000e+00 1.38662 0.089
90 194786. 0.00000e+00 11.4787 0.091
100 224245. 0.00000e+00 2.09363e-03 0.093
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.099
1 2 26723.6 LS inf 0.108
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.143
31 31 201572. FCRD inf 0.187
39 39 276093. LS inf 0.197
78 59 324807. FCRD inf 0.243
586 234 353513. FCRD inf 0.803
7893 466 353513. inf 13.109
15825 538 353513. inf 27.872
16384 543 353513. inf 28.791
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 (224.744s)
# 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 (225.507s)
Total program time (secs) = 28.79286 (228.873 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.070s
Rounding heuristic = 235 / 11 / 0.691s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.093s
===========================================================================
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.079
1 -2.18631e+06 4169.00 0.972220 0.080
2 -2.29768e+06 1085.58 2.17634 0.080
3 -2.30019e+06 332.058 2.54598 0.080
4 -2.29609e+06 208.243 2.66660 0.081
5 -2.29362e+06 154.106 2.71494 0.081
6 -2.29202e+06 129.462 2.74536 0.081
7 -2.29101e+06 114.596 2.76314 0.082
8 -2.29033e+06 94.6734 2.77424 0.082
9 -2.29020e+06 58.7190 2.77658 0.083
10 -2.29405e+06 74.2433 2.71926 0.083
11 -2.29449e+06 58.6296 2.71225 0.083
12 -2.29534e+06 41.7538 2.69742 0.084
13 -2.29655e+06 2.67403 2.67403 0.084
14 -2.29757e+06 9.85655 2.65300 0.084
15 -2.29832e+06 14.5454 2.63608 0.085
16 -2.29907e+06 18.9549 2.61714 0.085
17 -2.29986e+06 19.1783 2.59476 0.085
18 -2.30040e+06 18.9224 2.57703 0.086
19 -2.30103e+06 68.2573 2.55290 0.088
20 -2.30138e+06 40.6419 2.53644 0.089
30 -2.27459e+06 1.94848 25.0990 0.092
40 -2.21166e+06 1.65880 40.6006 0.095
50 -1.16443e+06 1.69438e-02 7.01353 0.099
60 -292557. 0.00000e+00 7.57059 0.102
70 -92475.1 0.00000e+00 13.7865 0.104
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -204634. FCRD inf 0.109
Knitro deduced that the problem is non-convex.
3 4 -130114. FP inf 0.141
15 16 -9778.33 FCRD inf 0.183
22 23 271197. FCRD inf 0.205
111 71 317011. FCRD inf 0.345
271 134 322811. FCRD inf 0.548
7227 484 322811. inf 17.673
14604 686 322811. inf 34.156
16388 719 322811. inf 37.934
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 (297.561s)
# 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 (298.360s)
Total program time (secs) = 37.93613 (301.639 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.005s
Rounding heuristic = 298 / 14 / 0.821s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 12 / 5 / 0.098s
===========================================================================
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.092
1 -2.20600e+06 4169.18 0.947036 0.093
2 -2.32986e+06 1080.05 2.17851 0.093
3 -2.33210e+06 320.093 2.55558 0.093
4 -2.32617e+06 247.255 2.69173 0.094
5 -2.32286e+06 210.928 2.74728 0.095
6 -2.32054e+06 189.619 2.77817 0.095
7 -2.31899e+06 171.477 2.79361 0.096
8 -2.31814e+06 154.914 2.79851 0.096
9 -2.31782e+06 130.244 2.79963 0.097
10 -2.31802e+06 115.010 2.79937 0.097
11 -2.31920e+06 120.375 2.78645 0.098
12 -2.31894e+06 103.102 2.79148 0.099
13 -2.31914e+06 93.7453 2.79123 0.099
14 -2.31954e+06 85.7147 2.78857 0.100
15 -2.32020e+06 77.5530 2.78276 0.100
16 -2.32126e+06 70.6128 2.77192 0.101
17 -2.32234e+06 63.0897 2.76009 0.101
18 -2.32347e+06 57.5711 2.74661 0.102
19 -2.32484e+06 51.8753 2.72906 0.102
20 -2.32658e+06 49.5184 2.70419 0.103
30 -2.33494e+06 17.9013 2.49491 0.107
40 -1.85422e+06 0.465946 72.0767 0.113
50 -343240. 0.00000e+00 8.51260 0.118
60 -5174.53 0.00000e+00 6.30000 0.122
70 83941.5 0.00000e+00 2.69830 0.126
80 107140. 1.45519e-11 9.46702e-13 0.129
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 59846.6 FCRD inf 0.133
Knitro deduced that the problem is non-convex.
23 24 76954.6 FCRD inf 0.222
38 39 102761. FCRD inf 0.249
46 47 160174. FCRD inf 0.269
108 100 208888. FCRD inf 0.404
147 135 208888. FCRD inf 0.478
171 152 208888. FCRD inf 0.517
233 202 231795. FCRD inf 0.639
4786 609 260502. FCRD inf 15.742
6730 614 260502. inf 22.738
12628 967 312116. FCRD inf 40.686
13936 998 312116. inf 44.133
16391 1045 312116. inf 50.527
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 (397.297s)
# 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 (398.620s)
Total program time (secs) = 50.53165 (401.837 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.086s
Rounding heuristic = 400 / 16 / 1.307s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 5 / 0.132s
===========================================================================
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.083
1 -2.22568e+06 4169.14 1.24444 0.084
2 -2.36204e+06 1075.25 2.18026 0.085
3 -2.36435e+06 316.479 2.55796 0.086
4 -2.35903e+06 195.818 2.68101 0.087
5 -2.35599e+06 157.615 2.72959 0.089
6 -2.35425e+06 127.053 2.75960 0.090
7 -2.35352e+06 96.8355 2.77302 0.091
8 -2.35371e+06 57.8037 2.77449 0.092
9 -2.35922e+06 105.574 2.70194 0.093
10 -2.35970e+06 76.7210 2.69532 0.094
11 -2.36024e+06 5.71021 2.68824 0.095
12 -2.36218e+06 2.65386 2.65386 0.096
13 -2.36683e+06 2.51510 4.55570 0.096
14 -2.35529e+06 2.48982 34.7539 0.097
15 -2.35419e+06 21.2098 5.68532 0.098
16 -2.35044e+06 29.0164 4.85545 0.098
17 -2.34107e+06 61.5293 2.53126 0.099
18 -2.32874e+06 47.4339 2.70344 0.100
19 -2.29618e+06 31.7195 3.99136 0.100
20 -2.23371e+06 31.6614 5.45247 0.101
30 -2.15081e+06 1.21544 61.5441 0.110
40 -1.78506e+06 0.372527 85.7464 0.115
50 -1.14209e+06 0.00000e+00 8.44370 0.121
60 -260542. 0.00000e+00 5.74022 0.125
70 -152791. 0.00000e+00 0.443641 0.128
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -223125. FCRD inf 0.136
Knitro deduced that the problem is non-convex.
3 4 -131496. FCRD inf 0.185
7 8 -102790. LS inf 0.209
35 36 46251.9 FCRD inf 0.301
60 58 169487. FCRD inf 0.353
217 180 175286. FCRD inf 0.715
225 185 201093. FCRD inf 0.729
610 322 224000. FCRD inf 1.617
1402 506 249807. FCRD inf 3.471
1416 511 252706. FCRD inf 3.503
5991 750 252706. FCRD inf 20.602
6762 769 252706. inf 23.493
7258 805 252706. FCRD inf 25.186
13699 1042 252706. inf 47.727
16384 1145 252706. inf 56.922
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 (447.763s)
# 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 (449.082s)
Total program time (secs) = 56.92636 (452.795 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.070s
Rounding heuristic = 376 / 17 / 1.255s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 18 / 6 / 0.184s
===========================================================================
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.104
1 -2.24537e+06 4169.21 0.909667 0.105
2 -2.39422e+06 1071.62 2.18168 0.106
3 -2.39643e+06 312.026 2.56144 0.107
4 -2.39125e+06 218.641 2.68525 0.107
5 -2.38771e+06 175.826 2.73442 0.108
6 -2.38589e+06 150.937 2.75803 0.109
7 -2.38474e+06 130.566 2.76823 0.110
8 -2.38390e+06 114.545 2.77471 0.110
9 -2.38326e+06 102.220 2.78188 0.111
10 -2.38316e+06 91.6032 2.78313 0.112
11 -2.38388e+06 95.5451 2.77599 0.112
12 -2.38371e+06 85.8699 2.77754 0.113
13 -2.38376e+06 77.1747 2.77662 0.114
14 -2.38383e+06 69.3538 2.77515 0.114
15 -2.38403e+06 62.3258 2.77216 0.115
16 -2.38433e+06 56.6964 2.76791 0.116
17 -2.38480e+06 51.6220 2.76186 0.117
18 -2.38547e+06 47.2041 2.75444 0.117
19 -2.38752e+06 48.7163 2.73194 0.126
20 -2.38905e+06 17.6810 2.71391 0.126
30 -2.38111e+06 8.95845 6.32155 0.135
40 -2.32117e+06 2.10445 93.9809 0.145
50 -2.34003e+06 1.81585 34.9506 0.152
60 -2.15105e+06 1.14059 54.6783 0.163
70 -1.19408e+06 0.00000e+00 8.04973 0.170
80 -353016. 0.00000e+00 0.126411 0.176
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -434475. FCRD inf 0.182
Knitro deduced that the problem is non-convex.
2 3 38456.4 FCRD inf 0.224
153 127 64263.2 FCRD inf 0.769
279 236 138784. FCRD inf 1.123
2971 772 141684. FCRD inf 10.663
6974 795 141684. inf 30.152
9090 848 167491. FCRD inf 41.035
14213 1095 167491. inf 65.579
16388 1184 167491. inf 75.435
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 (594.862s)
# 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 (596.368s)
Total program time (secs) = 75.43916 (600.951 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.166s
Rounding heuristic = 435 / 11 / 1.371s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 12 / 4 / 0.173s
===========================================================================
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.094
1 -2.26506e+06 4169.30 0.965946 0.095
2 -2.42640e+06 1068.55 2.18285 0.096
3 -2.42851e+06 309.861 2.56371 0.096
4 -2.42217e+06 211.140 2.69012 0.097
5 -2.41793e+06 166.044 2.73688 0.098
6 -2.41522e+06 139.636 2.76427 0.098
7 -2.41337e+06 117.480 2.78109 0.099
8 -2.41213e+06 106.345 2.79019 0.099
9 -2.41134e+06 94.2232 2.79510 0.100
10 -2.41056e+06 83.6854 2.80014 0.100
11 -2.41154e+06 87.0391 2.79196 0.101
12 -2.41177e+06 76.7426 2.79024 0.102
13 -2.41281e+06 55.7265 2.78149 0.103
14 -2.41456e+06 21.6990 2.76571 0.103
15 -2.41862e+06 31.4924 2.72643 0.104
16 -2.42001e+06 2.71057 2.71057 0.104
17 -2.42249e+06 17.2079 2.68177 0.105
18 -2.43024e+06 2.55984 2.55984 0.105
19 -2.43265e+06 2.48224 2.48224 0.106
20 -2.43284e+06 2.46570 3.19946 0.106
30 -2.41618e+06 2.10380 16.9443 0.115
40 -2.38005e+06 1.85691 26.5290 0.120
50 -1.89258e+06 8.52838 76.1391 0.126
60 -1.67016e+06 0.262945 89.7709 0.130
70 -1.43632e+06 64.1767 25.8866 0.136
80 -406908. 1.11210e-02 17.7552 0.141
90 -298248. 0.00000e+00 2.07183 0.145
100 -259616. 0.00000e+00 2.73540 0.150
110 -229454. 0.00000e+00 0.210249 0.154
120 -212184. 0.00000e+00 0.824945 0.159
130 -39569.3 0.00000e+00 22.6505 0.167
140 -1743.95 0.00000e+00 17.3926 0.175
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -121280. FCRD inf 0.185
Knitro deduced that the problem is non-convex.
31 32 -101273. FCRD inf 0.377
70 71 -98373.2 FCRD inf 0.521
70 71 -23852.3 LS inf 0.547
163 163 1954.50 FCRD inf 0.846
340 325 4854.13 FCRD inf 1.427
346 331 24861.7 FCRD inf 1.463
416 391 30660.9 FCRD inf 1.683
757 607 50668.5 FCRD inf 2.842
867 658 99382.5 FCRD inf 3.230
1042 713 108081. FCRD inf 3.847
7896 855 108081. inf 46.727
9264 938 108081. FCRD inf 53.757
15884 1009 108081. inf 91.492
16386 1032 108081. inf 93.908
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 (742.239s)
# 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 (743.713s)
Total program time (secs) = 93.91368 (745.948 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.141s
Rounding heuristic = 378 / 16 / 1.403s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 18 / 6 / 0.263s
===========================================================================
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.091
1 -2.28474e+06 4169.33 0.935687 0.092
2 -2.45857e+06 1065.93 2.18384 0.092
3 -2.46060e+06 302.345 2.56566 0.093
4 -2.45284e+06 195.548 2.69730 0.093
5 -2.44834e+06 150.776 2.74373 0.094
6 -2.44555e+06 117.964 2.77136 0.095
7 -2.44344e+06 104.265 2.78716 0.095
8 -2.44230e+06 95.5991 2.79528 0.096
9 -2.44128e+06 86.1724 2.80190 0.097
10 -2.44082e+06 79.5361 2.80420 0.097
11 -2.44162e+06 81.0669 2.79810 0.098
12 -2.44169e+06 72.7681 2.79656 0.099
13 -2.44211e+06 61.4529 2.79224 0.099
14 -2.44307e+06 61.0703 2.78366 0.100
15 -2.44389e+06 57.8645 2.77816 0.100
16 -2.44459e+06 54.6550 2.77366 0.101
17 -2.44738e+06 85.7540 2.74999 0.105
18 -2.45079e+06 133.913 2.78977 0.106
19 -2.45331e+06 153.460 3.19698 0.106
20 -2.45604e+06 175.298 2.66331 0.107
30 -2.46578e+06 281.448 3.56960 0.115
40 -2.35207e+06 223.194 10.4373 0.122
50 -2.17742e+06 1.15763 8.11516 0.129
60 -1.70267e+06 0.353133 10.7827 0.134
70 -1.48107e+06 0.259413 5.09665 0.140
80 -1.09963e+06 2.92108e-02 16.2952 0.145
90 -719284. 16.9179 8.32178 0.150
100 -515044. 3.32305e-06 2.74269 0.155
110 -261805. 0.00000e+00 6.33684 0.160
120 -3411.72 0.00000e+00 1.26966 0.166
130 78821.8 0.00000e+00 0.523474 0.171
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -83261.4 FCRD inf 0.178
Knitro deduced that the problem is non-convex.
127 128 -80361.8 FCRD inf 0.556
174 173 -31647.8 FCRD inf 0.661
403 382 45772.7 FCRD inf 1.209
7817 902 45772.7 inf 47.211
13689 1134 68679.8 FCRD inf 89.655
15727 1143 68679.8 inf 104.210
16386 1151 68679.8 inf 109.820
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 (868.676s)
# 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 (869.878s)
Total program time (secs) = 109.82339 (873.708 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.091s
Rounding heuristic = 391 / 12 / 1.165s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 11 / 4 / 0.215s
===========================================================================
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.