Base.@kwdef struct Field
width::Float64
length::Float64
segment_length::Float64
min_segments::Int
max_segments::Int
machine_cost::Float64
segment_cost::Float64
operating_cost::Float64
margin::Float64
end
area(field::Field) = field.width * field.length
struct Layout
npv::Float64
x::Vector{Float64}
y::Vector{Float64}
segments::Vector{Float64}
end
num_machines(layout::Layout) = length(layout.segments)
radius(field::Field, segments) = segments * field.segment_length
function covered_area(field::Field, segments)
return sum(pi * radius(field, s)^2 for s in segments)
end
function coverage(field::Field, layout::Layout)
return covered_area(field, layout.segments) / area(field)
end
function net_present_value(field::Field, segments)
margin = covered_area(field, segments) * field.margin
machines_cost = length(segments) * field.machine_cost
segments_cost = sum(s - 1 for s in segments) * field.segment_cost
return margin - machines_cost - segments_cost - field.operating_cost
endPivot 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,
)
function grid_layout(field::Field; segments=5)
reach = radius(field, segments)
columns = [reach + k * (field.width - 2reach) / 3 for k in 0:3]
rows = [reach, field.length - reach]
counts = fill(float(segments), 4 * length(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)
endA 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
using JuMP
using KNITROmaximize_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 the @objective and @constraint macros 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.
function maximize_npv(field::Field, num_machines; multistart=1, max_nodes=2^14)
reach = radius(field, field.min_segments)
model = Model(KNITRO.Optimizer)
set_attribute(model, "mip_multistart", multistart)
set_attribute(model, "mip_maxnodes", max_nodes)
@variable(model, field.min_segments <= s[1:num_machines] <= field.max_segments, Int)
@variable(model, reach <= x[1:num_machines] <= field.width - reach)
@variable(model, reach <= y[1:num_machines] <= field.length - reach)
area = sum(pi * (s[i] * field.segment_length)^2 for i in 1:num_machines)
margin = field.margin * area
machines_cost = num_machines * field.machine_cost
segments_cost = field.segment_cost * sum(s[i] - 1 for i in 1:num_machines)
objective = margin - machines_cost - segments_cost - field.operating_cost
@objective(model, Max, objective)
for i in 1:num_machines
@constraint(model, x[i] >= s[i] * field.segment_length)
@constraint(model, x[i] <= field.width - s[i] * field.segment_length)
@constraint(model, y[i] >= s[i] * field.segment_length)
@constraint(model, y[i] <= field.length - s[i] * field.segment_length)
end
for i in 1:num_machines, j in (i + 1):num_machines
radii = (s[i] + s[j]) * field.segment_length
@constraint(model, (x[i] - x[j])^2 + (y[i] - y[j])^2 >= radii^2)
end
optimize!(model)
npv = objective_value(model)
return Layout(npv, value.(x), value.(y), value.(s))
endSolving 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);=======================================
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.02s.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.047
1 -2.16662e+06 4168.94 0.883468 0.048
2 -2.26549e+06 1092.99 2.17355 0.048
3 -2.26807e+06 339.753 2.54056 0.048
4 -2.26491e+06 260.932 2.65815 0.049
5 -2.26283e+06 218.536 2.70606 0.049
6 -2.26142e+06 192.766 2.73660 0.049
7 -2.26055e+06 169.998 2.75323 0.049
8 -2.26013e+06 152.644 2.76265 0.050
9 -2.25975e+06 137.853 2.77337 0.050
10 -2.25951e+06 123.626 2.78079 0.050
11 -2.26022e+06 128.740 2.76929 0.051
12 -2.26036e+06 110.239 2.76954 0.051
13 -2.26062e+06 100.133 2.76746 0.051
14 -2.26147e+06 97.2033 2.75282 0.051
15 -2.26227e+06 86.6805 2.73710 0.052
16 -2.26340e+06 82.5117 2.71494 0.052
17 -2.26488e+06 68.6615 2.68155 0.052
18 -2.26605e+06 64.0655 2.65265 0.053
19 -2.26688e+06 55.3387 2.62733 0.053
20 -2.26779e+06 45.5852 2.59725 0.053
30 -2.23557e+06 9.53453 4.36023 0.056
40 -1.65424e+06 232.596 4.82700 0.059
50 -1.11012e+06 152.262 9.92209 0.061
60 -747689. 0.00000e+00 18.6551 0.063
70 -416266. 0.00000e+00 27.4401 0.065
80 -116079. 0.00000e+00 2.52873 0.067
90 150443. 0.00000e+00 7.31508 0.070
100 221380. 0.00000e+00 0.346355 0.072
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.078
1 2 26723.6 LS inf 0.086
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.114
31 31 201572. FCRD inf 0.165
39 39 276093. LS inf 0.172
76 61 324807. FCRD inf 0.217
3189 438 353513. FCRD inf 4.424
7913 509 353513. inf 12.091
15897 621 353513. inf 23.582
16385 630 353513. inf 24.271
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.53513363574207295e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16385 (189.333s)
# 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 = 16709 (189.798s)
Total program time (secs) = 24.27213 (193.206 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 = 5 / 1 / 0.089s
Rounding heuristic = 297 / 9 / 0.395s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.103s
===========================================================================
Show 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 4 80m 829.1 83.9 20,106 5.0%
2 5 100m 272.7 101.2 31,416 7.8%
3 7 140m 774.4 302.6 61,575 15.2%
4 3 60m 431.7 61.8 11,310 2.8%
5 4 80m 83.1 84.1 20,106 5.0%
6 7 140m 140.0 302.6 61,575 15.2%
7 8 160m 460.6 282.6 80,425 19.9%
8 5 100m 645.7 100.0 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 = 3:14layouts = [maximize_npv(field, num_machines) for num_machines in counts];Show the full outputHide the full output
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.003
1 -2.06819e+06 4167.22 0.842228 0.003
2 -2.10427e+06 1234.37 3.39503 0.003
3 -2.10698e+06 111.217 1.26369 0.004
4 -2.10695e+06 59.7654 1.26369 0.004
5 -2.10642e+06 92.8391 6.41785 0.004
6 -2.09065e+06 13.1853 2.33209 0.004
7 -2.08488e+06 3.70580 2.26512 0.004
8 -2.04651e+06 2.10497 3.51711 0.004
9 -1.97529e+06 1.99335 5.37828 0.004
10 -1.90748e+06 1.92130 6.61155 0.004
11 -1.90118e+06 1.84598 6.68489 0.004
12 -1.79043e+06 0.00000e+00 25.4903 0.004
13 -1.84283e+06 0.00000e+00 17.3191 0.005
14 -1.76008e+06 0.00000e+00 16.1102 0.005
15 -1.67344e+06 0.00000e+00 12.6535 0.005
16 -1.43086e+06 0.00000e+00 12.8315 0.005
17 -1.25574e+06 0.00000e+00 9.64968 0.005
18 -1.25650e+06 0.00000e+00 9.64820 0.005
19 -1.24009e+06 0.00000e+00 9.66460 0.005
20 -1.17540e+06 311.235 5.56185 0.005
30 -338459. 0.00000e+00 16.7201 0.006
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 1 5678.31 LEAF inf 0.007
200 0 5678.31 5678.31 0.00% 0.581
EXIT: Optimal solution found (assuming convexity).
Final Statistics for MIP
------------------------
Final objective value = 5.67831437182379887e+03
Final bound value = 5.67831437182379887e+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.540s)
# 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.540s)
Total program time (secs) = 0.58071 (0.619 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.013s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.003
1 -2.08787e+06 4168.14 0.807571 0.003
2 -2.13661e+06 1170.59 1.70845 0.003
3 -2.13934e+06 412.886 2.46895 0.004
4 -2.13865e+06 315.701 2.53609 0.004
5 -2.13823e+06 268.085 2.56761 0.004
6 -2.13791e+06 232.825 2.58594 0.004
7 -2.13772e+06 200.157 2.59659 0.004
8 -2.13774e+06 170.926 2.59645 0.004
9 -2.13788e+06 141.808 2.58998 0.005
10 -2.13823e+06 119.556 2.57123 0.005
11 -2.13883e+06 23.7446 2.53085 0.005
12 -2.13910e+06 2.50803 2.50803 0.005
13 -2.13961e+06 52.0198 1.67954 0.005
14 -2.13700e+06 55.2317 8.91996 0.005
15 -2.13410e+06 20.6321 6.36662 0.006
16 -2.12915e+06 36.5047 5.57905 0.008
17 -2.11475e+06 16.0126 4.18197 0.008
18 -2.05463e+06 1.93271 4.66114 0.008
19 -1.97220e+06 1.87812 6.75993 0.009
20 -1.81578e+06 1.82578 9.63717 0.009
30 -393714. 0.00000e+00 16.7042 0.010
40 20328.8 0.00000e+00 6.04452 0.011
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -56630.4 FCRD inf 0.016
3 4 43697.2 FCRD inf 0.023
Knitro deduced that the problem is non-convex.
13 10 46596.8 FCRD inf 0.039
6241 6 46596.8 inf 3.407
EXIT: Satisfactory solution found.
Final Statistics for MIP
------------------------
Final objective value = 4.65968443674491718e+04
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 6462 (22.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 = 6502 (22.472s)
Total program time (secs) = 3.63969 (23.620 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 = 31 / 5 / 0.048s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 4 / 0.026s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.002
1 -2.10756e+06 4168.43 0.812609 0.002
2 -2.16887e+06 1137.06 3.43957 0.002
3 -2.17160e+06 400.918 2.49868 0.002
4 -2.17061e+06 296.328 2.57022 0.002
5 -2.17028e+06 262.835 2.59699 0.002
6 -2.17000e+06 235.623 2.61645 0.003
7 -2.16973e+06 210.443 2.63277 0.003
8 -2.16955e+06 181.069 2.64461 0.003
9 -2.16965e+06 172.926 2.64238 0.003
10 -2.16971e+06 154.353 2.64316 0.003
11 -2.16997e+06 160.791 2.63243 0.003
12 -2.17021e+06 151.746 2.62253 0.004
13 -2.17034e+06 132.233 2.61898 0.004
14 -2.17108e+06 132.136 2.57786 0.004
15 -2.17123e+06 131.574 2.56734 0.004
16 -2.17148e+06 130.268 2.54818 0.004
17 -2.17118e+06 118.390 2.53168 0.004
18 -2.16638e+06 88.2926 2.50191 0.005
19 -2.16220e+06 80.8362 2.47693 0.005
20 -2.11676e+06 54.5914 3.93852 0.005
30 -1.66705e+06 511.526 6.17690 0.006
40 -747510. 0.00000e+00 56.5714 0.008
50 -457676. 0.00000e+00 11.3599 0.009
60 4426.21 0.00000e+00 30.8074 0.010
70 198100. 0.00000e+00 7.92082e-05 0.011
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -15711.9 FCRD inf 0.015
Knitro deduced that the problem is non-convex.
3 4 58808.9 LS inf 0.019
7 8 159137. FP inf 0.025
7940 78 159137. inf 5.284
15939 96 159137. inf 10.138
16386 110 159137. inf 10.412
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 = 16386 (79.894s)
# 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 = 16537 (80.044s)
Total program time (secs) = 10.41343 (82.725 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.008s
Rounding heuristic = 141 / 7 / 0.151s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 5 / 0.021s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.001
1 -2.12725e+06 4168.71 0.825003 0.002
2 -2.20109e+06 1116.69 2.55192 0.002
3 -2.20372e+06 380.694 2.52326 0.002
4 -2.20162e+06 301.184 2.63173 0.002
5 -2.20027e+06 253.939 2.67807 0.002
6 -2.19910e+06 225.481 2.71462 0.003
7 -2.19822e+06 197.827 2.73975 0.003
8 -2.19798e+06 157.203 2.74807 0.003
9 -2.19794e+06 116.356 2.75150 0.003
10 -2.20015e+06 117.185 2.69775 0.003
11 -2.20058e+06 94.9885 2.68577 0.004
12 -2.20151e+06 69.9709 2.65798 0.004
13 -2.20216e+06 13.0110 2.63593 0.004
14 -2.20472e+06 7.96768 2.48351 0.004
15 -2.20438e+06 9.23417 4.46606 0.004
16 -2.20397e+06 4.37360 5.31754 0.005
17 -2.19688e+06 99.5042 22.9048 0.005
18 -2.19168e+06 23.3808 2.59920 0.005
19 -2.18320e+06 83.7849 4.79063 0.005
20 -2.16916e+06 25.8944 2.47750 0.005
30 -1.60652e+06 366.200 49.1476 0.007
40 -550290. 2.50862e-02 8.82375 0.008
50 -217677. 0.00000e+00 1.20785 0.010
60 105406. 0.00000e+00 1.24628 0.011
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 48113.8 FCRD inf 0.014
Knitro deduced that the problem is non-convex.
15 16 200055. FCRD inf 0.031
7865 180 200055. inf 6.577
15799 209 200055. inf 13.074
16390 212 200055. inf 13.529
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 2.00055103970828000e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16390 (104.878s)
# 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 = 16585 (105.063s)
Total program time (secs) = 13.53057 (107.944 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.001s
Rounding heuristic = 191 / 6 / 0.209s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 8 / 4 / 0.034s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.002
1 -2.14694e+06 4168.80 0.853542 0.002
2 -2.23330e+06 1102.75 2.16985 0.002
3 -2.23585e+06 338.041 2.53484 0.002
4 -2.23247e+06 205.204 2.66089 0.003
5 -2.23059e+06 150.239 2.70685 0.003
6 -2.22955e+06 123.198 2.72925 0.003
7 -2.22899e+06 102.116 2.74276 0.003
8 -2.22865e+06 80.7539 2.75485 0.003
9 -2.22870e+06 65.5838 2.75857 0.004
10 -2.22907e+06 50.7054 2.75526 0.004
11 -2.23189e+06 37.6813 2.69621 0.004
12 -2.23242e+06 23.0712 2.68541 0.004
13 -2.23356e+06 49.2455 2.65545 0.005
14 -2.23677e+06 37.1895 2.52062 0.005
15 -2.23677e+06 32.3409 7.56834 0.005
16 -2.23428e+06 26.7500 3.22402 0.005
17 -2.22477e+06 50.4409 2.30554 0.005
18 -2.20441e+06 14.6173 2.29534 0.006
19 -2.18891e+06 13.1769 2.79701 0.006
20 -2.11495e+06 11.9943 4.69835 0.006
30 -1.06835e+06 0.00000e+00 9.43860 0.008
40 -570242. 659.173 5.93090 0.010
50 -180114. 0.00000e+00 9.55136 0.012
60 73991.0 0.00000e+00 1.64354 0.014
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -11295.3 FCRD inf 0.017
Knitro deduced that the problem is non-convex.
3 4 66125.2 FCRD inf 0.027
7 8 140646. LS inf 0.033
13 14 169352. FCRD inf 0.038
28 29 189360. FCRD inf 0.051
36 37 240974. FCRD inf 0.057
114 91 312595. FCRD inf 0.108
6266 175 312595. FCRD inf 6.137
7840 202 312595. inf 7.780
15447 276 312595. inf 16.029
16387 281 312595. inf 17.072
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.12594833578581922e+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 (132.635s)
# 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 = 16576 (132.830s)
Total program time (secs) = 17.07387 (135.907 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.010s
Rounding heuristic = 181 / 23 / 0.206s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 6 / 0.060s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.002
1 -2.16662e+06 4168.94 0.883468 0.002
2 -2.26549e+06 1092.99 2.17355 0.002
3 -2.26807e+06 339.753 2.54056 0.003
4 -2.26491e+06 260.932 2.65815 0.003
5 -2.26283e+06 218.536 2.70606 0.003
6 -2.26142e+06 192.766 2.73660 0.003
7 -2.26055e+06 169.998 2.75323 0.004
8 -2.26013e+06 152.644 2.76265 0.004
9 -2.25975e+06 137.853 2.77337 0.004
10 -2.25951e+06 123.626 2.78079 0.005
11 -2.26022e+06 128.740 2.76929 0.005
12 -2.26036e+06 110.239 2.76954 0.005
13 -2.26062e+06 100.133 2.76746 0.005
14 -2.26147e+06 97.2033 2.75282 0.006
15 -2.26227e+06 86.6805 2.73710 0.006
16 -2.26340e+06 82.5117 2.71494 0.006
17 -2.26488e+06 68.6615 2.68155 0.007
18 -2.26605e+06 64.0655 2.65265 0.007
19 -2.26688e+06 55.3387 2.62733 0.007
20 -2.26779e+06 45.5852 2.59725 0.008
30 -2.23557e+06 9.53453 4.36023 0.011
40 -1.65424e+06 232.596 4.82700 0.013
50 -1.11012e+06 152.262 9.92209 0.015
60 -747689. 0.00000e+00 18.6551 0.017
70 -416266. 0.00000e+00 27.4401 0.020
80 -116079. 0.00000e+00 2.52873 0.022
90 150443. 0.00000e+00 7.31508 0.024
100 221380. 0.00000e+00 0.346355 0.027
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.030
1 2 26723.6 LS inf 0.033
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.049
31 31 201572. FCRD inf 0.074
39 39 276093. LS inf 0.078
76 61 324807. FCRD inf 0.115
3189 438 353513. FCRD inf 4.268
7913 509 353513. inf 11.947
15897 621 353513. inf 23.457
16385 630 353513. inf 24.149
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.53513363574207295e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16385 (189.007s)
# 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 = 16709 (189.399s)
Total program time (secs) = 24.15042 (192.766 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 = 5 / 1 / 0.071s
Rounding heuristic = 297 / 9 / 0.356s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.076s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.002
1 -2.18631e+06 4169.00 0.972220 0.002
2 -2.29768e+06 1085.58 2.17634 0.002
3 -2.30019e+06 332.058 2.54598 0.003
4 -2.29609e+06 208.243 2.66660 0.003
5 -2.29362e+06 154.106 2.71494 0.003
6 -2.29202e+06 129.462 2.74536 0.004
7 -2.29101e+06 114.596 2.76314 0.004
8 -2.29033e+06 94.6734 2.77424 0.004
9 -2.29020e+06 58.7190 2.77658 0.005
10 -2.29405e+06 74.2433 2.71926 0.005
11 -2.29449e+06 58.6296 2.71225 0.005
12 -2.29534e+06 41.7538 2.69742 0.006
13 -2.29655e+06 2.67403 2.67403 0.006
14 -2.29757e+06 9.85655 2.65300 0.006
15 -2.29832e+06 14.5454 2.63608 0.007
16 -2.29907e+06 18.9549 2.61714 0.007
17 -2.29986e+06 19.1783 2.59476 0.007
18 -2.30040e+06 18.9224 2.57703 0.008
19 -2.30103e+06 68.2573 2.55290 0.009
20 -2.30138e+06 40.6419 2.53644 0.010
30 -2.27459e+06 1.94848 25.0990 0.013
40 -2.21166e+06 1.65880 40.6006 0.016
50 -1.16443e+06 1.69438e-02 7.01353 0.019
60 -292577. 0.00000e+00 7.57071 0.022
70 -97670.5 0.00000e+00 9.10005 0.024
80 -11646.1 0.00000e+00 3.27807 0.027
90 47243.8 0.00000e+00 5.84846 0.030
100 79399.4 3.63798e-11 3.75157e-13 0.032
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -55592.7 FCRD inf 0.035
Knitro deduced that the problem is non-convex.
20 21 167970. FCRD inf 0.081
33 32 170869. FCRD inf 0.093
88 76 193777. FCRD inf 0.166
112 97 242491. FCRD inf 0.190
127 112 294104. FCRD inf 0.205
213 148 317011. FCRD inf 0.299
943 291 322811. FCRD inf 1.287
7843 548 322811. inf 15.935
15799 792 322811. inf 31.353
16390 807 322811. inf 32.482
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 = 16390 (255.435s)
# 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 = 16796 (255.900s)
Total program time (secs) = 32.48378 (259.471 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 / 0 / 0.035s
Rounding heuristic = 392 / 18 / 0.484s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 5 / 0.091s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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.002
1 -2.20600e+06 4169.18 0.947036 0.002
2 -2.32986e+06 1080.05 2.17851 0.003
3 -2.33210e+06 320.093 2.55558 0.003
4 -2.32617e+06 247.255 2.69173 0.003
5 -2.32286e+06 210.928 2.74728 0.004
6 -2.32054e+06 189.619 2.77817 0.004
7 -2.31899e+06 171.477 2.79361 0.004
8 -2.31814e+06 154.914 2.79851 0.005
9 -2.31782e+06 130.244 2.79963 0.005
10 -2.31802e+06 115.010 2.79937 0.006
11 -2.31920e+06 120.375 2.78645 0.006
12 -2.31894e+06 103.102 2.79148 0.006
13 -2.31914e+06 93.7453 2.79123 0.007
14 -2.31954e+06 85.7147 2.78857 0.007
15 -2.32020e+06 77.5530 2.78276 0.008
16 -2.32126e+06 70.6128 2.77192 0.008
17 -2.32234e+06 63.0898 2.76009 0.008
18 -2.32347e+06 57.5711 2.74661 0.009
19 -2.32484e+06 51.8753 2.72906 0.009
20 -2.32658e+06 49.5184 2.70419 0.010
30 -2.33494e+06 17.9013 2.49491 0.013
40 -1.85423e+06 0.465955 72.0763 0.018
50 -343246. 0.00000e+00 8.51261 0.021
60 -4306.30 0.00000e+00 6.35057 0.024
70 81006.6 0.00000e+00 1.19469 0.027
80 99440.7 6.87237e-11 1.00441e-08 0.030
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -192422. FCRD inf 0.033
1 2 -117901. LS inf 0.038
Knitro deduced that the problem is non-convex.
3 4 59846.6 DDRD inf 0.054
15 16 208888. FCRD inf 0.081
112 101 211788. FCRD inf 0.215
316 264 231795. FCRD inf 0.478
599 439 231795. FCRD inf 0.865
623 455 312116. FCRD inf 0.896
1906 545 332123. FCRD inf 3.363
2135 560 332123. FCRD inf 3.815
7637 627 332123. inf 15.619
15342 693 332123. inf 32.454
16389 702 332123. inf 34.789
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.32123144447020721e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16389 (273.775s)
# 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 = 16656 (274.119s)
Total program time (secs) = 34.79145 (277.926 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.039s
Rounding heuristic = 252 / 14 / 0.333s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 7 / 0.140s
===========================================================================
=======================================
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.
datacheck 0
feastol 1e-06
feastol_abs 1e-06
hessian_no_f 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
Number of nonzeros:
Initial points
--------------
Time
report_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 49 81.7% $332,123
11 49 80.4% $252,706
12 51 79.8% $167,491
13 53 79.8% $108,081
14 56 80.7% $71,579
8 machines earn the most at $353,513
81.7% 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.