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,...,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,
)
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.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.072
1 -2.16662e+06 4168.94 0.883468 0.073
2 -2.26549e+06 1092.99 2.17355 0.073
3 -2.26807e+06 339.753 2.54056 0.073
4 -2.26491e+06 260.932 2.65815 0.073
5 -2.26283e+06 218.536 2.70606 0.074
6 -2.26142e+06 192.766 2.73660 0.074
7 -2.26055e+06 169.998 2.75323 0.074
8 -2.26013e+06 152.644 2.76265 0.075
9 -2.25975e+06 137.853 2.77337 0.075
10 -2.25951e+06 123.626 2.78079 0.075
11 -2.26022e+06 128.740 2.76929 0.075
12 -2.26036e+06 110.239 2.76954 0.076
13 -2.26062e+06 100.133 2.76746 0.076
14 -2.26147e+06 97.2033 2.75282 0.076
15 -2.26227e+06 86.6805 2.73710 0.077
16 -2.26340e+06 82.5117 2.71494 0.077
17 -2.26488e+06 68.6615 2.68155 0.077
18 -2.26605e+06 64.0655 2.65265 0.077
19 -2.26688e+06 55.3387 2.62733 0.078
20 -2.26779e+06 45.5852 2.59725 0.078
30 -2.23557e+06 9.53453 4.36023 0.081
40 -1.65424e+06 232.596 4.82700 0.083
50 -1.11012e+06 152.262 9.92209 0.086
60 -747689. 0.00000e+00 18.6551 0.088
70 -416266. 0.00000e+00 27.4401 0.090
80 -116079. 0.00000e+00 2.52873 0.092
90 150443. 0.00000e+00 7.31508 0.095
100 221380. 0.00000e+00 0.346355 0.097
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.102
1 2 26723.6 LS inf 0.109
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.125
31 31 201572. FCRD inf 0.175
39 39 276093. LS inf 0.180
76 61 324807. FCRD inf 0.235
3189 438 353513. FCRD inf 4.708
7913 509 353513. inf 13.107
15897 621 353513. inf 25.032
16385 630 353513. inf 25.737
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 (200.634s)
# 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 (201.126s)
Total program time (secs) = 25.73881 (204.576 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.080s
Rounding heuristic = 297 / 9 / 0.444s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.096s
===========================================================================
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.003
4 -2.10695e+06 59.7654 1.26369 0.003
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.004
14 -1.76008e+06 0.00000e+00 16.1102 0.004
15 -1.67344e+06 0.00000e+00 12.6535 0.004
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.008
200 0 5678.31 5678.31 0.00% 0.551
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.511s)
# 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.511s)
Total program time (secs) = 0.55079 (0.592 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.017s
===========================================================================
=======================================
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.007
1 -2.08787e+06 4168.14 0.807571 0.008
2 -2.13661e+06 1170.59 1.70845 0.008
3 -2.13934e+06 412.886 2.46895 0.008
4 -2.13865e+06 315.701 2.53609 0.009
5 -2.13823e+06 268.085 2.56761 0.009
6 -2.13791e+06 232.825 2.58594 0.009
7 -2.13772e+06 200.157 2.59659 0.009
8 -2.13774e+06 170.926 2.59645 0.010
9 -2.13788e+06 141.808 2.58998 0.010
10 -2.13823e+06 119.556 2.57123 0.011
11 -2.13883e+06 23.7446 2.53085 0.011
12 -2.13910e+06 2.50803 2.50803 0.011
13 -2.13961e+06 52.0198 1.67954 0.011
14 -2.13700e+06 55.2317 8.91996 0.012
15 -2.13410e+06 20.6321 6.36662 0.012
16 -2.12915e+06 36.5047 5.57905 0.012
17 -2.11475e+06 16.0126 4.18197 0.013
18 -2.05463e+06 1.93271 4.66114 0.013
19 -1.97220e+06 1.87812 6.75993 0.013
20 -1.81578e+06 1.82578 9.63717 0.013
30 -393714. 0.00000e+00 16.7042 0.016
40 20328.8 0.00000e+00 6.04452 0.018
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -56630.4 FCRD inf 0.026
3 4 43697.2 FCRD inf 0.034
Knitro deduced that the problem is non-convex.
13 10 46596.8 FCRD inf 0.062
6241 6 46596.8 inf 3.443
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.685s)
# 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.758s)
Total program time (secs) = 3.68906 (23.936 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.007s
Rounding heuristic = 31 / 5 / 0.058s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 4 / 0.035s
===========================================================================
=======================================
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.003
5 -2.17028e+06 262.835 2.59699 0.003
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.004
11 -2.16997e+06 160.791 2.63243 0.004
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.005
17 -2.17118e+06 118.390 2.53168 0.005
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.007
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.012
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -15711.9 FCRD inf 0.014
Knitro deduced that the problem is non-convex.
3 4 58808.9 LS inf 0.017
7 8 159137. FP inf 0.025
7940 78 159137. inf 5.644
15939 96 159137. inf 10.757
16386 110 159137. inf 11.042
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 (84.729s)
# 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 (84.910s)
Total program time (secs) = 11.04276 (87.707 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.175s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 5 / 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: 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.002
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.003
5 -2.20027e+06 253.939 2.67807 0.003
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.004
10 -2.20015e+06 117.185 2.69775 0.004
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.005
15 -2.20438e+06 9.23417 4.46606 0.005
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.006
30 -1.60652e+06 366.200 49.1476 0.007
40 -550290. 2.50862e-02 8.82375 0.009
50 -217677. 0.00000e+00 1.20785 0.010
60 105406. 0.00000e+00 1.24628 0.012
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 48113.8 FCRD inf 0.015
Knitro deduced that the problem is non-convex.
15 16 200055. FCRD inf 0.032
7865 180 200055. inf 7.162
15799 209 200055. inf 14.455
16390 212 200055. inf 14.950
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 (115.858s)
# 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 (116.100s)
Total program time (secs) = 14.95163 (119.220 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.267s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 8 / 4 / 0.036s
===========================================================================
=======================================
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.003
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.004
8 -2.22865e+06 80.7539 2.75485 0.004
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.005
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.006
17 -2.22477e+06 50.4409 2.30554 0.006
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.009
40 -570242. 659.173 5.93090 0.011
50 -180114. 0.00000e+00 9.55136 0.014
60 73991.0 0.00000e+00 1.64354 0.016
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -11295.3 FCRD inf 0.020
Knitro deduced that the problem is non-convex.
3 4 66125.2 FCRD inf 0.032
7 8 140646. LS inf 0.041
13 14 169352. FCRD inf 0.046
28 29 189360. FCRD inf 0.064
36 37 240974. FCRD inf 0.072
114 91 312595. FCRD inf 0.130
6266 175 312595. FCRD inf 6.944
7840 202 312595. inf 8.718
15447 276 312595. inf 18.138
16387 281 312595. inf 19.268
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 (149.652s)
# 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 (149.890s)
Total program time (secs) = 19.27004 (153.281 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.011s
Rounding heuristic = 181 / 23 / 0.248s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 6 / 0.064s
===========================================================================
=======================================
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.018
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.034
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.050
31 31 201572. FCRD inf 0.078
39 39 276093. LS inf 0.082
76 61 324807. FCRD inf 0.124
3189 438 353513. FCRD inf 4.665
7913 509 353513. inf 13.461
15897 621 353513. inf 27.780
16385 630 353513. inf 28.617
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 (223.947s)
# 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 (224.440s)
Total program time (secs) = 28.61890 (227.664 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.087s
Rounding heuristic = 297 / 9 / 0.447s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 6 / 0.077s
===========================================================================
=======================================
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.003
1 -2.18631e+06 4169.00 0.972220 0.004
2 -2.29768e+06 1085.58 2.17634 0.004
3 -2.30019e+06 332.058 2.54598 0.005
4 -2.29609e+06 208.243 2.66660 0.005
5 -2.29362e+06 154.106 2.71494 0.006
6 -2.29202e+06 129.462 2.74536 0.006
7 -2.29101e+06 114.596 2.76314 0.007
8 -2.29033e+06 94.6734 2.77424 0.007
9 -2.29020e+06 58.7190 2.77658 0.008
10 -2.29405e+06 74.2433 2.71926 0.008
11 -2.29449e+06 58.6296 2.71225 0.009
12 -2.29534e+06 41.7538 2.69742 0.009
13 -2.29655e+06 2.67403 2.67403 0.010
14 -2.29757e+06 9.85655 2.65300 0.010
15 -2.29832e+06 14.5454 2.63608 0.011
16 -2.29907e+06 18.9549 2.61714 0.011
17 -2.29986e+06 19.1783 2.59476 0.012
18 -2.30040e+06 18.9224 2.57703 0.012
19 -2.30103e+06 68.2573 2.55290 0.015
20 -2.30138e+06 40.6419 2.53644 0.016
30 -2.27459e+06 1.94848 25.0990 0.020
40 -2.21166e+06 1.65880 40.6006 0.024
50 -1.16443e+06 1.69438e-02 7.01353 0.028
60 -292577. 0.00000e+00 7.57071 0.030
70 -97670.5 0.00000e+00 9.10005 0.033
80 -11646.1 0.00000e+00 3.27807 0.037
90 47243.8 0.00000e+00 5.84846 0.039
100 79399.4 3.63798e-11 3.75157e-13 0.042
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -55592.7 FCRD inf 0.045
Knitro deduced that the problem is non-convex.
20 21 167970. FCRD inf 0.111
33 32 170869. FCRD inf 0.128
88 76 193777. FCRD inf 0.225
112 97 242491. FCRD inf 0.257
127 112 294104. FCRD inf 0.281
213 148 317011. FCRD inf 0.416
943 291 322811. FCRD inf 1.815
7843 548 322811. inf 19.242
15799 792 322811. inf 35.775
16390 807 322811. inf 36.935
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 (290.319s)
# 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 (290.897s)
Total program time (secs) = 36.93716 (294.453 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.047s
Rounding heuristic = 392 / 18 / 0.587s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 5 / 0.100s
===========================================================================
=======================================
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.003
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.004
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.005
8 -2.31814e+06 154.914 2.79851 0.005
9 -2.31782e+06 130.244 2.79963 0.006
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.007
13 -2.31914e+06 93.7453 2.79123 0.007
14 -2.31954e+06 85.7147 2.78857 0.008
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.009
18 -2.32347e+06 57.5711 2.74661 0.009
19 -2.32484e+06 51.8753 2.72906 0.010
20 -2.32658e+06 49.5184 2.70419 0.010
30 -2.33494e+06 17.9013 2.49491 0.014
40 -1.85423e+06 0.465955 72.0763 0.018
50 -343246. 0.00000e+00 8.51261 0.022
60 -4306.30 0.00000e+00 6.35057 0.025
70 81006.6 0.00000e+00 1.19469 0.028
80 99440.7 6.87237e-11 1.00441e-08 0.031
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -192422. FCRD inf 0.035
1 2 -117901. LS inf 0.040
Knitro deduced that the problem is non-convex.
3 4 59846.6 DDRD inf 0.055
15 16 208888. FCRD inf 0.083
112 101 211788. FCRD inf 0.220
316 264 231795. FCRD inf 0.511
599 439 231795. FCRD inf 0.920
623 455 312116. FCRD inf 0.951
1906 545 332123. FCRD inf 3.532
2135 560 332123. FCRD inf 3.993
7637 627 332123. inf 16.235
15342 693 332123. inf 34.765
16389 702 332123. inf 37.402
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 (294.212s)
# 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 (294.611s)
Total program time (secs) = 37.40454 (298.516 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.393s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 7 / 0.142s
===========================================================================
=======================================
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.