import math
from dataclasses import dataclass
from plot import draw_comparison, draw_layout, draw_layouts
from report import report_counts, report_layout
@dataclass
class Field:
width: float
length: float
segment_length: float
min_segments: int
max_segments: int
machine_cost: float
segment_cost: float
operating_cost: float
margin: float
@property
def area(self):
return self.width * self.length
@dataclass
class Layout:
npv: float
x: list
y: list
segments: list
@property
def num_machines(self):
return len(self.segments)
def radius(field, segments):
return segments * field.segment_length
def covered_area(field, segments):
return sum(math.pi * radius(field, s) ** 2 for s in segments)
def coverage(field, layout):
return covered_area(field, layout.segments) / field.area
def net_present_value(field, segments):
margin = covered_area(field, segments) * field.margin
machines_cost = len(segments) * field.machine_cost
segments_cost = sum(s - 1 for s in segments) * field.segment_cost
return margin - machines_cost - segments_cost - field.operating_costPivot Irrigators
Lay out centre-pivot irrigation machines in a field to maximize the net present value of the investment, a circle-packing problem with discrete radii.
Introduction
We consider the problem of designing the layout of center-pivot irrigation machines in a field, which can be modeled as a circle packing problem.
Pivot irrigators are commonly used by crop farmers to supplement natural rainfall. For example, large areas of the mid-west USA are covered with these machines. The machines are almost always arranged in a simple grid pattern, which is not an efficient design in terms of coverage.
We consider the following situation:
- In a semi-arid region, only irrigated areas are productive.
- We consider a rectangular field in this region, with sides of 914.400 by 442.570 metres, with a total area of 40.4686 hectares (exactly 100 acres).
- The water distribution system of the field, composed of pivot irrigators, is worn out, so we need to replace it with the same type of machines.
- The machines are composed of a pivot mechanism and 20 metre long segments.
To maximize crop yield, it is important that we irrigate as much of the area as possible. However, we need to account for the cost of the machines, along with the operational and maintenance costs over their lifetime.
This example is based on this post.
Here is the grid layout of eight identical machines, and the layout the model finds for the same eight:
Both cover the same field with the same number of machines, and on the numbers below the grid is not merely worse. It loses money. Letting the machines differ in size and sit where they fit turns that loss into a profit.
Investment characteristics
Each machine costs $43,606 to purchase, install and for its maintenance over 15 years (its expected lifetime). A machine consists of the pivot mechanism and a single 20 metre long built-in segment.
Additional 20 metre long segments cost $15,803 each all included. A machine may have up to a total of eight segments (including the built-in segment).
We have fixed operating costs of $2,009,094 for 15 years, covering costs for other machinery and staff associated with working the field.
The planned crop will yield an average gross margin of $10.268 per square metre per year, allowing for all variable costs (planting, harvesting, etc).
A positive Net Present Value (NPV) would indicate that this is a worthwhile investment, while a negative one would indicate that the investment is a loss.
Furthermore, we note that larger machines are more profitable. Specifically, the cost of a machine is a linear function of the number of segments, while the yield from a machine is a function of the coverage area, which increases with the square of the number of segments. Therefore, all else being equal, larger machines are better.
In particular, a machine with only one or two segments makes a loss, while larger machines make a positive contribution to the NPV. Therefore, we only consider machines with at least 3 segments (including the built-in segment).
Problem description
Input
- \(S_{\text{size}}\) the length of each irrigation machine segment
- \(S^{\text{min}}\) the minimum number of segments per machine
- \(S^{\text{max}}\) the maximum number of segments per machine
- \(W\) the width of the field
- \(L\) the length of the field
- \(C_{\text{operating}}\) the operating cost (over 15 years)
- \(C_{\text{machine}}\) the cost of each irrigation machine (all included)
- \(C_{\text{segment}}\) the cost of each additional irrigation machine segment (all included)
- \(Y\) the yield per square metre irrigated
Problem:
Create a layout by choosing:
- the number of machines
- the number of segments of each machine
- the position of each machine’s pivot in the field
such that:
- the circle covered by each machine is within the field’s boundaries
- the circles covered by two machines cannot overlap
Objective:
Maximize the overall NPV of our investment.
This is a variant of a circle packing problem, where the radii of the circles are decision variables that must take values in a discrete set.
Mixed-integer nonlinear model
We simplify the model by making the number of machines an exogenous input \(N\). Otherwise, we would need an additional binary variable for each machine to decide whether we use it or not, which would unnecessarily complicate the model. We can instead solve the model iteratively over a reasonable range for the number of machines.
For a given number of machines \(N\), the model needs to decide, for each machine, the number of segments and the position of the machine’s pivot.
Variables
- \(s_i \in \mathbb{N}\), \(S^{\text{min}} \le s_i \le S^{\text{max}}\), \(i=1,...,N\), the number of segments of machine \(i\) (including the built-in segment)
- \(x_i \in \mathbb{R}\), \(i=1,...,N\), the \(x\) position of machine \(i\)’s pivot
- \(y_i \in \mathbb{R}\), \(i=1,...,N\), the \(y\) position of machine \(i\)’s pivot
Objective: maximize the NPV, i.e. the total yield of the irrigated areas minus the cost of the machines, the cost of the additional segments and the operating cost
\[ \max \quad \left( \sum_{i=1}^N \pi \cdot (S_{\text{size}} \cdot s_i)^2 \right) \cdot Y - N \cdot C_{\text{machine}} - \left( \sum_{i=1}^N (s_i - 1) \right) \cdot C_{\text{segment}} - C_{\text{operating}} \]
Note that the cost part of the NPV calculation is linear. But the yield is a function of the area covered by each machine, which depends on the squared number of segments of the machine: the objective is therefore nonlinear (quadratic).
Constraints
- Irrigation circles are within the field’s boundaries:
\[ \forall i=1,...,N, \qquad S_{\text{size}} \cdot s_i \le x_i \le W - S_{\text{size}} \cdot s_i \]
\[ \forall i=1,...,N, \qquad S_{\text{size}} \cdot s_i \le y_i \le L - S_{\text{size}} \cdot s_i \]
- Irrigation circles must not overlap, i.e. the distance between two pivots must be at least the sum of the radii of the two irrigation circles:
\[ \forall i,j=1,...,N, \; i<j, \qquad (x_i - x_j)^2 + (y_i - y_j)^2 \ge \left( S_{\text{size}} \cdot (s_i + s_j) \right)^2 \]
These non-overlap constraints are nonconvex quadratic constraints, which makes this problem a nonconvex mixed-integer nonlinear program (MINLP).
Input data
A Field is the field and the money. It holds how big the field is, how long a segment is, how many segments a machine may carry, what a machine and a segment cost, what running the field costs, and what a square metre yields in a year. A Layout is where each machine stands and how many segments it carries, together with the net present value that layout earns.
net_present_value is the objective written out in plain code, so a layout that was never solved for can be priced the same way as one that was.
The field is 914.400 by 442.570 metres, machines are built from 20 metre segments and carry between 3 and 8 of them, and the costs and yield are the ones listed above, in dollars over the fifteen year lifetime. grid_layout is the arrangement farms actually use, four machines by two, every one the same size and as large as the spacing allows.
field = Field(
width=914.400,
length=442.570,
segment_length=20,
min_segments=3,
max_segments=8,
machine_cost=43606.07950630836,
segment_cost=15803.03975315418,
operating_cost=2009094.3111355049,
margin=10.268207333516287,
)
def grid_layout(field, segments=5):
reach = radius(field, segments)
columns = [reach + k * (field.width - 2 * reach) / 3 for k in range(4)]
rows = [reach, field.length - reach]
counts = [float(segments)] * (4 * len(rows))
x = [column for _ in rows for column in columns]
y = [row for row in rows for _ in columns]
return Layout(net_present_value(field, counts), x, y, counts)A layout is the field seen from above, each machine a disc as wide as its reach. The dashed rings inside a disc are its segments, so a bigger machine is both wider and more finely drawn, and the number at the center is how many it carries. Ground no disc covers is ground that earns nothing.
Eight machines on a grid is the arrangement to beat. It leaves the four corners, the gaps between neighbours and a strip right across the middle dry, and on these numbers it does not merely earn less than it could. It loses money.
report_layout(field, grid_layout(field))8 machines, net present value -$282,958, covering 62.1% of the field
machine segments reach x y covered share
------------------------------------------------------------------
1 5 100m 100.0 100.0 31,416 7.8%
2 5 100m 338.1 100.0 31,416 7.8%
3 5 100m 576.3 100.0 31,416 7.8%
4 5 100m 814.4 100.0 31,416 7.8%
5 5 100m 100.0 342.6 31,416 7.8%
6 5 100m 338.1 342.6 31,416 7.8%
7 5 100m 576.3 342.6 31,416 7.8%
8 5 100m 814.4 342.6 31,416 7.8%
Margin $2,580,682 less $348,849 of machines, $505,697 of segments,
$2,009,094 to operatedraw_layout(field, grid_layout(field), "Eight machines on a grid")Model implementation
import 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 add_objective and add_constraint take them as written.
Since the problem is a nonconvex MINLP, we enable Knitro’s MIP multistart, which helps find good solutions, and we set a node limit on the branch-and-bound to bound the resolution time.
def maximize_npv(field, num_machines, *, multistart=1, max_nodes=2**14):
prob = knitro.Problem()
prob.set_param(knitro.KN_PARAM_MIP_MULTISTART, multistart)
prob.set_param(knitro.KN_PARAM_MIP_MAXNODES, max_nodes)
reach = radius(field, field.min_segments)
machines = range(num_machines)
s = [
prob.add_variable(
lb=field.min_segments,
ub=field.max_segments,
vtype=knitro.KN_VARTYPE_INTEGER,
)
for _ in machines
]
x = [prob.add_variable(lb=reach, ub=field.width - reach) for _ in machines]
y = [prob.add_variable(lb=reach, ub=field.length - reach) for _ in machines]
area = prob.nsum(math.pi * (s[i] * field.segment_length) ** 2 for i in machines)
margin = field.margin * area
machines_cost = num_machines * field.machine_cost
segments_cost = field.segment_cost * prob.nsum(s[i] - 1 for i in machines)
objective = margin - machines_cost - segments_cost - field.operating_cost
prob.add_objective(objective, goal=knitro.KN_OBJGOAL_MAXIMIZE)
for i in machines:
prob.add_constraint(x[i] >= s[i] * field.segment_length)
prob.add_constraint(x[i] <= field.width - s[i] * field.segment_length)
prob.add_constraint(y[i] >= s[i] * field.segment_length)
prob.add_constraint(y[i] <= field.length - s[i] * field.segment_length)
for i in machines:
for j in range(i + 1, num_machines):
radii = (s[i] + s[j]) * field.segment_length
prob.add_constraint((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2 >= radii**2)
prob.solve()
npv = prob.get_attr(knitro.KN_ATTR_OBJ_VALUE)
return Layout(npv, [v.value for v in x], [v.value for v in y], [v.value for v in s])Solving for eight machines
Eight is the number the grid uses, so it is the first thing to ask for, the same field and the same count with the machines free to move and free to differ in size.
layout_8 = maximize_npv(field, 8)=======================================
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.01s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 373 | 0
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: [0e+00, 0e+00] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.68170e+06 14400.9 0.211068 0.098
1 -2.16662e+06 4168.94 0.883468 0.099
2 -2.26549e+06 1092.99 2.17355 0.099
3 -2.26807e+06 339.753 2.54056 0.099
4 -2.26491e+06 260.932 2.65815 0.100
5 -2.26283e+06 218.536 2.70606 0.100
6 -2.26142e+06 192.766 2.73660 0.100
7 -2.26055e+06 169.998 2.75323 0.100
8 -2.26013e+06 152.644 2.76265 0.101
9 -2.25975e+06 137.853 2.77337 0.101
10 -2.25951e+06 123.626 2.78079 0.101
11 -2.26022e+06 128.740 2.76929 0.101
12 -2.26036e+06 110.239 2.76954 0.102
13 -2.26062e+06 100.133 2.76746 0.102
14 -2.26147e+06 97.2033 2.75282 0.102
15 -2.26227e+06 86.6805 2.73710 0.103
16 -2.26340e+06 82.5117 2.71494 0.103
17 -2.26488e+06 68.6615 2.68155 0.103
18 -2.26605e+06 64.0655 2.65265 0.104
19 -2.26688e+06 55.3387 2.62733 0.104
20 -2.26779e+06 45.5852 2.59725 0.104
30 -2.23557e+06 9.53453 4.36023 0.107
40 -1.65424e+06 232.595 4.82700 0.110
50 -1.11012e+06 152.262 9.92205 0.112
60 -747658. 0.00000e+00 18.6520 0.114
70 -365828. 0.00000e+00 32.0869 0.116
80 -60523.5 0.00000e+00 2.34387 0.119
90 71731.8 24.9194 1.17656 0.121
100 224247. 3.60164e-06 2.64885e-06 0.123
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.127
1 2 26723.6 LS inf 0.131
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.149
31 31 201572. FCRD inf 0.189
39 39 276093. LS inf 0.193
76 61 324807. FCRD inf 0.243
1759 334 353513. FCRD inf 2.768
3825 386 353513. FCRD inf 6.431
7909 466 353513. inf 14.316
15900 599 353513. inf 27.299
16386 602 353513. inf 28.146
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.53513363574206363e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16386 (219.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 = 16680 (220.085s)
Total program time (secs) = 28.14845 (222.161 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.040s
Rounding heuristic = 278 / 10 / 0.435s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 7 / 0.089s
===========================================================================
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 84.5 85.0 20,106 5.0%
2 5 100m 641.7 101.2 31,416 7.8%
3 4 80m 829.7 84.7 20,106 5.0%
4 7 140m 140.0 302.6 61,575 15.2%
5 3 60m 439.9 61.2 11,310 2.8%
6 7 140m 774.4 302.6 61,575 15.2%
7 5 100m 268.7 100.0 31,416 7.8%
8 8 160m 453.8 282.6 80,425 19.9%
Margin $3,264,563 less $348,849 of machines, $553,106 of segments,
$2,009,094 to operatedraw_layout(field, layout_8)Solving for every count
The number of machines is an input to the model rather than something it decides, so the question of how many to buy is answered by solving once for each count in a reasonable range.
counts = range(3, 15)layouts = [maximize_npv(field, num_machines) for num_machines in counts]Show the full outputHide the full output
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 83 | 0
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: [0e+00, 0e+00] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.88632e+06 14400.5 0.501635 0.002
1 -2.06819e+06 4167.22 0.842228 0.002
2 -2.10427e+06 1234.37 3.39503 0.002
3 -2.10698e+06 111.217 1.26369 0.002
4 -2.10695e+06 59.7654 1.26369 0.002
5 -2.10642e+06 92.8391 6.41785 0.002
6 -2.09065e+06 13.1853 2.33209 0.002
7 -2.08488e+06 3.70580 2.26512 0.002
8 -2.04651e+06 2.10497 3.51711 0.003
9 -1.97529e+06 1.99335 5.37828 0.003
10 -1.90748e+06 1.92130 6.61155 0.003
11 -1.90118e+06 1.84598 6.68489 0.003
12 -1.79043e+06 0.00000e+00 25.4903 0.003
13 -1.84283e+06 0.00000e+00 17.3191 0.003
14 -1.76008e+06 0.00000e+00 16.1102 0.003
15 -1.67344e+06 0.00000e+00 12.6535 0.003
16 -1.43086e+06 0.00000e+00 12.8315 0.003
17 -1.25574e+06 0.00000e+00 9.64968 0.003
18 -1.25650e+06 0.00000e+00 9.64820 0.003
19 -1.24009e+06 0.00000e+00 9.66460 0.004
20 -1.17540e+06 311.235 5.56185 0.004
30 -338459. 0.00000e+00 16.7200 0.004
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 1 5678.31 LEAF inf 0.006
200 0 5678.31 5678.31 0.00% 0.618
EXIT: Optimal solution found (assuming convexity).
Final Statistics for MIP
------------------------
Final objective value = 5.67831437182333320e+03
Final bound value = 5.67831437182333320e+03
Final optimality gap (abs / rel) = 0.00000e+00 / 0.00000e+00 (0.00%)
# of root cutting plane rounds = 0
# of restarts = 0
# of nodes processed = 200 (0.575s)
# 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.575s)
Total program time (secs) = 0.61786 (0.650 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.008s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 123 | 0
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: [0e+00, 0e+00] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.84540e+06 14400.9 0.405803 0.008
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.009
4 -2.13865e+06 315.701 2.53609 0.009
5 -2.13823e+06 268.085 2.56761 0.010
6 -2.13791e+06 232.825 2.58594 0.010
7 -2.13772e+06 200.157 2.59659 0.010
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.011
15 -2.13410e+06 20.6321 6.36662 0.011
16 -2.12915e+06 36.5047 5.57905 0.011
17 -2.11475e+06 16.0126 4.18197 0.011
18 -2.05463e+06 1.93271 4.66114 0.012
19 -1.97220e+06 1.87812 6.75993 0.012
20 -1.81578e+06 1.82578 9.63717 0.012
30 -393714. 0.00000e+00 16.7042 0.013
40 20287.4 0.00000e+00 6.03009 0.014
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -56630.4 FCRD inf 0.019
3 4 43697.2 FCRD inf 0.027
Knitro deduced that the problem is non-convex.
13 10 46596.8 FCRD inf 0.041
6442 5 46596.8 inf 4.827
EXIT: Satisfactory solution found.
Final Statistics for MIP
------------------------
Final objective value = 4.65968443674487062e+04
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 6654 (30.639s)
# 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 = 6694 (30.704s)
Total program time (secs) = 5.14462 (31.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 = 1 / 1 / 0.010s
Rounding heuristic = 32 / 6 / 0.045s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 9 / 4 / 0.019s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 172 | 0
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: [0e+00, 0e+00] | [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.01 0.00000e+00 30.8072 0.010
70 198100. 0.00000e+00 7.90316e-05 0.012
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.
7 8 159137. FP inf 0.029
26 16 159137. FCRD inf 0.066
37 20 159137. FCRD inf 0.080
7940 76 159137. inf 5.923
15936 101 159137. inf 11.282
16384 107 159137. inf 11.584
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 = 16384 (88.615s)
# 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 = 16524 (88.806s)
Total program time (secs) = 11.58547 (91.374 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.009s
Rounding heuristic = 131 / 7 / 0.187s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 10 / 4 / 0.031s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 230 | 0
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: [0e+00, 0e+00] | [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.96762 2.48351 0.004
15 -2.20438e+06 9.23414 4.46600 0.004
16 -2.20397e+06 4.37366 5.31747 0.005
17 -2.19688e+06 99.4994 22.9034 0.005
18 -2.19168e+06 23.3843 2.59924 0.005
19 -2.18320e+06 83.8034 4.79067 0.005
20 -2.16916e+06 25.9151 2.47731 0.005
30 -1.60291e+06 368.494 49.1903 0.007
40 -423944. 2.22508e-02 9.81663 0.008
50 -4110.85 0.00000e+00 2.51589 0.010
60 115708. 1.30967e-10 9.99592e-11 0.011
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 48113.8 FCRD inf 0.013
Knitro deduced that the problem is non-convex.
15 16 200055. FCRD inf 0.031
7754 197 200055. inf 7.084
15445 219 200055. inf 14.462
16389 220 200055. inf 15.432
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 2.00055103970827535e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16389 (119.768s)
# 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 = 16600 (119.998s)
Total program time (secs) = 15.43307 (122.761 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 2 / 0 / 0.002s
Rounding heuristic = 206 / 7 / 0.255s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 8 / 4 / 0.032s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 297 | 0
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: [0e+00, 0e+00] | [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.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.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 -570241. 659.180 5.93091 0.010
50 -180132. 0.00000e+00 9.54566 0.012
60 69613.5 0.00000e+00 3.41120 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.029
7 8 140646. LS inf 0.036
13 14 169352. FCRD inf 0.042
28 29 189360. FCRD inf 0.057
36 37 212267. FCRD inf 0.064
48 47 240974. FCRD inf 0.073
145 113 312595. FCRD inf 0.140
7766 197 312595. inf 8.889
15551 253 312595. inf 17.858
16388 260 312595. inf 18.932
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.12594833578581456e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (146.777s)
# 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 = 16558 (146.994s)
Total program time (secs) = 18.93421 (149.973 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 2 / 0 / 0.012s
Rounding heuristic = 161 / 14 / 0.220s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 5 / 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.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 373 | 0
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: [0e+00, 0e+00] | [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.595 4.82700 0.013
50 -1.11012e+06 152.262 9.92205 0.015
60 -747658. 0.00000e+00 18.6520 0.018
70 -365828. 0.00000e+00 32.0869 0.020
80 -60523.5 0.00000e+00 2.34387 0.022
90 71731.8 24.9194 1.17656 0.024
100 224247. 3.60164e-06 2.64885e-06 0.026
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.076
39 39 276093. LS inf 0.082
76 61 324807. FCRD inf 0.125
1759 334 353513. FCRD inf 2.532
3825 386 353513. FCRD inf 6.380
7909 466 353513. inf 13.667
15900 599 353513. inf 25.919
16386 602 353513. inf 26.703
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.53513363574206363e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16386 (209.281s)
# 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 = 16680 (209.641s)
Total program time (secs) = 26.70506 (212.626 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.034s
Rounding heuristic = 278 / 10 / 0.358s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 7 / 0.082s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 458 | 0
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: [0e+00, 0e+00] | [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.003
2 -2.29768e+06 1085.58 2.17634 0.003
3 -2.30019e+06 332.058 2.54598 0.003
4 -2.29609e+06 208.243 2.66660 0.004
5 -2.29362e+06 154.106 2.71494 0.004
6 -2.29202e+06 129.462 2.74536 0.005
7 -2.29101e+06 114.596 2.76314 0.005
8 -2.29033e+06 94.6734 2.77424 0.006
9 -2.29020e+06 58.7190 2.77658 0.006
10 -2.29405e+06 74.2433 2.71926 0.006
11 -2.29449e+06 58.6296 2.71225 0.007
12 -2.29534e+06 41.7538 2.69742 0.007
13 -2.29655e+06 2.67403 2.67403 0.008
14 -2.29757e+06 9.85655 2.65300 0.008
15 -2.29832e+06 14.5454 2.63608 0.008
16 -2.29907e+06 18.9549 2.61714 0.009
17 -2.29986e+06 19.1783 2.59476 0.009
18 -2.30040e+06 18.9224 2.57703 0.010
19 -2.30103e+06 68.2573 2.55290 0.011
20 -2.30138e+06 40.6419 2.53644 0.012
30 -2.27459e+06 1.94848 25.0990 0.015
40 -2.21166e+06 1.65880 40.6006 0.018
50 -1.16443e+06 1.69438e-02 7.01353 0.022
60 -292585. 0.00000e+00 7.57076 0.024
70 -138617. 0.00000e+00 0.665284 0.027
80 -62880.1 0.00000e+00 6.88877e-03 0.030
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -130114. FCRD inf 0.033
Knitro deduced that the problem is non-convex.
2 3 -55592.7 LS inf 0.045
5 6 142163. FCRD inf 0.057
11 11 216684. FCRD inf 0.073
13 13 251189. FCRD inf 0.088
72 57 291205. FCRD inf 0.215
240 127 322811. FCRD inf 0.492
397 174 322811. FCRD inf 0.727
7713 524 322811. inf 18.194
15476 620 322811. inf 34.902
16388 636 322811. inf 36.820
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.22810693957703188e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (289.132s)
# 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 = 16686 (289.526s)
Total program time (secs) = 36.82219 (292.276 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.004s
Rounding heuristic = 293 / 13 / 0.432s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 6 / 0.099s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 552 | 0
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: [0e+00, 0e+00] | [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.005
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.007
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.009
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.465961 72.0761 0.018
50 -343249. 0.00000e+00 8.51262 0.021
60 -4005.83 0.00000e+00 6.33967 0.025
70 80714.7 0.00000e+00 0.601606 0.027
80 104582. 0.00000e+00 0.333255 0.031
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 59846.6 FCRD inf 0.035
Knitro deduced that the problem is non-convex.
23 24 76954.6 FCRD inf 0.084
38 39 102761. FCRD inf 0.105
46 47 160174. FCRD inf 0.113
148 137 208888. FCRD inf 0.302
187 170 208888. FCRD inf 0.365
234 209 231795. FCRD inf 0.432
1540 640 254703. FCRD inf 2.929
1767 654 312116. FCRD inf 3.555
7092 732 332123. FCRD inf 19.119
7455 730 332123. inf 20.164
15257 776 332123. inf 39.839
16386 777 332123. inf 42.423
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.32123144447019324e+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 (334.449s)
# 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 = 16695 (334.876s)
Total program time (secs) = 42.42613 (338.020 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.026s
Rounding heuristic = 300 / 15 / 0.455s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 4 / 0.120s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
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 expressions: 655 | 0
Number of constraints: 99 | 99
eq. ineq. range | eq. ineq. range
linear: 0 44 0 | 0 44 0
quadratic: 0 55 0 | 0 55 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 11 88 | 11 88
quadratic: 11 330 198 | 11 330 198
total: 11 418 198 | 11 418 198
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [0e+00, 0e+00] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.55892e+06 14401.0 0.184312 0.002
1 -2.22568e+06 4169.14 1.24444 0.003
2 -2.36204e+06 1075.25 2.18026 0.003
3 -2.36435e+06 316.479 2.55796 0.004
4 -2.35903e+06 195.818 2.68101 0.004
5 -2.35599e+06 157.615 2.72959 0.005
6 -2.35425e+06 127.053 2.75960 0.005
7 -2.35352e+06 96.8355 2.77302 0.005
8 -2.35371e+06 57.8037 2.77449 0.006
9 -2.35922e+06 105.574 2.70194 0.006
10 -2.35970e+06 76.7210 2.69532 0.007
11 -2.36024e+06 5.71021 2.68824 0.007
12 -2.36218e+06 2.65386 2.65386 0.008
13 -2.36683e+06 2.51510 4.55570 0.008
14 -2.35529e+06 2.48982 34.7539 0.008
15 -2.35419e+06 21.2098 5.68532 0.009
16 -2.35044e+06 29.0164 4.85545 0.009
17 -2.34107e+06 61.5293 2.53126 0.010
18 -2.32874e+06 47.4339 2.70344 0.010
19 -2.29618e+06 31.7195 3.99136 0.010
20 -2.23371e+06 31.6614 5.45247 0.011
30 -2.15081e+06 1.21544 61.5440 0.016
40 -1.78506e+06 0.372527 85.7465 0.020
50 -1.14331e+06 0.00000e+00 8.43256 0.024
60 -295020. 0.00000e+00 3.82340 0.028
70 -159347. 0.00000e+00 2.28722 0.031
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -223125. FCRD inf 0.039
Knitro deduced that the problem is non-convex.
3 4 -131496. FCRD inf 0.079
7 8 -102790. LS inf 0.104
35 36 46251.9 FCRD inf 0.174
50 49 120773. FCRD inf 0.219
62 61 169487. FCRD inf 0.238
136 120 172386. FCRD inf 0.428
206 168 175286. FCRD inf 0.579
361 261 178186. FCRD inf 0.979
1870 582 201093. FCRD inf 5.721
6476 602 201093. inf 25.955
12708 990 249807. FCRD inf 49.344
12842 994 249807. inf 49.953
16384 1017 249807. inf 65.881
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 2.49806835271297023e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16384 (520.709s)
# 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 = 16775 (521.408s)
Total program time (secs) = 65.88407 (523.661 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.143s
Rounding heuristic = 368 / 14 / 0.608s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 17 / 7 / 0.166s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 36 | 36
bounds: lower upper range | lower upper range
0 0 36 | 0 0 36
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
24 0 12 | 24 0 12
Number of expressions: 767 | 0
Number of constraints: 114 | 114
eq. ineq. range | eq. ineq. range
linear: 0 48 0 | 0 48 0
quadratic: 0 66 0 | 0 66 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 12 96 | 12 96
quadratic: 12 396 234 | 12 396 234
total: 12 492 234 | 12 492 234
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [0e+00, 0e+00] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.51800e+06 14401.0 0.173121 0.005
1 -2.24537e+06 4169.21 0.909667 0.006
2 -2.39422e+06 1071.62 2.18168 0.007
3 -2.39643e+06 312.026 2.56144 0.008
4 -2.39125e+06 218.641 2.68525 0.009
5 -2.38771e+06 175.826 2.73442 0.010
6 -2.38589e+06 150.937 2.75803 0.011
7 -2.38474e+06 130.566 2.76823 0.012
8 -2.38390e+06 114.545 2.77471 0.013
9 -2.38326e+06 102.220 2.78188 0.014
10 -2.38316e+06 91.6032 2.78313 0.015
11 -2.38388e+06 95.5451 2.77599 0.015
12 -2.38371e+06 85.8699 2.77754 0.016
13 -2.38376e+06 77.1747 2.77662 0.017
14 -2.38383e+06 69.3538 2.77515 0.018
15 -2.38403e+06 62.3258 2.77216 0.019
16 -2.38433e+06 56.6964 2.76791 0.020
17 -2.38480e+06 51.6220 2.76186 0.022
18 -2.38547e+06 47.2041 2.75444 0.023
19 -2.38752e+06 48.7163 2.73194 0.027
20 -2.38905e+06 17.6810 2.71391 0.028
30 -2.38111e+06 8.95845 6.32155 0.037
40 -2.32117e+06 2.10445 93.9809 0.047
50 -2.34003e+06 1.81585 34.9505 0.056
60 -2.15105e+06 1.14059 54.6782 0.063
70 -1.19409e+06 0.00000e+00 8.05165 0.070
80 -352081. 0.00000e+00 0.192569 0.077
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -434475. FCRD inf 0.083
Knitro deduced that the problem is non-convex.
3 4 38456.4 FCRD inf 0.126
53 42 67162.9 FCRD inf 0.356
155 124 115877. FCRD inf 0.761
185 148 141684. FCRD inf 0.874
193 152 167491. FCRD inf 0.894
6801 672 167491. inf 29.666
9517 805 190398. FCRD inf 41.862
13668 953 190398. inf 61.758
16388 1058 190398. inf 74.561
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 1.90397716011834331e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (589.442s)
# 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 = 16797 (590.261s)
Total program time (secs) = 74.56357 (592.819 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 = 7 / 0 / 0.247s
Rounding heuristic = 377 / 10 / 0.643s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 4 / 0.128s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 39 | 39
bounds: lower upper range | lower upper range
0 0 39 | 0 0 39
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
26 0 13 | 26 0 13
Number of expressions: 888 | 0
Number of constraints: 130 | 130
eq. ineq. range | eq. ineq. range
linear: 0 52 0 | 0 52 0
quadratic: 0 78 0 | 0 78 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 13 104 | 13 104
quadratic: 13 468 273 | 13 468 273
total: 13 572 273 | 13 572 273
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [0e+00, 0e+00] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.47707e+06 14401.0 0.166195 0.002
1 -2.26506e+06 4169.30 0.965946 0.003
2 -2.42640e+06 1068.55 2.18285 0.004
3 -2.42851e+06 309.861 2.56371 0.004
4 -2.42217e+06 211.140 2.69012 0.005
5 -2.41793e+06 166.044 2.73688 0.005
6 -2.41522e+06 139.636 2.76427 0.006
7 -2.41337e+06 117.480 2.78109 0.007
8 -2.41213e+06 106.345 2.79019 0.007
9 -2.41134e+06 94.2232 2.79510 0.008
10 -2.41056e+06 83.6854 2.80014 0.008
11 -2.41154e+06 87.0391 2.79196 0.009
12 -2.41177e+06 76.7426 2.79024 0.009
13 -2.41281e+06 55.7265 2.78149 0.010
14 -2.41456e+06 21.6990 2.76571 0.010
15 -2.41862e+06 31.4924 2.72643 0.011
16 -2.42001e+06 2.71057 2.71057 0.011
17 -2.42249e+06 17.2079 2.68177 0.012
18 -2.43024e+06 2.55984 2.55984 0.013
19 -2.43265e+06 2.48224 2.48224 0.013
20 -2.43284e+06 2.46570 3.19946 0.014
30 -2.41618e+06 2.10380 16.9444 0.021
40 -2.38005e+06 1.85690 26.5292 0.026
50 -1.89374e+06 8.47849 76.0609 0.031
60 -1.67982e+06 0.274545 89.1051 0.034
70 -1.34335e+06 1.62220e-02 9.73970 0.041
80 -486042. 0.00000e+00 1.58612 0.046
90 -58565.4 0.00000e+00 0.929926 0.050
100 94461.0 0.00000e+00 0.265157 0.055
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -78365.6 FCRD inf 0.061
Knitro deduced that the problem is non-convex.
27 28 -75466.0 FCRD inf 0.211
58 59 -52558.8 FCRD inf 0.272
81 82 -945.132 FCRD inf 0.336
96 97 21962.1 FCRD inf 0.350
159 158 76475.3 FCRD inf 0.485
438 373 79375.0 FCRD inf 1.036
1160 733 79375.0 FCRD inf 3.023
2091 1035 108081. FCRD inf 6.331
7766 1146 108081. inf 36.144
11280 1202 108081. FCRD inf 53.862
15550 1352 108081. inf 74.022
16389 1388 108081. inf 77.995
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 1.08081406836112961e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16389 (616.739s)
# 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 = 16921 (617.682s)
Total program time (secs) = 77.99852 (622.609 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 4 / 1 / 0.149s
Rounding heuristic = 508 / 20 / 0.887s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 4 / 0.193s
===========================================================================
=======================================
Commercial License
Artelys Knitro 16.0.0
=======================================
Knitro changing mip_method from AUTO to 1.
No start point provided -- Knitro computing one.
Knitro presolve eliminated 0 variables (0%) and 0 constraints (0%) in 0.00s.
concurrent_evals 0
feastol 1e-06
feastol_abs 1e-06
mip_maxnodes 16384
mip_multistart 1
opttol 1e-06
opttol_abs 0.001
Knitro changing mip_root_nlpalg from AUTO to 1.
Knitro changing mip_node_nlpalg from AUTO to 1.
Knitro changing mip_branchrule from AUTO to 2.
Knitro changing mip_selectrule from AUTO to 2.
Knitro changing mip_mir from AUTO to 2.
Knitro changing mip_clique from AUTO to 0.
Knitro changing mip_zerohalf from AUTO to 0.
Knitro changing mip_liftproject from AUTO to 0.
Knitro changing mip_knapsack from AUTO to 2.
Knitro changing mip_gomory from AUTO to 0.
Knitro changing mip_cut_flowcover from AUTO to 2.
Knitro changing mip_cut_probing from AUTO to 1.
Knitro changing mip_rounding from AUTO to 3.
Knitro changing mip_heuristic_strategy from AUTO to 1.
Knitro changing mip_heuristic_feaspump from AUTO to 1.
Knitro changing mip_heuristic_misqp from AUTO to 0.
Knitro changing mip_heuristic_mpec from AUTO to 1.
Knitro changing mip_heuristic_diving from AUTO to 1926.
Knitro changing mip_heuristic_fixpropagate from AUTO to 62.
Knitro changing mip_heuristic_lns from AUTO to 0.
Knitro changing mip_heuristic_localsearch from AUTO to 1.
Knitro changing mip_pseudoinit from AUTO to 1.
Problem Characteristics | Presolved
-----------------------
Problem type: MIQCQP
Objective: maximize / quadratic
Number of variables: 42 | 42
bounds: lower upper range | lower upper range
0 0 42 | 0 0 42
free fixed | free fixed
0 0 | 0 0
cont. binary integer | cont. binary integer
28 0 14 | 28 0 14
Number of expressions: 1018 | 0
Number of constraints: 147 | 147
eq. ineq. range | eq. ineq. range
linear: 0 56 0 | 0 56 0
quadratic: 0 91 0 | 0 91 0
Number of nonzeros:
objective Jacobian Hessian | objective Jacobian Hessian
linear: 14 112 | 14 112
quadratic: 14 546 315 | 14 546 315
total: 14 658 315 | 14 658 315
Knitro using Branch and Bound method with 8 threads.
Initial points
--------------
No initial point provided for the root node relaxation.
No primal point provided for the MIP.
Coefficient range:
linear objective: [2e+04, 2e+04] | [3e+01, 3e+01]
linear constraints: [1e+00, 2e+01] | [1e+00, 2e+01]
quadratic objective: [1e+04, 1e+04] | [2e+01, 2e+01]
quadratic constraints: [1e+00, 8e+02] | [2e-02, 2e+01]
variable bounds: [3e+00, 9e+02] | [3e+00, 9e+02]
constraint bounds: [0e+00, 0e+00] | [4e+02, 9e+02]
Root node relaxation
--------------------
Iter Objective Feasibility Optimality Time
error error (secs)
---- --------- ----------- ---------- ------
0 -1.43615e+06 14401.0 0.147938 0.003
1 -2.28474e+06 4169.33 0.935687 0.004
2 -2.45857e+06 1065.93 2.18384 0.004
3 -2.46060e+06 302.345 2.56566 0.005
4 -2.45284e+06 195.548 2.69730 0.006
5 -2.44834e+06 150.776 2.74373 0.006
6 -2.44555e+06 117.964 2.77136 0.007
7 -2.44344e+06 104.265 2.78716 0.008
8 -2.44230e+06 95.5991 2.79528 0.008
9 -2.44128e+06 86.1724 2.80190 0.009
10 -2.44082e+06 79.5361 2.80420 0.009
11 -2.44162e+06 81.0669 2.79810 0.010
12 -2.44169e+06 72.7681 2.79656 0.011
13 -2.44211e+06 61.4529 2.79224 0.011
14 -2.44307e+06 61.0703 2.78366 0.012
15 -2.44389e+06 57.8645 2.77816 0.013
16 -2.44459e+06 54.6550 2.77366 0.013
17 -2.44738e+06 85.7540 2.74999 0.016
18 -2.45079e+06 133.913 2.78977 0.017
19 -2.45331e+06 153.460 3.19698 0.018
20 -2.45604e+06 175.298 2.66331 0.019
30 -2.46578e+06 281.448 3.56960 0.026
40 -2.35206e+06 223.191 10.4376 0.034
50 -2.17856e+06 1.15996 8.11115 0.040
60 -1.73550e+06 3.33520 3.29668 0.045
70 -1.49947e+06 0.164717 18.0433 0.050
80 -1.08761e+06 1.15266e-03 57.7146 0.055
90 -637290. 0.00000e+00 14.3988 0.060
100 -405647. 0.00000e+00 0.623725 0.066
110 -175681. 0.00000e+00 3.45995 0.072
120 53604.2 0.00000e+00 2.89435 0.077
130 100368. 0.00000e+00 0.634687 0.082
140 140687. 3.52429e-12 6.98551e-12 0.087
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -263909. FCRD inf 0.091
3 4 -63253.9 DDRD inf 0.140
Knitro deduced that the problem is non-convex.
143 144 -31647.8 FCRD inf 0.507
174 175 -5840.98 FCRD inf 0.577
301 283 17066.2 FCRD inf 0.872
635 485 42873.0 FCRD inf 1.812
7830 931 42873.0 inf 44.144
10110 1000 68679.8 FCRD inf 58.651
15769 1046 68679.8 inf 94.559
16388 1058 68679.8 inf 98.049
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 6.86798476295592263e+04
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (776.781s)
# 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 = 16774 (777.654s)
Total program time (secs) = 98.05176 (782.350 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 5 / 1 / 0.230s
Rounding heuristic = 357 / 16 / 0.674s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 5 / 0.210s
===========================================================================
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 50 80.7% $249,807
12 52 80.7% $190,398
13 53 79.8% $108,081
14 57 81.0% $68,680
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.