import math
from dataclasses import dataclass
from plot import draw_comparison, draw_layout, draw_layouts
from report import report_counts, report_layout
@dataclass
class Field:
width: float
length: float
segment_length: float
min_segments: int
max_segments: int
machine_cost: float
segment_cost: float
operating_cost: float
margin: float
@property
def area(self):
return self.width * self.length
@dataclass
class Layout:
npv: float
x: list
y: list
segments: list
@property
def num_machines(self):
return len(self.segments)
def radius(field, segments):
return segments * field.segment_length
def covered_area(field, segments):
return sum(math.pi * radius(field, s) ** 2 for s in segments)
def coverage(field, layout):
return covered_area(field, layout.segments) / field.area
def net_present_value(field, segments):
margin = covered_area(field, segments) * field.margin
machines_cost = len(segments) * field.machine_cost
segments_cost = sum(s - 1 for s in segments) * field.segment_cost
return margin - machines_cost - segments_cost - field.operating_costPivot Irrigators
Lay out centre-pivot irrigation machines in a field to maximize the net present value of the investment, a circle-packing problem with discrete radii.
Introduction
We consider the problem of designing the layout of center-pivot irrigation machines in a field, which can be modeled as a circle packing problem.
Pivot irrigators are commonly used by crop farmers to supplement natural rainfall. For example, large areas of the mid-west USA are covered with these machines. The machines are almost always arranged in a simple grid pattern, which is not an efficient design in terms of coverage.
We consider the following situation:
- In a semi-arid region, only irrigated areas are productive.
- We consider a rectangular field in this region, with sides of 914.400 by 442.570 metres, with a total area of 40.4686 hectares (exactly 100 acres).
- The water distribution system of the field, composed of pivot irrigators, is worn out, so we need to replace it with the same type of machines.
- The machines are composed of a pivot mechanism and 20 metre long segments.
To maximize crop yield, it is important that we irrigate as much of the area as possible. However, we need to account for the cost of the machines, along with the operational and maintenance costs over their lifetime.
This example is based on this post.
Here is the grid layout of eight identical machines, and the layout the model finds for the same eight:
Both cover the same field with the same number of machines, and on the numbers below the grid is not merely worse. It loses money. Letting the machines differ in size and sit where they fit turns that loss into a profit.
Investment characteristics
Each machine costs $43,606 to purchase, install and for its maintenance over 15 years (its expected lifetime). A machine consists of the pivot mechanism and a single 20 metre long built-in segment.
Additional 20 metre long segments cost $15,803 each all included. A machine may have up to a total of eight segments (including the built-in segment).
We have fixed operating costs of $2,009,094 for 15 years, covering costs for other machinery and staff associated with working the field.
The planned crop will yield an average gross margin of $10.268 per square metre per year, allowing for all variable costs (planting, harvesting, etc).
A positive Net Present Value (NPV) would indicate that this is a worthwhile investment, while a negative one would indicate that the investment is a loss.
Furthermore, we note that larger machines are more profitable. Specifically, the cost of a machine is a linear function of the number of segments, while the yield from a machine is a function of the coverage area, which increases with the square of the number of segments. Therefore, all else being equal, larger machines are better.
In particular, a machine with only one or two segments makes a loss, while larger machines make a positive contribution to the NPV. Therefore, we only consider machines with at least 3 segments (including the built-in segment).
Problem description
Input
- \(S_{\text{size}}\) the length of each irrigation machine segment
- \(S^{\text{min}}\) the minimum number of segments per machine
- \(S^{\text{max}}\) the maximum number of segments per machine
- \(W\) the width of the field
- \(L\) the length of the field
- \(C_{\text{operating}}\) the operating cost (over 15 years)
- \(C_{\text{machine}}\) the cost of each irrigation machine (all included)
- \(C_{\text{segment}}\) the cost of each additional irrigation machine segment (all included)
- \(Y\) the yield per square metre irrigated
Problem:
Create a layout by choosing:
- the number of machines
- the number of segments of each machine
- the position of each machine’s pivot in the field
such that:
- the circle covered by each machine is within the field’s boundaries
- the circles covered by two machines cannot overlap
Objective:
Maximize the overall NPV of our investment.
This is a variant of a circle packing problem, where the radii of the circles are decision variables that must take values in a discrete set.
Mixed-integer nonlinear model
We simplify the model by making the number of machines an exogenous input \(N\). Otherwise, we would need an additional binary variable for each machine to decide whether we use it or not, which would unnecessarily complicate the model. We can instead solve the model iteratively over a reasonable range for the number of machines.
For a given number of machines \(N\), the model needs to decide, for each machine, the number of segments and the position of the machine’s pivot.
Variables
- \(s_i \in \mathbb{N}\), \(S^{\text{min}} \le s_i \le S^{\text{max}}\), \(i = 1, \dots, N\), the number of segments of machine \(i\) (including the built-in segment)
- \(x_i \in \mathbb{R}\), \(i = 1, \dots, N\), the \(x\) position of machine \(i\)’s pivot
- \(y_i \in \mathbb{R}\), \(i = 1, \dots, N\), the \(y\) position of machine \(i\)’s pivot
Objective: maximize the NPV, i.e. the total yield of the irrigated areas minus the cost of the machines, the cost of the additional segments and the operating cost
\[ \max \quad \left( \sum_{i=1}^N \pi \cdot (S_{\text{size}} \cdot s_i)^2 \right) \cdot Y - N \cdot C_{\text{machine}} - \left( \sum_{i=1}^N (s_i - 1) \right) \cdot C_{\text{segment}} - C_{\text{operating}} \]
Note that the cost part of the NPV calculation is linear. But the yield is a function of the area covered by each machine, which depends on the squared number of segments of the machine: the objective is therefore nonlinear (quadratic).
Constraints
- Irrigation circles are within the field’s boundaries:
\[ \forall i = 1, \dots, N, \qquad S_{\text{size}} \cdot s_i \le x_i \le W - S_{\text{size}} \cdot s_i \]
\[ \forall i = 1, \dots, N, \qquad S_{\text{size}} \cdot s_i \le y_i \le L - S_{\text{size}} \cdot s_i \]
- Irrigation circles must not overlap, i.e. the distance between two pivots must be at least the sum of the radii of the two irrigation circles:
\[ \forall i, j = 1, \dots, N, \; i<j, \qquad (x_i - x_j)^2 + (y_i - y_j)^2 \ge \left( S_{\text{size}} \cdot (s_i + s_j) \right)^2 \]
These non-overlap constraints are nonconvex quadratic constraints, which makes this problem a nonconvex mixed-integer nonlinear program (MINLP).
Input data
A Field is the field and the money. It holds how big the field is, how long a segment is, how many segments a machine may carry, what a machine and a segment cost, what running the field costs, and what a square metre yields in a year. A Layout is where each machine stands and how many segments it carries, together with the net present value that layout earns.
net_present_value is the objective written out in plain code, so a layout that was never solved for can be priced the same way as one that was.
The field is 914.400 by 442.570 metres, machines are built from 20 metre segments and carry between 3 and 8 of them, and the costs and yield are the ones listed above, in dollars over the fifteen year lifetime. grid_layout is the arrangement farms actually use, four machines by two, every one the same size and as large as the spacing allows.
field = Field(
width=914.400,
length=442.570,
segment_length=20,
min_segments=3,
max_segments=8,
machine_cost=43606.07950630836,
segment_cost=15803.03975315418,
operating_cost=2009094.3111355049,
margin=10.268207333516287,
)
def grid_layout(field, segments=5):
reach = radius(field, segments)
columns = [reach + k * (field.width - 2 * reach) / 3 for k in range(4)]
rows = [reach, field.length - reach]
counts = [float(segments)] * (4 * len(rows))
x = [column for _ in rows for column in columns]
y = [row for row in rows for _ in columns]
return Layout(net_present_value(field, counts), x, y, counts)A layout is the field seen from above, each machine a disc as wide as its reach. The dashed rings inside a disc are its segments, so a bigger machine is both wider and more finely drawn, and the number at the center is how many it carries. Ground no disc covers is ground that earns nothing.
Eight machines on a grid is the arrangement to beat. It leaves the four corners, the gaps between neighbours and a strip right across the middle dry, and on these numbers it does not merely earn less than it could. It loses money.
report_layout(field, grid_layout(field))8 machines, net present value -$282,958, covering 62.1% of the field
machine segments reach x y covered share
------------------------------------------------------------------
1 5 100m 100.0 100.0 31,416 7.8%
2 5 100m 338.1 100.0 31,416 7.8%
3 5 100m 576.3 100.0 31,416 7.8%
4 5 100m 814.4 100.0 31,416 7.8%
5 5 100m 100.0 342.6 31,416 7.8%
6 5 100m 338.1 342.6 31,416 7.8%
7 5 100m 576.3 342.6 31,416 7.8%
8 5 100m 814.4 342.6 31,416 7.8%
Margin $2,580,682 less $348,849 of machines, $505,697 of segments,
$2,009,094 to operatedraw_layout(field, grid_layout(field), "Eight machines on a grid")Model implementation
import 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.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.029
1 -2.16662e+06 4168.94 0.883468 0.030
2 -2.26549e+06 1092.99 2.17355 0.030
3 -2.26807e+06 339.753 2.54056 0.030
4 -2.26491e+06 260.932 2.65815 0.031
5 -2.26283e+06 218.536 2.70606 0.031
6 -2.26142e+06 192.766 2.73660 0.031
7 -2.26055e+06 169.998 2.75323 0.032
8 -2.26013e+06 152.644 2.76265 0.032
9 -2.25975e+06 137.853 2.77337 0.033
10 -2.25951e+06 123.626 2.78079 0.033
11 -2.26022e+06 128.740 2.76929 0.033
12 -2.26036e+06 110.239 2.76954 0.034
13 -2.26062e+06 100.133 2.76746 0.034
14 -2.26147e+06 97.2033 2.75282 0.034
15 -2.26227e+06 86.6805 2.73710 0.035
16 -2.26340e+06 82.5117 2.71494 0.035
17 -2.26488e+06 68.6615 2.68155 0.035
18 -2.26605e+06 64.0655 2.65265 0.036
19 -2.26688e+06 55.3387 2.62733 0.036
20 -2.26779e+06 45.5852 2.59725 0.036
30 -2.23557e+06 9.53453 4.36023 0.040
40 -1.65424e+06 232.595 4.82700 0.043
50 -1.11012e+06 152.262 9.92205 0.045
60 -747658. 0.00000e+00 18.6520 0.047
70 -365828. 0.00000e+00 32.0869 0.050
80 -60523.5 0.00000e+00 2.34387 0.052
90 71731.8 24.9194 1.17656 0.054
100 224247. 3.60164e-06 2.64885e-06 0.056
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -47797.2 FCRD inf 0.061
1 2 26723.6 LS inf 0.065
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.086
31 31 201572. FCRD inf 0.127
39 39 276093. LS inf 0.131
76 61 324807. FCRD inf 0.180
1759 334 353513. FCRD inf 2.473
3825 386 353513. FCRD inf 5.874
7909 466 353513. inf 12.649
15900 599 353513. inf 24.072
16386 602 353513. inf 24.724
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 (193.330s)
# 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 (193.727s)
Total program time (secs) = 24.72617 (197.105 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.037s
Rounding heuristic = 278 / 10 / 0.380s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 7 / 0.103s
===========================================================================
Show the full outputHide the full output
report_layout(field, layout_8)8 machines, net present value $353,513, covering 78.6% of the field
machine segments reach x y covered share
------------------------------------------------------------------
1 4 80m 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.002
9 -1.97529e+06 1.99335 5.37828 0.002
10 -1.90748e+06 1.92130 6.61155 0.002
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.003
20 -1.17540e+06 311.235 5.56185 0.003
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.005
200 0 5678.31 5678.31 0.00% 0.514
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.480s)
# 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.480s)
Total program time (secs) = 0.51428 (0.555 CPU time)
Time spent in evaluations (secs) = 0.00000
Cuts statistics (gen / add)
---------------------------
Knapsack cuts = 0 / 0
Mixed-integer rounding cuts = 0 / 0
Flow-cover cuts = 0 / 0
Probing cuts = 0 / 0
Heuristics statistics (calls / successes / time)
------------------------------------------------
Feasibility pump = 0 / 0 / 0.000s
Rounding heuristic = 0 / 0 / 0.000s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 5 / 4 / 0.009s
===========================================================================
=======================================
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.001
1 -2.08787e+06 4168.14 0.807571 0.001
2 -2.13661e+06 1170.59 1.70845 0.001
3 -2.13934e+06 412.886 2.46895 0.001
4 -2.13865e+06 315.701 2.53609 0.001
5 -2.13823e+06 268.085 2.56761 0.002
6 -2.13791e+06 232.825 2.58594 0.002
7 -2.13772e+06 200.157 2.59659 0.002
8 -2.13774e+06 170.926 2.59645 0.002
9 -2.13788e+06 141.808 2.58998 0.002
10 -2.13823e+06 119.556 2.57123 0.002
11 -2.13883e+06 23.7446 2.53085 0.002
12 -2.13910e+06 2.50803 2.50803 0.003
13 -2.13961e+06 52.0198 1.67954 0.003
14 -2.13700e+06 55.2317 8.91996 0.003
15 -2.13410e+06 20.6321 6.36662 0.003
16 -2.12915e+06 36.5047 5.57905 0.003
17 -2.11475e+06 16.0126 4.18197 0.003
18 -2.05463e+06 1.93271 4.66114 0.003
19 -1.97220e+06 1.87812 6.75993 0.003
20 -1.81578e+06 1.82578 9.63717 0.003
30 -393714. 0.00000e+00 16.7042 0.004
40 20287.4 0.00000e+00 6.03009 0.005
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -56630.4 FCRD inf 0.008
3 4 43697.2 FCRD inf 0.015
Knitro deduced that the problem is non-convex.
13 10 46596.8 FCRD inf 0.036
6442 5 46596.8 inf 3.608
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 (23.965s)
# 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 (24.042s)
Total program time (secs) = 3.91559 (25.230 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.012s
Rounding heuristic = 32 / 6 / 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.
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.002
5 -2.17028e+06 262.835 2.59699 0.002
6 -2.17000e+06 235.623 2.61645 0.003
7 -2.16973e+06 210.443 2.63277 0.003
8 -2.16955e+06 181.069 2.64461 0.003
9 -2.16965e+06 172.926 2.64238 0.003
10 -2.16971e+06 154.353 2.64316 0.003
11 -2.16997e+06 160.791 2.63243 0.003
12 -2.17021e+06 151.746 2.62253 0.004
13 -2.17034e+06 132.233 2.61898 0.004
14 -2.17108e+06 132.136 2.57786 0.004
15 -2.17123e+06 131.574 2.56734 0.004
16 -2.17148e+06 130.268 2.54818 0.004
17 -2.17118e+06 118.390 2.53168 0.004
18 -2.16638e+06 88.2926 2.50191 0.004
19 -2.16220e+06 80.8362 2.47693 0.005
20 -2.11676e+06 54.5914 3.93852 0.005
30 -1.66705e+06 511.526 6.17690 0.006
40 -747510. 0.00000e+00 56.5714 0.008
50 -457676. 0.00000e+00 11.3599 0.009
60 4426.01 0.00000e+00 30.8072 0.010
70 198100. 0.00000e+00 7.90316e-05 0.011
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -15711.9 FCRD inf 0.013
Knitro deduced that the problem is non-convex.
7 8 159137. DDRD inf 0.030
26 16 159137. FCRD inf 0.060
37 20 159137. FCRD inf 0.074
7940 76 159137. inf 5.385
15936 101 159137. inf 11.448
16384 107 159137. inf 11.795
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 (90.094s)
# 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 (90.288s)
Total program time (secs) = 11.80543 (93.151 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.016s
Rounding heuristic = 131 / 7 / 0.185s
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.008
1 -2.12725e+06 4168.71 0.825003 0.008
2 -2.20109e+06 1116.69 2.55192 0.009
3 -2.20372e+06 380.694 2.52326 0.009
4 -2.20162e+06 301.184 2.63173 0.010
5 -2.20027e+06 253.939 2.67807 0.010
6 -2.19910e+06 225.481 2.71462 0.010
7 -2.19822e+06 197.827 2.73975 0.011
8 -2.19798e+06 157.203 2.74807 0.011
9 -2.19794e+06 116.356 2.75150 0.012
10 -2.20015e+06 117.185 2.69775 0.012
11 -2.20058e+06 94.9885 2.68577 0.013
12 -2.20151e+06 69.9709 2.65798 0.013
13 -2.20216e+06 13.0110 2.63593 0.014
14 -2.20472e+06 7.96762 2.48351 0.014
15 -2.20438e+06 9.23414 4.46600 0.014
16 -2.20397e+06 4.37366 5.31747 0.015
17 -2.19688e+06 99.4994 22.9034 0.015
18 -2.19168e+06 23.3843 2.59924 0.016
19 -2.18320e+06 83.8034 4.79067 0.016
20 -2.16916e+06 25.9151 2.47731 0.016
30 -1.60291e+06 368.494 49.1903 0.019
40 -423944. 2.22508e-02 9.81663 0.021
50 -4110.85 0.00000e+00 2.51589 0.024
60 115708. 1.30967e-10 9.99592e-11 0.026
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 48113.8 FCRD inf 0.030
Knitro deduced that the problem is non-convex.
15 16 200055. FCRD inf 0.072
7754 197 200055. inf 7.571
15445 219 200055. inf 14.878
16389 220 200055. inf 15.703
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 (121.237s)
# 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 (121.490s)
Total program time (secs) = 15.70454 (124.380 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.277s
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.
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.018
Knitro deduced that the problem is non-convex.
3 4 66125.2 FCRD inf 0.028
7 8 140646. LS inf 0.036
13 14 169352. FCRD inf 0.041
28 29 189360. FCRD inf 0.054
36 37 212267. FCRD inf 0.061
48 47 240974. FCRD inf 0.069
145 113 312595. FCRD inf 0.128
7766 197 312595. inf 9.205
15551 253 312595. inf 18.521
16388 260 312595. inf 19.560
EXIT: Node limit reached. Integer feasible point found.
Final Statistics for MIP
------------------------
Final objective value = 3.12594833578581456e+05
Final bound value = +inf
Final optimality gap (abs / rel) = inf / inf
# of root cutting plane rounds = 1
# of restarts = 0
# of nodes processed = 16388 (151.783s)
# 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 (152.001s)
Total program time (secs) = 19.56103 (154.770 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.011s
Rounding heuristic = 161 / 14 / 0.224s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 5 / 0.059s
===========================================================================
=======================================
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.002
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.004
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.005
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.006
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.007
30 -2.23557e+06 9.53453 4.36023 0.010
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.017
70 -365828. 0.00000e+00 32.0869 0.019
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.028
1 2 26723.6 LS inf 0.032
Knitro deduced that the problem is non-convex.
3 4 129951. DDRD inf 0.048
31 31 201572. FCRD inf 0.081
39 39 276093. LS inf 0.087
76 61 324807. FCRD inf 0.134
1759 334 353513. FCRD inf 2.958
3825 386 353513. FCRD inf 7.159
7909 466 353513. inf 14.671
15900 599 353513. inf 26.792
16386 602 353513. inf 27.448
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 (211.569s)
# 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 (211.987s)
Total program time (secs) = 27.44945 (215.485 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.419s
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.002
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.003
5 -2.29362e+06 154.106 2.71494 0.003
6 -2.29202e+06 129.462 2.74536 0.004
7 -2.29101e+06 114.596 2.76314 0.004
8 -2.29033e+06 94.6734 2.77424 0.005
9 -2.29020e+06 58.7190 2.77658 0.005
10 -2.29405e+06 74.2433 2.71926 0.005
11 -2.29449e+06 58.6296 2.71225 0.006
12 -2.29534e+06 41.7538 2.69742 0.006
13 -2.29655e+06 2.67403 2.67403 0.006
14 -2.29757e+06 9.85655 2.65300 0.007
15 -2.29832e+06 14.5454 2.63608 0.007
16 -2.29907e+06 18.9549 2.61714 0.007
17 -2.29986e+06 19.1783 2.59476 0.008
18 -2.30040e+06 18.9224 2.57703 0.008
19 -2.30103e+06 68.2573 2.55290 0.009
20 -2.30138e+06 40.6419 2.53644 0.010
30 -2.27459e+06 1.94848 25.0990 0.013
40 -2.21166e+06 1.65880 40.6006 0.016
50 -1.16443e+06 1.69438e-02 7.01353 0.019
60 -292585. 0.00000e+00 7.57076 0.022
70 -138617. 0.00000e+00 0.665284 0.024
80 -62880.1 0.00000e+00 6.88877e-03 0.027
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -130114. FCRD inf 0.030
Knitro deduced that the problem is non-convex.
2 3 -55592.7 LS inf 0.040
5 6 142163. FCRD inf 0.051
11 11 216684. FCRD inf 0.063
13 13 251189. FCRD inf 0.072
72 57 291205. FCRD inf 0.167
240 127 322811. FCRD inf 0.373
397 174 322811. FCRD inf 0.542
7713 524 322811. inf 15.890
15476 620 322811. inf 31.722
16388 636 322811. inf 33.641
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 (264.418s)
# 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 (264.794s)
Total program time (secs) = 33.64264 (268.270 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.003s
Rounding heuristic = 293 / 13 / 0.415s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 14 / 6 / 0.093s
===========================================================================
=======================================
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.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.009
17 -2.32234e+06 63.0898 2.76009 0.009
18 -2.32347e+06 57.5711 2.74661 0.010
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.465961 72.0761 0.019
50 -343249. 0.00000e+00 8.51262 0.022
60 -4005.83 0.00000e+00 6.33967 0.026
70 80714.7 0.00000e+00 0.601606 0.029
80 104582. 0.00000e+00 0.333255 0.032
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 59846.6 FCRD inf 0.036
Knitro deduced that the problem is non-convex.
23 24 76954.6 FCRD inf 0.093
38 39 102761. FCRD inf 0.114
46 47 160174. FCRD inf 0.129
148 137 208888. FCRD inf 0.284
187 170 208888. FCRD inf 0.346
234 209 231795. FCRD inf 0.415
1540 640 254703. FCRD inf 2.881
1767 654 312116. FCRD inf 3.499
7092 732 332123. FCRD inf 19.240
7455 730 332123. inf 20.182
15257 776 332123. inf 39.055
16386 777 332123. inf 41.989
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 (330.927s)
# 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 (331.353s)
Total program time (secs) = 41.99109 (335.495 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.031s
Rounding heuristic = 300 / 15 / 0.449s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 4 / 0.124s
===========================================================================
=======================================
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.003
1 -2.22568e+06 4169.14 1.24444 0.003
2 -2.36204e+06 1075.25 2.18026 0.004
3 -2.36435e+06 316.479 2.55796 0.004
4 -2.35903e+06 195.818 2.68101 0.005
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.006
8 -2.35371e+06 57.8037 2.77449 0.006
9 -2.35922e+06 105.574 2.70194 0.007
10 -2.35970e+06 76.7210 2.69532 0.007
11 -2.36024e+06 5.71021 2.68824 0.008
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.009
15 -2.35419e+06 21.2098 5.68532 0.009
16 -2.35044e+06 29.0164 4.85545 0.010
17 -2.34107e+06 61.5293 2.53126 0.010
18 -2.32874e+06 47.4339 2.70344 0.011
19 -2.29618e+06 31.7195 3.99136 0.011
20 -2.23371e+06 31.6614 5.45247 0.011
30 -2.15081e+06 1.21544 61.5440 0.017
40 -1.78506e+06 0.372527 85.7465 0.021
50 -1.14331e+06 0.00000e+00 8.43256 0.026
60 -295020. 0.00000e+00 3.82340 0.029
70 -159347. 0.00000e+00 2.28722 0.032
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -223125. FCRD inf 0.040
Knitro deduced that the problem is non-convex.
3 4 -131496. FCRD inf 0.069
7 8 -102790. LS inf 0.088
35 36 46251.9 FCRD inf 0.154
50 49 120773. FCRD inf 0.196
62 61 169487. FCRD inf 0.222
136 120 172386. FCRD inf 0.382
206 168 175286. FCRD inf 0.530
361 261 178186. FCRD inf 0.879
1870 582 201093. FCRD inf 5.449
6476 602 201093. inf 23.049
12708 990 249807. FCRD inf 44.991
12842 994 249807. inf 45.439
16384 1017 249807. inf 58.410
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 (461.726s)
# 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 (462.386s)
Total program time (secs) = 58.41212 (466.746 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.125s
Rounding heuristic = 368 / 14 / 0.578s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 17 / 7 / 0.169s
===========================================================================
=======================================
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.003
1 -2.24537e+06 4169.21 0.909667 0.003
2 -2.39422e+06 1071.62 2.18168 0.004
3 -2.39643e+06 312.026 2.56144 0.004
4 -2.39125e+06 218.641 2.68525 0.005
5 -2.38771e+06 175.826 2.73442 0.005
6 -2.38589e+06 150.937 2.75803 0.006
7 -2.38474e+06 130.566 2.76823 0.006
8 -2.38390e+06 114.545 2.77471 0.007
9 -2.38326e+06 102.220 2.78188 0.007
10 -2.38316e+06 91.6032 2.78313 0.008
11 -2.38388e+06 95.5451 2.77599 0.008
12 -2.38371e+06 85.8699 2.77754 0.009
13 -2.38376e+06 77.1747 2.77662 0.009
14 -2.38383e+06 69.3538 2.77515 0.010
15 -2.38403e+06 62.3258 2.77216 0.010
16 -2.38433e+06 56.6964 2.76791 0.011
17 -2.38480e+06 51.6220 2.76186 0.011
18 -2.38547e+06 47.2041 2.75444 0.012
19 -2.38752e+06 48.7163 2.73194 0.014
20 -2.38905e+06 17.6810 2.71391 0.015
30 -2.38111e+06 8.95845 6.32155 0.020
40 -2.32117e+06 2.10445 93.9809 0.027
50 -2.34003e+06 1.81585 34.9505 0.032
60 -2.15105e+06 1.14059 54.6782 0.036
70 -1.19409e+06 0.00000e+00 8.05165 0.040
80 -352081. 0.00000e+00 0.192569 0.045
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -434475. FCRD inf 0.049
Knitro deduced that the problem is non-convex.
3 4 38456.4 FCRD inf 0.076
53 42 67162.9 FCRD inf 0.235
155 124 115877. FCRD inf 0.501
185 148 141684. FCRD inf 0.569
193 152 167491. FCRD inf 0.581
6801 672 167491. inf 28.256
9517 805 190398. FCRD inf 40.139
13668 953 190398. inf 57.462
16388 1058 190398. inf 68.635
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 (543.076s)
# 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 (543.778s)
Total program time (secs) = 68.63719 (548.394 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.202s
Rounding heuristic = 377 / 10 / 0.562s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 4 / 0.117s
===========================================================================
=======================================
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.003
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.005
4 -2.42217e+06 211.140 2.69012 0.005
5 -2.41793e+06 166.044 2.73688 0.006
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.009
11 -2.41154e+06 87.0391 2.79196 0.009
12 -2.41177e+06 76.7426 2.79024 0.010
13 -2.41281e+06 55.7265 2.78149 0.010
14 -2.41456e+06 21.6990 2.76571 0.011
15 -2.41862e+06 31.4924 2.72643 0.011
16 -2.42001e+06 2.71057 2.71057 0.012
17 -2.42249e+06 17.2079 2.68177 0.013
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.035
70 -1.34335e+06 1.62220e-02 9.73970 0.041
80 -486042. 0.00000e+00 1.58612 0.045
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.060
Knitro deduced that the problem is non-convex.
27 28 -75466.0 FCRD inf 0.193
58 59 -52558.8 FCRD inf 0.255
81 82 -945.132 FCRD inf 0.312
96 97 21962.1 FCRD inf 0.324
159 158 76475.3 FCRD inf 0.454
438 373 79375.0 FCRD inf 0.955
1160 733 79375.0 FCRD inf 2.819
2091 1035 108081. FCRD inf 5.863
7766 1146 108081. inf 36.174
11280 1202 108081. FCRD inf 53.384
15550 1352 108081. inf 74.383
16389 1388 108081. inf 78.408
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 (619.963s)
# 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 (620.843s)
Total program time (secs) = 78.41075 (626.011 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.144s
Rounding heuristic = 508 / 20 / 0.821s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 16 / 4 / 0.191s
===========================================================================
=======================================
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.005
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.007
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.010
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.012
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.017
20 -2.45604e+06 175.298 2.66331 0.018
30 -2.46578e+06 281.448 3.56960 0.025
40 -2.35206e+06 223.191 10.4376 0.033
50 -2.17856e+06 1.15996 8.11115 0.039
60 -1.73550e+06 3.33520 3.29668 0.044
70 -1.49947e+06 0.164717 18.0433 0.049
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.065
110 -175681. 0.00000e+00 3.45995 0.071
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.086
Tree search
-----------
Nodes Best solution Best bound Gap Time
Expl | Unexpl value value (secs)
--------------- ------------- ---------- --- ------
1 2 -263909. FCRD inf 0.089
3 4 -63253.9 DDRD inf 0.138
Knitro deduced that the problem is non-convex.
143 144 -31647.8 FCRD inf 0.464
174 175 -5840.98 FCRD inf 0.520
301 283 17066.2 FCRD inf 0.813
635 485 42873.0 FCRD inf 1.748
7830 931 42873.0 inf 42.923
10110 1000 68679.8 FCRD inf 57.562
15769 1046 68679.8 inf 91.160
16388 1058 68679.8 inf 95.420
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 (756.122s)
# 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 (756.946s)
Total program time (secs) = 95.42374 (762.386 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.223s
Rounding heuristic = 357 / 16 / 0.622s
MPEC heuristic = 0 / 0 / 0.000s
Local search heuristic = 13 / 5 / 0.211s
===========================================================================
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.