Internals

BatchedNumber{T}

Equivalent to Union{T, AbstractVector{T}} for a number type T. Represents a quantity which is scalar without batching, and holds one value per instance otherwise.

Combine such quantities with BangBang.broadcast!!(f, dest, args...), which writes into dest when batched and returns a fresh number otherwise, so the result must always be used.

ConstraintMatrix

Fields

• A::SparseArrays.AbstractSparseMatrix{T, Ti} where {T<:Number, Ti<:Integer}

• At::SparseArrays.AbstractSparseMatrix{T, Ti} where {T<:Number, Ti<:Integer}

ConvergenceStats

Fields

• err::CoolPDLP.KKTErrors: current KKT error

• starting_time::Float64: time at which the algorithm started, in seconds

• time_elapsed::Float64: time elapsed since the algorithm started, in seconds

• kkt_passes::Int64: number of multiplications by both the KKT matrix and its transpose

• termination_status::CoolPDLP.TerminationStatus: termination stats (should be STILL_RUNNING until the algorithm actually terminates)

• error_history::Array{Tuple{Int64, CoolPDLP.KKTErrors{T}}, 1} where T<:(Union{AbstractVector{T}, T} where T<:Number)

ConversionParameters{T,Ti,M}

Type parameters

• T: floating point type to convert values to
• Ti: integer type to convert indices to
• M: matrix constructor to use on the constraints

Fields

• backend::KernelAbstractions.Backend: CPU or GPU backend used for computations

GenericParameters

Fields

• show_progress::Bool: whether to show a progress bar

• check_every::Int64: frequency of restart or termination checks

• record_error_history::Bool: whether or not to record error evolution

PDHGState

Fields

• sol::PrimalDualSolution: current solution

• sol_last::PrimalDualSolution: last solution

• step_sizes::CoolPDLP.StepSizes{S} where {T<:Number, S<:Union{AbstractVector{T}, T}}: step sizes

• scratch::CoolPDLP.Scratch: scratch space

• stats::CoolPDLP.ConvergenceStats{S} where {T<:Number, S<:Union{AbstractVector{T}, T}}: convergence stats

PDLPState

Fields

• sol::PrimalDualSolution: current solution

• sol_last::PrimalDualSolution: last solution

• sol_avg::PrimalDualSolution: current average solution

• sol_avg_last::PrimalDualSolution: last average solution

• sol_restart::PrimalDualSolution: solution from last restart

• step_sizes::CoolPDLP.StepSizes{S} where {T<:Number, S<:Union{AbstractVector{T}, T}}: step sizes

• scratch::CoolPDLP.Scratch: scratch space

• iteration::CoolPDLP.IterationCounter: iteration counter

• restart_stats::CoolPDLP.RestartStats{S} where {T<:Number, S<:Union{AbstractVector{T}, T}}: restart stats

• stats::CoolPDLP.ConvergenceStats{S} where {T<:Number, S<:Union{AbstractVector{T}, T}}: convergence stats

Preconditioner

Fields

• D1::LinearAlgebra.Diagonal{T, V} where {T<:Number, V<:DenseVector{T}}: left preconditioner

• D2::LinearAlgebra.Diagonal{T, V} where {T<:Number, V<:DenseVector{T}}: right preconditioner

PreconditioningParameters

Fields

• chambolle_pock_alpha::Any: norm parameter in the Chambolle-pock preconditioner

• ruiz_iter::Int64: iteration parameter in the Ruiz preconditioner

RestartParameters

Fields

• sufficient_decay::Number: restart criterion: sufficient decay in normalized duality gap

• necessary_decay::Number: restart criterion: necessary decay

• artificial_decay::Number: restart criterion: long inner loop

• batch_aggregation::Any: how the per-instance absolute errors are reduced to the single restart decision shared by the batch

RestartStats

Fields

• restart_from_avg::Union{Bool, AbstractVector{Bool}}: whether to restart from the average solution, column by column

• err_current::CoolPDLP.KKTErrors: KKT errors of the current solution

• err_avg::CoolPDLP.KKTErrors: KKT errors of the current average solution

• err_last::CoolPDLP.KKTErrors: KKT errors of the last solution

• err_avg_last::CoolPDLP.KKTErrors: KKT errors of the last average solution

• err_restart::CoolPDLP.KKTErrors: KKT errors of the solution at the last restart

• abs_candidate::Union{AbstractVector{T}, T} where T<:Number: absolute error of the restart candidate

• abs_candidate_last::Union{AbstractVector{T}, T} where T<:Number: absolute error of the previous restart candidate

• abs_restart::Union{AbstractVector{T}, T} where T<:Number: absolute error at the last restart

StepSizeParameters

Fields

• invnorm_scaling::Number: scaling of the inverse spectral norm of A when defining the non-adaptive step size

• primal_weight_damping::Number: primal weight update damping

• zero_tol::Number: tolerance in absolute comparisons to zero

StepSizes

Fields

• η::Union{AbstractVector{T}, T} where T<:Number: step size

• η_sum::Union{AbstractVector{T}, T} where T<:Number: cumulated step size since last restart

• ω::Union{AbstractVector{T}, T} where T<:Number: primal weight

Symmetrized

Represent a symmetric matrix Kᵀ * K lazily.

TerminationParameters

Fields

• termination_reltol::Number: tolerance on KKT relative errors to decide termination

• max_kkt_passes::Int64: maximum number of multiplications by both the KKT matrix K and its transpose Kᵀ

• time_limit::Float64: time limit in seconds

TerminationStatus

Enum for the various ways that an algorithm can terminate.

Possible values:

• OPTIMAL
• TIME_LIMIT
• ITERATION_LIMIT
• STILL_RUNNING

absolute!!(dest, err, ω)

Compute the absolute KKT error for primal weight ω, column by column, into dest.

batch_sizes(c, lv, uv, lc, uc)

Return the number of instances carried by each field of a MILP which can be batched, 1 meaning shared by the whole batch.

batched_all(f, args...)

Reduce the per-instance conditions f(args...) to a single decision for the whole batch.

batched_expand(x, val)

Return val itself if the array x is not batched, or one copy of val per instance otherwise.

batched_mean(val)

Average a per-instance quantity over all the instances, yielding a single number.

batched_select!(sol, cond, sol_other)

Overwrite the columns of sol for which cond holds with those of sol_other.

batched_similar(val)

Return an uninitialized per-instance quantity with the same shape as val.

batched_zeros(x, n, nbinstances, Val(batched))

Allocate a zeroed vector of length n with the same array type as x, or a matrix holding one such column per instance when batched is true.

Batching is passed as a Val because the number of instances is only known at run time, while the shape of the result must be inferrable.

best_error!!(abs_err, err1, err2, scratch, sol1, sol2, milp, ω)

Fill err1 and err2 with the KKT errors of sol1 and sol2, then keep the smaller of their absolute errors, column by column, in abs_err.

Return abs_err together with both absolute errors, which live in the scratch space and stay valid only until the next call.

check_mul_dims(c, A, b)

Throw a DimensionMismatch unless c, A and b have compatible sizes for mul!(c, A, b, α, β), i.e. size(c, 1) == size(A, 1) and size(b, 1) == size(A, 2). A need not be an AbstractMatrix, only support size, which covers matrix-free operators like Symmetrized.

coldot(a, b)

Return the scalar product of a and b, or one scalar product per column if either is batched.

colnorm!!(dest, x)

Compute the Euclidean norm of x, or one norm per column if x is batched, into dest.

Unlike colnorm, the batched (AbstractMatrix) method computes sqrt(sum(abs2, ...)) directly instead of LinearAlgebra.norm's scaled, overflow-safe algorithm: it needs to stay a single allocation-free, GPU-broadcastable reduction, since it runs every iteration on the hot path (see primal_weight_update!! and kkt_errors!). This means colnorm!! can over/underflow on badly scaled columns where colnorm would not; that tradeoff is intentional here, since the values it norms are primal-dual residuals that are not expected to approach the extremes of the floating-point range in practice.

colnorm(x)

Return the Euclidean norm of x, or one norm per column if x is batched.

colsum!!(dest, x)

Compute the sum of x, or one sum per column if x is batched, into dest.

combine(l, u)

Return the largest finite absolute value between the two bounds, or zero if neither is finite.

common_backend(args...)

Return the common GPU backend of several arguments, if it exists, and throw an error otherwise.

instance_num(val, i)

Extract the value of val for the i-th instance of the batch.

kkt_errors!(err, scratch, sol, milp)

Fill err with the KKT errors of sol, one value per column of the batch.

primal_weight_update!!(scratch, step_sizes, sol_cand, sol_restart, params)

Compute the new primal weight, column by column, into step_sizes.ω.

progress_value(rel)

Format a relative error for the progress display: the value itself for a single instance, the maximum and mean over the instances for a batch.

The two summaries are printed in fixed width so that they line up across the progress rows.

proj_multiplier(λ, l, u)

Project λ onto the feasible space of the (double) Lagrange multiplier λ⁺ - λ⁻ associated with the constraint l ≤ x ≤ u, where l and/or u might be infinite.

relative!!(dest, err)

Compute the largest relative KKT error, column by column, into dest.

safeprod_left(left, right)

Compute left * right, except that right is forced to zero whenever left is infinite.

This is used to evaluate terms like l * y⁺ in the dual objective, where l is a (possibly infinite) constraint/variable bound and y⁺ its associated Lagrange multiplier. The PDHG update and proj_multiplier guarantee that the multiplier paired with an infinite bound is mathematically zero, but not necessarily exactly zero in floating point (e.g. a free row's multiplier is computed as a σ/inv(σ) round-trip that can leave a tiny nonzero residual). Checking iszero(right) instead of always zeroing out would let such residuals turn into ±Inf (and, once several rows are summed, Inf - Inf = NaN) even though nothing is actually wrong with the solution.

select_errors!!(dest, cond, err_true, err_false)

Fill dest, column by column, with the errors of err_true where cond holds and those of err_false elsewhere.

set_eltype(T, milp)

Change the element type of floating-point containers inside milp to T.

set_indtype(Ti, milp)

Change the element type of integer containers inside milp to Ti.

set_matrix_type(::Type{M}, milp)

Convert the sparse matrices inside milp using constructor M.

should_restart(stats, iteration, params)

Decide whether the whole batch restarts, based on an aggregate of the per-column fixed-point residuals.

Since every instance of the batch restarts at the same time, the three usual criteria (sufficient decay, necessary decay without local progress, long inner loop) are applied to params.batch_aggregation (the mean by default) of the per-column absolute KKT errors instead of requiring each column to agree.

sort_rows_columns(milp)

Return a new MILP where the constraint matrix has been permuted by order of increasing column and row density.

spectral_norm(K, Kᵀ)

Compute the spectral norm of K with the power method from IterativeSolvers.jl.

termination_status!!(dest, stats, params)

Decide how the algorithm terminates, using dest as scratch space for the relative errors.