22279069886

Committed 22 Feb 2026 02:32PM UTC coverage: 89.311% (+0.3%) from 89.013%

Build # 22279069886

Build Type

Pull #38

github

Committed by

web-flow

Commit Message

Merge bae50547e into e13878911

Pull Request Pull Request #38: [WIP] Speedup

Coverage Stats

1281 of 1432 branches covered (89.46%)

Branch coverage included in aggregate %.

181 of 193 new or added lines in 10 files covered. (93.78%)

67 existing lines in 7 files now uncovered.

3983 of 4462 relevant lines covered (89.26%)

6008.65 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

77.35

/src/core/Activity.c

/*
 * Copyright 2025 Daniel Cederberg
 *
 * This file is part of the PSLP project (LP Presolver).
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "Activity.h"
#include "Bounds.h"
#include "Matrix.h"
#include "Memory_wrapper.h"
#include "Numerics.h"
#include "RowColViews.h"
#include "glbopts.h"

Activity *new_activities(const Matrix *A, const ColTag *col_tags,
                         const Bound *bounds)
{
    Activity *activities = (Activity *) ps_malloc(A->m, sizeof(Activity));
    RETURN_PTR_IF_NULL(activities, NULL);
    int i, j, start, end;
    int *cols = A->i;
    double *vals = A->x;

    for (i = 0; i < A->m; ++i)
    {
        Activity *act = activities + i;
        act->n_inf_min = 0;
        act->n_inf_max = 0;
        act->max = 0.0;
        act->min = 0.0;
        act->status = NOT_ADDED;

        start = A->p[i].start;
        end = A->p[i].end;

        // record infinite contributions
        for (j = start; j < end; ++j)
        {
            if (vals[j] > 0)
            {
                if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))
                {
                    act->n_inf_max++;
                }

                if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))
                {
                    act->n_inf_min++;
                }
            }
            else
            {
                if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))
                {
                    act->n_inf_max++;
                }

                if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))
                {
                    act->n_inf_min++;
                }
            }
        }

        // compute max act if it is useful
        if (act->n_inf_max == 0)
        {
            for (j = start; j < end; ++j)
            {
                if (vals[j] > 0)
                {
                    assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));
                    assert(!IS_POS_INF(bounds[cols[j]].ub));
                    act->max += vals[j] * bounds[cols[j]].ub;
                }
                else
                {
                    assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));
                    assert(!IS_NEG_INF(bounds[cols[j]].lb));
                    act->max += vals[j] * bounds[cols[j]].lb;
                }
            }
        }
#ifndef NDEBUG
        else
        {
            act->max = INVALID_ACT_DEBUG;
        }
#endif

        // compute min act if it is useful
        if (act->n_inf_min == 0)
        {
            for (j = start; j < end; ++j)
            {
                if (vals[j] > 0)
                {
                    assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));
                    assert(!IS_NEG_INF(bounds[cols[j]].lb));
                    act->min += vals[j] * bounds[cols[j]].lb;
                }
                else
                {
                    assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));
                    assert(!IS_POS_INF(bounds[cols[j]].ub));
                    act->min += vals[j] * bounds[cols[j]].ub;
                }
            }
        }
#ifndef NDEBUG
        else
        {
            act->min = INVALID_ACT_DEBUG;
        }
#endif
    }

    return activities;
}

void free_activities(Activity *activities)
{
    PS_FREE(activities);
}

void Activities_init(const Matrix *A, const ColTag *col_tags, const RowTag *row_tags,
                     const Bound *bounds, Activity *acts)
{

    for (int i = 0; i < A->m; ++i)
    {
        if (HAS_TAG(row_tags[i], R_TAG_INACTIVE))
        {
            DEBUG(acts[i].status = NOT_ADDED;);
            continue;
        }

        Activity_init(acts + i, A->x + A->p[i].start, A->i + A->p[i].start,
                      A->p[i].end - A->p[i].start, bounds, col_tags);
    }
}

void Activity_init(Activity *act, const double *vals, const int *cols, int len,
                   const Bound *bounds, const ColTag *col_tags)
{
    act->n_inf_min = 0;
    act->n_inf_max = 0;
    act->max = 0.0;
    act->min = 0.0;
    act->status = NOT_ADDED;
    int j;

    // record infinite contributions
    for (j = 0; j < len; ++j)
    {
        if (vals[j] > 0)
        {
            if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))
            {
                act->n_inf_max++;
            }

            if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))
            {
                act->n_inf_min++;
            }
        }
        else
        {
            if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))
            {
                act->n_inf_max++;
            }

            if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))
            {
                act->n_inf_min++;
            }
        }
    }

    // compute max act if it is useful
    if (act->n_inf_max == 0)
    {
        for (j = 0; j < len; ++j)
        {
            if (vals[j] > 0)
            {
                assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));
                assert(!IS_POS_INF(bounds[cols[j]].ub));
                act->max += vals[j] * bounds[cols[j]].ub;
            }
            else
            {
                assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));
                assert(!IS_NEG_INF(bounds[cols[j]].lb));
                act->max += vals[j] * bounds[cols[j]].lb;
            }
        }
    }
#ifndef NDEBUG
    else
    {
        act->max = INVALID_ACT_DEBUG;
    }
#endif

    // compute min act if it is useful
    if (act->n_inf_min == 0)
    {
        for (j = 0; j < len; ++j)
        {
            if (vals[j] > 0)
            {
                assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));
                assert(!IS_NEG_INF(bounds[cols[j]].lb));
                act->min += vals[j] * bounds[cols[j]].lb;
            }
            else
            {
                assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));
                assert(!IS_POS_INF(bounds[cols[j]].ub));
                act->min += vals[j] * bounds[cols[j]].ub;
            }
        }
    }
#ifndef NDEBUG
    else
    {
        act->min = INVALID_ACT_DEBUG;
    }
#endif
}

double compute_min_act_tags(const double *vals, const int *cols, int len,
                            const Bound *bounds, const ColTag *col_tags)
{
    double min_act = 0.0;
    for (int j = 0; j < len; ++j)
    {
        if (vals[j] > 0)
        {
            if (!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))
            {
                assert(!IS_NEG_INF(bounds[cols[j]].lb));
                min_act += vals[j] * bounds[cols[j]].lb;
            }
        }
        else
        {
            if (!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))
            {
                assert(!IS_POS_INF(bounds[cols[j]].ub));
                min_act += vals[j] * bounds[cols[j]].ub;
            }
        }
    }
    return min_act;
}

double compute_max_act_tags(const double *vals, const int *cols, int len,
                            const Bound *bounds, const ColTag *col_tags)
{
    double max_act = 0.0;
    for (int j = 0; j < len; ++j)
    {
        if (vals[j] > 0)
        {
            if (!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))
            {
                assert(!IS_POS_INF(bounds[cols[j]].ub));
                max_act += vals[j] * bounds[cols[j]].ub;
            }
        }
        else
        {
            if (!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))
            {
                assert(!IS_NEG_INF(bounds[cols[j]].lb));
                max_act += vals[j] * bounds[cols[j]].lb;
            }
        }
    }
    return max_act;
}

double compute_min_act_no_tags(const double *vals, const int *cols, int len,
                               const Bound *bounds)
{
    double min_act = 0.0;
    for (int j = 0; j < len; ++j)
    {
        if (vals[j] > 0)
        {
            assert(!IS_NEG_INF(bounds[cols[j]].lb));
            min_act += vals[j] * bounds[cols[j]].lb;
        }
        else
        {
            assert(!IS_POS_INF(bounds[cols[j]].ub));
            min_act += vals[j] * bounds[cols[j]].ub;
        }
    }
    return min_act;
}

double compute_max_act_no_tags(const double *vals, const int *cols, int len,
                               const Bound *bounds)
{
    double max_act = 0.0;
    for (int j = 0; j < len; ++j)
    {
        if (vals[j] > 0)
        {
            assert(!IS_POS_INF(bounds[cols[j]].ub));
            max_act += vals[j] * bounds[cols[j]].ub;
        }
        else
        {
            assert(!IS_NEG_INF(bounds[cols[j]].lb));
            max_act += vals[j] * bounds[cols[j]].lb;
        }
    }
    return max_act;
}

double compute_min_act_one_tag(const double *vals, const int *cols, int len,
                               const Bound *bounds, int col_to_avoid)
{
    assert(col_to_avoid >= 0);
    double min_act = 0.0;
    for (int j = 0; j < len; ++j)
    {
        if (cols[j] == col_to_avoid)
        {
            continue;
        }

        if (vals[j] > 0)
        {
            assert(!IS_NEG_INF(bounds[cols[j]].lb));
            min_act += vals[j] * bounds[cols[j]].lb;
        }
        else
        {
            assert(!IS_POS_INF(bounds[cols[j]].ub));
            min_act += vals[j] * bounds[cols[j]].ub;
        }
    }
    return min_act;
}

double compute_max_act_one_tag(const double *vals, const int *cols, int len,
                               const Bound *bounds, int col_to_avoid)
{
    assert(col_to_avoid >= 0);
    double max_act = 0.0;
    for (int j = 0; j < len; ++j)
    {
        if (cols[j] == col_to_avoid)
        {
            continue;
        }

        if (vals[j] > 0)
        {
            assert(!IS_POS_INF(bounds[cols[j]].ub));
            max_act += vals[j] * bounds[cols[j]].ub;
        }
        else
        {
            assert(!IS_NEG_INF(bounds[cols[j]].lb));
            max_act += vals[j] * bounds[cols[j]].lb;
        }
    }
    return max_act;
}

Altered_Activity update_act_bound_change(Activity *act, double coeff,
                                         double old_bound, double new_bound,
                                         bool finite_bound, bool lower,
                                         const double *vals, const int *cols,
                                         int len, const Bound *bounds)
{
    // ---------------------------------------------------------------------
    //              If a lower bound has been updated
    // ---------------------------------------------------------------------
    if (lower)
    {
        if (coeff < 0)
        {
            if (act->n_inf_max == 0)
            {
                assert(finite_bound);
                act->max += (new_bound - old_bound) * coeff;
            }
            else if (!finite_bound)
            {
                act->n_inf_max--;

                if (act->n_inf_max == 0)
                {
                    act->max = compute_max_act_no_tags(vals, cols, len, bounds);
                }
            }

            return MAX_ALTERED;
        }
        else
        {
            if (act->n_inf_min == 0)
            {
                assert(finite_bound);
                act->min += (new_bound - old_bound) * coeff;
            }
            else if (!finite_bound)
            {
                act->n_inf_min--;

                if (act->n_inf_min == 0)
                {
                    act->min = compute_min_act_no_tags(vals, cols, len, bounds);
                }
            }
            return MIN_ALTERED;
        }
    }
    // ------------------------------------------------------------------------
    //                 If an upper bound has been updated
    // ------------------------------------------------------------------------
    else
    {
        if (coeff < 0)
        {
            if (act->n_inf_min == 0)
            {
                assert(finite_bound);
                act->min += (new_bound - old_bound) * coeff;
            }
            else if (!finite_bound)
            {
                act->n_inf_min--;

                if (act->n_inf_min == 0)
                {
                    act->min = compute_min_act_no_tags(vals, cols, len, bounds);
                }
            }
            return MIN_ALTERED;
        }
        else
        {
            if (act->n_inf_max == 0)
            {
                assert(finite_bound);
                act->max += (new_bound - old_bound) * coeff;
            }
            else if (!finite_bound)
            {
                act->n_inf_max--;

                if (act->n_inf_max == 0)
                {
                    act->max = compute_max_act_no_tags(vals, cols, len, bounds);
                }
            }
            return MAX_ALTERED;
        }
    }
}

void update_activities_bound_change(Activity *activities, const Matrix *A,
                                    const Bound *bounds, const double *vals,
                                    const int *rows, int len, double old_bound,
                                    double new_bound, bool finite_bound, bool lower,
                                    iVec *updated_activities HUGE_BOUND_PARAM)
{
    assert(!IS_HUGE(new_bound) || huge_bound_ok);
    assert(!finite_bound || (lower && new_bound > old_bound) ||
           (!lower && new_bound < old_bound));

    Altered_Activity altered;
    for (int ii = 0; ii < len; ++ii)
    {
        int i = rows[ii];
        Activity *act = activities + i;
        altered = update_act_bound_change(act, vals[ii], old_bound, new_bound,
                                          finite_bound, lower, A->x + A->p[i].start,
                                          A->i + A->p[i].start,
                                          A->p[i].end - A->p[i].start, bounds);

        if (((act->n_inf_max == 0 && (altered & MAX_ALTERED)) ||
             (act->n_inf_min == 0 && (altered & MIN_ALTERED))))
        {
            if (act->status == NOT_ADDED)
            {
                act->status = ADDED;
                iVec_append(updated_activities, rows[ii]);
            }
            else if (act->status == PROPAGATED_THIS_ROUND)
            {
                act->status = PROPAGATE_NEXT_ROUND;
                iVec_append(updated_activities, rows[ii]);
            }
        }
    }
}

void update_activities_fixed_col(Activity *activities, const Matrix *A,
                                 const Bound *bounds, const double *vals,
                                 const int *rows, int len, double old_ub,
                                 double old_lb, double val, bool ub_update,
                                 bool lb_update, bool is_ub_inf, bool is_lb_inf,
                                 iVec *updated_activities)
{
    Altered_Activity altered1;
    Altered_Activity altered2;
    Altered_Activity altered;

    for (int ii = 0; ii < len; ++ii)
    {
        altered1 = NO_RECOMPUTE;
        altered2 = NO_RECOMPUTE;
        int i = rows[ii];
        Activity *act = activities + i;

        if (ub_update)
        {
            altered1 = update_act_bound_change(
                act, vals[ii], old_ub, val, !is_ub_inf, false, A->x + A->p[i].start,
                A->i + A->p[i].start, A->p[i].end - A->p[i].start, bounds);
        }

        if (lb_update)
        {
            altered2 = update_act_bound_change(
                act, vals[ii], old_lb, val, !is_lb_inf, true, A->x + A->p[i].start,
                A->i + A->p[i].start, A->p[i].end - A->p[i].start, bounds);
        }

        altered = altered1 | altered2;
        if (((act->n_inf_max == 0 && (altered & MAX_ALTERED)) ||
             (act->n_inf_min == 0 && (altered & MIN_ALTERED))))
        {
            if (act->status == NOT_ADDED)
            {
                act->status = ADDED;
                iVec_append(updated_activities, i);
            }
            else if (act->status == PROPAGATED_THIS_ROUND)
            {
                act->status = PROPAGATE_NEXT_ROUND;
                iVec_append(updated_activities, i);
            }
        }
    }
}

Altered_Activity update_activity_coeff_change(Activity *act, double lb, double ub,
                                              double old_coeff, double new_coeff,
                                              ColTag cTag)
{
    assert(!HAS_TAG(cTag, C_TAG_INACTIVE));
    bool is_lb_finite = !HAS_TAG(cTag, C_TAG_LB_INF);
    bool is_ub_finite = !HAS_TAG(cTag, C_TAG_UB_INF);

    int n_inf_min_before = act->n_inf_min;
    int n_inf_max_before = act->n_inf_max;

    // ----------------------------------------
    // remove contribution from old coefficient
    // ----------------------------------------
    if (old_coeff > 0)
    {
        if (is_lb_finite)
        {
            if (act->n_inf_min == 0)
            {
                act->min -= old_coeff * lb;
            }
        }
        else
        {
            act->n_inf_min--;
        }

        if (is_ub_finite)
        {
            if (act->n_inf_max == 0)
            {
                act->max -= old_coeff * ub;
            }
        }
        else
        {
            act->n_inf_max--;
        }
    }
    else if (old_coeff < 0)
    {
        if (is_lb_finite)
        {
            if (act->n_inf_max == 0)
            {
                act->max -= old_coeff * lb;
            }
        }
        else
        {
            act->n_inf_max--;
        }

        if (is_ub_finite)
        {
            if (act->n_inf_min == 0)
            {
                act->min -= old_coeff * ub;
            }
        }
        else
        {
            act->n_inf_min--;
        }
    }

    // -----------------------------------
    // add contribution of new coefficient
    // -----------------------------------
    if (new_coeff > 0)
    {
        if (is_lb_finite)
        {
            if (act->n_inf_min == 0)
            {
                act->min += new_coeff * lb;
            }
        }
        else
        {
            act->n_inf_min++;
        }

        if (is_ub_finite)
        {
            if (act->n_inf_max == 0)
            {
                act->max += new_coeff * ub;
            }
        }
        else
        {
            act->n_inf_max++;
        }
    }
    else if (new_coeff < 0)
    {
        if (is_lb_finite)
        {
            if (act->n_inf_max == 0)
            {
                act->max += new_coeff * lb;
            }
        }
        else
        {
            act->n_inf_max++;
        }

        if (is_ub_finite)
        {
            if (act->n_inf_min == 0)
            {
                act->min += new_coeff * ub;
            }
        }
        else
        {
            act->n_inf_min++;
        }
    }

#ifndef NDEBUG
    if (n_inf_min_before == 0 && act->n_inf_min == 1)
    {
        act->min = INVALID_ACT_DEBUG;
    }

    if (n_inf_max_before == 0 && act->n_inf_max == 1)
    {
        act->max = INVALID_ACT_DEBUG;
    }
#endif

    // recompute from scratch if necessary
    if (act->n_inf_min == 0 && n_inf_min_before == 1)
    {
        return MIN_ALTERED_RECOMPUTE;
    }

    if (act->n_inf_max == 0 && n_inf_max_before == 1)
    {
        return MAX_ALTERED_RECOMPUTE;
    }

    return NO_RECOMPUTE;
}

void remove_finite_lb_from_activities(const ConstColView *col, Activity *acts,
                                      double bound)
{

    for (int ii = 0; ii < *col->len; ii++)
    {
        int i = col->rows[ii];
        Activity *act = acts + i;

        if (col->vals[ii] > 0)
        {
            if (act->n_inf_min == 0)
            {
                act->min -= col->vals[ii] * bound;
            }

            act->n_inf_min++;
        }
        else if (col->vals[ii] < 0)
        {
            if (act->n_inf_max == 0)
            {
                act->max -= col->vals[ii] * bound;
            }
            act->n_inf_max++;
        }

        DEBUG(acts[i].min =
                  (acts[i].n_inf_min != 0) ? INVALID_ACT_DEBUG : acts[i].min);
        DEBUG(acts[i].max =
                  (acts[i].n_inf_max != 0) ? INVALID_ACT_DEBUG : acts[i].max);
    }

    return;
}

void remove_finite_ub_from_activities(const ConstColView *col, Activity *acts,
                                      double bound)
{

    for (int ii = 0; ii < *col->len; ii++)
    {
        int i = col->rows[ii];
        Activity *act = acts + i;

        if (col->vals[ii] > 0)
        {
            if (act->n_inf_max == 0)
            {
                act->max -= col->vals[ii] * bound;
            }

            act->n_inf_max++;
        }
        else if (col->vals[ii] < 0)
        {
            if (act->n_inf_min == 0)
            {
                act->min -= col->vals[ii] * bound;
            }
            act->n_inf_min++;
        }

        DEBUG(acts[i].min =
                  (acts[i].n_inf_min != 0) ? INVALID_ACT_DEBUG : acts[i].min);
        DEBUG(acts[i].max =
                  (acts[i].n_inf_max != 0) ? INVALID_ACT_DEBUG : acts[i].max);
    }

    return;
}

void recompute_n_infs(Activity *act, const double *vals, const int *cols, int len,
                      const ColTag *coltags)
{
    int n_inf_max = 0;
    int n_inf_min = 0;

    for (int j = 0; j < len; ++j)
    {
        if (HAS_TAG(coltags[cols[j]], C_TAG_INACTIVE))
        {
            continue;
        }

        if (vals[j] > 0)
        {
            if (HAS_TAG(coltags[cols[j]], C_TAG_UB_INF))
            {
                n_inf_max++;
            }

            if (HAS_TAG(coltags[cols[j]], C_TAG_LB_INF))
            {
                n_inf_min++;
            }
        }
        else
        {
            if (HAS_TAG(coltags[cols[j]], C_TAG_LB_INF))
            {
                n_inf_max++;
            }

            if (HAS_TAG(coltags[cols[j]], C_TAG_UB_INF))
            {
                n_inf_min++;
            }
        }
    }

    act->n_inf_max = n_inf_max;
    act->n_inf_min = n_inf_min;
}

1	/*
2	* Copyright 2025 Daniel Cederberg
3	*
4	* This file is part of the PSLP project (LP Presolver).
5	*
6	* Licensed under the Apache License, Version 2.0 (the "License");
7	* you may not use this file except in compliance with the License.
8	* You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing, software
13	* distributed under the License is distributed on an "AS IS" BASIS,
14	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15	* See the License for the specific language governing permissions and
16	* limitations under the License.
17	*/
18
19	#include "Activity.h"
20	#include "Bounds.h"
21	#include "Matrix.h"
22	#include "Memory_wrapper.h"
23	#include "Numerics.h"
24	#include "RowColViews.h"
25	#include "glbopts.h"
26
27	Activity new_activities(const Matrix A, const ColTag *col_tags,	99✔
28	const Bound *bounds)
29	{
30	Activity activities = (Activity ) ps_malloc(A->m, sizeof(Activity));	99✔
31	RETURN_PTR_IF_NULL(activities, NULL);	99✔
32	int i, j, start, end;
33	int *cols = A->i;	99✔
34	double *vals = A->x;	99✔
35
36	for (i = 0; i < A->m; ++i)	514✔
37	{
38	Activity *act = activities + i;	415✔
39	act->n_inf_min = 0;	415✔
40	act->n_inf_max = 0;	415✔
41	act->max = 0.0;	415✔
42	act->min = 0.0;	415✔
43	act->status = NOT_ADDED;	415✔
44
45	start = A->p[i].start;	415✔
46	end = A->p[i].end;	415✔
47
48	// record infinite contributions
49	for (j = start; j < end; ++j)	1,825✔
50	{
51	if (vals[j] > 0)	1,410✔
52	{
53	if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))	1,085✔
54	{
55	act->n_inf_max++;	701✔
56	}
57
58	if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))	1,085✔
59	{
60	act->n_inf_min++;	98✔
61	}
62	}
63	else
64	{
65	if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))	325✔
66	{
67	act->n_inf_max++;	32✔
68	}
69
70	if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))	325✔
71	{
72	act->n_inf_min++;	196✔
73	}
74	}
75	}
76
77	// compute max act if it is useful
78	if (act->n_inf_max == 0)	415✔
79	{
80	for (j = start; j < end; ++j)	545✔
81	{
82	if (vals[j] > 0)	435✔
83	{
84	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));	292✔
85	assert(!IS_POS_INF(bounds[cols[j]].ub));	292✔
86	act->max += vals[j] * bounds[cols[j]].ub;	292✔
87	}
88	else
89	{
90	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));	143✔
91	assert(!IS_NEG_INF(bounds[cols[j]].lb));	143✔
92	act->max += vals[j] * bounds[cols[j]].lb;	143✔
93	}
94	}
95	}
96	#ifndef NDEBUG
97	else
98	{
99	act->max = INVALID_ACT_DEBUG;	305✔
100	}
101	#endif
102
103	// compute min act if it is useful
104	if (act->n_inf_min == 0)	415✔
105	{
106	for (j = start; j < end; ++j)	989✔
107	{
108	if (vals[j] > 0)	751✔
109	{
110	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));	632✔
111	assert(!IS_NEG_INF(bounds[cols[j]].lb));	632✔
112	act->min += vals[j] * bounds[cols[j]].lb;	632✔
113	}
114	else
115	{
116	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));	119✔
117	assert(!IS_POS_INF(bounds[cols[j]].ub));	119✔
118	act->min += vals[j] * bounds[cols[j]].ub;	119✔
119	}
120	}
121	}
122	#ifndef NDEBUG
123	else
124	{
125	act->min = INVALID_ACT_DEBUG;	177✔
126	}
127	#endif
128	}
129
130	return activities;	99✔
131	}
132
133	void free_activities(Activity *activities)	×
134	{
135	PS_FREE(activities);	×
136	}	×
137
138	void Activities_init(const Matrix A, const ColTag col_tags, const RowTag *row_tags,	×
139	const Bound bounds, Activity acts)
140	{
141
142	for (int i = 0; i < A->m; ++i)	×
143	{
144	if (HAS_TAG(row_tags[i], R_TAG_INACTIVE))	×
145	{
146	DEBUG(acts[i].status = NOT_ADDED;);	×
147	continue;	×
148	}
149
150	Activity_init(acts + i, A->x + A->p[i].start, A->i + A->p[i].start,	×
151	A->p[i].end - A->p[i].start, bounds, col_tags);	×
152	}
153	}	×
154
155	void Activity_init(Activity act, const double vals, const int *cols, int len,	×
156	const Bound bounds, const ColTag col_tags)
157	{
158	act->n_inf_min = 0;	×
159	act->n_inf_max = 0;	×
160	act->max = 0.0;	×
161	act->min = 0.0;	×
162	act->status = NOT_ADDED;	×
163	int j;
164
165	// record infinite contributions
166	for (j = 0; j < len; ++j)	×
167	{
168	if (vals[j] > 0)	×
169	{
170	if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))	×
171	{
172	act->n_inf_max++;	×
173	}
174
175	if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))	×
176	{
177	act->n_inf_min++;	×
178	}
179	}
180	else
181	{
182	if (HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))	×
183	{
184	act->n_inf_max++;	×
185	}
186
187	if (HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))	×
188	{
189	act->n_inf_min++;	×
190	}
191	}
192	}
193
194	// compute max act if it is useful
195	if (act->n_inf_max == 0)	×
196	{
197	for (j = 0; j < len; ++j)	×
198	{
199	if (vals[j] > 0)	×
200	{
201	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));	×
202	assert(!IS_POS_INF(bounds[cols[j]].ub));	×
203	act->max += vals[j] * bounds[cols[j]].ub;	×
204	}
205	else
206	{
207	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));	×
208	assert(!IS_NEG_INF(bounds[cols[j]].lb));	×
209	act->max += vals[j] * bounds[cols[j]].lb;	×
210	}
211	}
212	}
213	#ifndef NDEBUG
214	else
215	{
216	act->max = INVALID_ACT_DEBUG;	×
217	}
218	#endif
219
220	// compute min act if it is useful
221	if (act->n_inf_min == 0)	×
222	{
223	for (j = 0; j < len; ++j)	×
224	{
225	if (vals[j] > 0)	×
226	{
227	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF));	×
228	assert(!IS_NEG_INF(bounds[cols[j]].lb));	×
229	act->min += vals[j] * bounds[cols[j]].lb;	×
230	}
231	else
232	{
233	assert(!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF));	×
234	assert(!IS_POS_INF(bounds[cols[j]].ub));	×
235	act->min += vals[j] * bounds[cols[j]].ub;	×
236	}
237	}
238	}
239	#ifndef NDEBUG
240	else
241	{
242	act->min = INVALID_ACT_DEBUG;	×
243	}
244	#endif
245	}	×
246
247	double compute_min_act_tags(const double vals, const int cols, int len,	7✔
248	const Bound bounds, const ColTag col_tags)
249	{
250	double min_act = 0.0;	7✔
251	for (int j = 0; j < len; ++j)	40✔
252	{
253	if (vals[j] > 0)	33✔
254	{
255	if (!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))	28✔
256	{
257	assert(!IS_NEG_INF(bounds[cols[j]].lb));	26✔
258	min_act += vals[j] * bounds[cols[j]].lb;	26✔
259	}
260	}
261	else
262	{
263	if (!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))	5✔
264	{
265	assert(!IS_POS_INF(bounds[cols[j]].ub));	×
266	min_act += vals[j] * bounds[cols[j]].ub;	×
267	}
268	}
269	}
270	return min_act;	7✔
271	}
272
273	double compute_max_act_tags(const double vals, const int cols, int len,	2✔
274	const Bound bounds, const ColTag col_tags)
275	{
276	double max_act = 0.0;	2✔
277	for (int j = 0; j < len; ++j)	8✔
278	{
279	if (vals[j] > 0)	6✔
280	{
281	if (!HAS_TAG(col_tags[cols[j]], C_TAG_UB_INF))	2✔
282	{
283	assert(!IS_POS_INF(bounds[cols[j]].ub));	×
284	max_act += vals[j] * bounds[cols[j]].ub;	×
285	}
286	}
287	else
288	{
289	if (!HAS_TAG(col_tags[cols[j]], C_TAG_LB_INF))	4✔
290	{
291	assert(!IS_NEG_INF(bounds[cols[j]].lb));	4✔
292	max_act += vals[j] * bounds[cols[j]].lb;	4✔
293	}
294	}
295	}
296	return max_act;	2✔
297	}
298
299	double compute_min_act_no_tags(const double vals, const int cols, int len,	54✔
300	const Bound *bounds)
301	{
302	double min_act = 0.0;	54✔
303	for (int j = 0; j < len; ++j)	222✔
304	{
305	if (vals[j] > 0)	168✔
306	{
307	assert(!IS_NEG_INF(bounds[cols[j]].lb));	116✔
308	min_act += vals[j] * bounds[cols[j]].lb;	116✔
309	}
310	else
311	{
312	assert(!IS_POS_INF(bounds[cols[j]].ub));	52✔
313	min_act += vals[j] * bounds[cols[j]].ub;	52✔
314	}
315	}
316	return min_act;	54✔
317	}
318
319	double compute_max_act_no_tags(const double vals, const int cols, int len,	44✔
320	const Bound *bounds)
321	{
322	double max_act = 0.0;	44✔
323	for (int j = 0; j < len; ++j)	158✔
324	{
325	if (vals[j] > 0)	114✔
326	{
327	assert(!IS_POS_INF(bounds[cols[j]].ub));	77✔
328	max_act += vals[j] * bounds[cols[j]].ub;	77✔
329	}
330	else
331	{
332	assert(!IS_NEG_INF(bounds[cols[j]].lb));	37✔
333	max_act += vals[j] * bounds[cols[j]].lb;	37✔
334	}
335	}
336	return max_act;	44✔
337	}
338
339	double compute_min_act_one_tag(const double vals, const int cols, int len,	2✔
340	const Bound *bounds, int col_to_avoid)
341	{
342	assert(col_to_avoid >= 0);	2✔
343	double min_act = 0.0;	2✔
344	for (int j = 0; j < len; ++j)	9✔
345	{
346	if (cols[j] == col_to_avoid)	7✔
347	{
348	continue;	2✔
349	}
350
351	if (vals[j] > 0)	5✔
352	{
353	assert(!IS_NEG_INF(bounds[cols[j]].lb));	5✔
354	min_act += vals[j] * bounds[cols[j]].lb;	5✔
355	}
356	else
357	{
358	assert(!IS_POS_INF(bounds[cols[j]].ub));	×
359	min_act += vals[j] * bounds[cols[j]].ub;	×
360	}
361	}
362	return min_act;	2✔
363	}
364
365	double compute_max_act_one_tag(const double vals, const int cols, int len,	1✔
366	const Bound *bounds, int col_to_avoid)
367	{
368	assert(col_to_avoid >= 0);	1✔
369	double max_act = 0.0;	1✔
370	for (int j = 0; j < len; ++j)	3✔
371	{
372	if (cols[j] == col_to_avoid)	2✔
373	{
374	continue;	1✔
375	}
376
377	if (vals[j] > 0)	1✔
378	{
379	assert(!IS_POS_INF(bounds[cols[j]].ub));	1✔
380	max_act += vals[j] * bounds[cols[j]].ub;	1✔
381	}
382	else
383	{
384	assert(!IS_NEG_INF(bounds[cols[j]].lb));	×
385	max_act += vals[j] * bounds[cols[j]].lb;	×
386	}
387	}
388	return max_act;	1✔
389	}
390
391	Altered_Activity update_act_bound_change(Activity *act, double coeff,	350✔
392	double old_bound, double new_bound,
393	bool finite_bound, bool lower,
394	const double vals, const int cols,
395	int len, const Bound *bounds)
396	{
397	// ---------------------------------------------------------------------
398	// If a lower bound has been updated
399	// ---------------------------------------------------------------------
400	if (lower)	350✔
401	{
402	if (coeff < 0)	70✔
403	{
404	if (act->n_inf_max == 0)	22✔
405	{
406	assert(finite_bound);	14✔
407	act->max += (new_bound - old_bound) * coeff;	14✔
408	}
409	else if (!finite_bound)	8✔
410	{
411	act->n_inf_max--;	4✔
412
413	if (act->n_inf_max == 0)	4✔
414	{
415	act->max = compute_max_act_no_tags(vals, cols, len, bounds);	×
416	}
417	}
418
419	return MAX_ALTERED;	22✔
420	}
421	else
422	{
423	if (act->n_inf_min == 0)	48✔
424	{
425	assert(finite_bound);	20✔
426	act->min += (new_bound - old_bound) * coeff;	20✔
427	}
428	else if (!finite_bound)	28✔
429	{
430	act->n_inf_min--;	20✔
431
432	if (act->n_inf_min == 0)	20✔
433	{
434	act->min = compute_min_act_no_tags(vals, cols, len, bounds);	8✔
435	}
436	}
437	return MIN_ALTERED;	48✔
438	}
439	}
440	// ------------------------------------------------------------------------
441	// If an upper bound has been updated
442	// ------------------------------------------------------------------------
443	else
444	{
445	if (coeff < 0)	280✔
446	{
447	if (act->n_inf_min == 0)	82✔
448	{
449	assert(finite_bound);	20✔
450	act->min += (new_bound - old_bound) * coeff;	20✔
451	}
452	else if (!finite_bound)	62✔
453	{
454	act->n_inf_min--;	60✔
455
456	if (act->n_inf_min == 0)	60✔
457	{
458	act->min = compute_min_act_no_tags(vals, cols, len, bounds);	39✔
459	}
460	}
461	return MIN_ALTERED;	82✔
462	}
463	else
464	{
465	if (act->n_inf_max == 0)	198✔
466	{
467	assert(finite_bound);	72✔
468	act->max += (new_bound - old_bound) * coeff;	72✔
469	}
470	else if (!finite_bound)	126✔
471	{
472	act->n_inf_max--;	112✔
473
474	if (act->n_inf_max == 0)	112✔
475	{
476	act->max = compute_max_act_no_tags(vals, cols, len, bounds);	42✔
477	}
478	}
479	return MAX_ALTERED;	198✔
480	}
481	}
482	}
483
484	void update_activities_bound_change(Activity activities, const Matrix A,	74✔
485	const Bound bounds, const double vals,
486	const int *rows, int len, double old_bound,
487	double new_bound, bool finite_bound, bool lower,
488	iVec *updated_activities HUGE_BOUND_PARAM)
489	{
490	assert(!IS_HUGE(new_bound) \|\| huge_bound_ok);	74✔
491	assert(!finite_bound \|\| (lower && new_bound > old_bound) \|\|	74✔
492	(!lower && new_bound < old_bound));
493
494	Altered_Activity altered;
495	for (int ii = 0; ii < len; ++ii)	324✔
496	{
497	int i = rows[ii];	250✔
498	Activity *act = activities + i;	250✔
499	altered = update_act_bound_change(act, vals[ii], old_bound, new_bound,	250✔
500	finite_bound, lower, A->x + A->p[i].start,	250✔
501	A->i + A->p[i].start,	250✔
502	A->p[i].end - A->p[i].start, bounds);	250✔
503
504	if (((act->n_inf_max == 0 && (altered & MAX_ALTERED)) \|\|	250✔
505	(act->n_inf_min == 0 && (altered & MIN_ALTERED))))	149✔
506	{
507	if (act->status == NOT_ADDED)	162✔
508	{
509	act->status = ADDED;	31✔
510	iVec_append(updated_activities, rows[ii]);	31✔
511	}
512	else if (act->status == PROPAGATED_THIS_ROUND)	131✔
513	{
514	act->status = PROPAGATE_NEXT_ROUND;	30✔
515	iVec_append(updated_activities, rows[ii]);	30✔
516	}
517	}
518	}
519	}	74✔
520
521	void update_activities_fixed_col(Activity activities, const Matrix A,	32✔
522	const Bound bounds, const double vals,
523	const int *rows, int len, double old_ub,
524	double old_lb, double val, bool ub_update,
525	bool lb_update, bool is_ub_inf, bool is_lb_inf,
526	iVec *updated_activities)
527	{
528	Altered_Activity altered1;
529	Altered_Activity altered2;
530	Altered_Activity altered;
531
532	for (int ii = 0; ii < len; ++ii)	113✔
533	{
534	altered1 = NO_RECOMPUTE;	81✔
535	altered2 = NO_RECOMPUTE;	81✔
536	int i = rows[ii];	81✔
537	Activity *act = activities + i;	81✔
538
539	if (ub_update)	81✔
540	{
541	altered1 = update_act_bound_change(	57✔
542	act, vals[ii], old_ub, val, !is_ub_inf, false, A->x + A->p[i].start,	57✔
543	A->i + A->p[i].start, A->p[i].end - A->p[i].start, bounds);	57✔
544	}
545
546	if (lb_update)	81✔
547	{
548	altered2 = update_act_bound_change(	43✔
549	act, vals[ii], old_lb, val, !is_lb_inf, true, A->x + A->p[i].start,	43✔
550	A->i + A->p[i].start, A->p[i].end - A->p[i].start, bounds);	43✔
551	}
552
553	altered = altered1 \| altered2;	81✔
554	if (((act->n_inf_max == 0 && (altered & MAX_ALTERED)) \|\|	81✔
555	(act->n_inf_min == 0 && (altered & MIN_ALTERED))))	54✔
556	{
557	if (act->status == NOT_ADDED)	36✔
558	{
559	act->status = ADDED;	5✔
560	iVec_append(updated_activities, i);	5✔
561	}
562	else if (act->status == PROPAGATED_THIS_ROUND)	31✔
563	{
564	act->status = PROPAGATE_NEXT_ROUND;	8✔
565	iVec_append(updated_activities, i);	8✔
566	}
567	}
568	}
569	}	32✔
570
571	Altered_Activity update_activity_coeff_change(Activity *act, double lb, double ub,	104✔
572	double old_coeff, double new_coeff,
573	ColTag cTag)
574	{
575	assert(!HAS_TAG(cTag, C_TAG_INACTIVE));	104✔
576	bool is_lb_finite = !HAS_TAG(cTag, C_TAG_LB_INF);	104✔
577	bool is_ub_finite = !HAS_TAG(cTag, C_TAG_UB_INF);	104✔
578
579	int n_inf_min_before = act->n_inf_min;	104✔
580	int n_inf_max_before = act->n_inf_max;	104✔
581
582	// ----------------------------------------
583	// remove contribution from old coefficient
584	// ----------------------------------------
585	if (old_coeff > 0)	104✔
586	{
587	if (is_lb_finite)	58✔
588	{
589	if (act->n_inf_min == 0)	54✔
590	{
591	act->min -= old_coeff * lb;	39✔
592	}
593	}
594	else
595	{
596	act->n_inf_min--;	4✔
597	}
598
599	if (is_ub_finite)	58✔
600	{
601	if (act->n_inf_max == 0)	24✔
602	{
603	act->max -= old_coeff * ub;	9✔
604	}
605	}
606	else
607	{
608	act->n_inf_max--;	34✔
609	}
610	}
611	else if (old_coeff < 0)	46✔
612	{
613	if (is_lb_finite)	18✔
614	{
615	if (act->n_inf_max == 0)	18✔
616	{
617	act->max -= old_coeff * lb;	7✔
618	}
619	}
620	else
621	{
622	act->n_inf_max--;	×
623	}
624
625	if (is_ub_finite)	18✔
626	{
627	if (act->n_inf_min == 0)	15✔
628	{
629	act->min -= old_coeff * ub;	11✔
630	}
631	}
632	else
633	{
634	act->n_inf_min--;	3✔
635	}
636	}
637
638	// -----------------------------------
639	// add contribution of new coefficient
640	// -----------------------------------
641	if (new_coeff > 0)	104✔
642	{
643	if (is_lb_finite)	26✔
644	{
645	if (act->n_inf_min == 0)	26✔
646	{
647	act->min += new_coeff * lb;	19✔
648	}
649	}
650	else
651	{
652	act->n_inf_min++;	×
653	}
654
655	if (is_ub_finite)	26✔
656	{
657	if (act->n_inf_max == 0)	10✔
658	{
659	act->max += new_coeff * ub;	2✔
660	}
661	}
662	else
663	{
664	act->n_inf_max++;	16✔
665	}
666	}
667	else if (new_coeff < 0)	78✔
668	{
669	if (is_lb_finite)	17✔
670	{
671	if (act->n_inf_max == 0)	16✔
672	{
673	act->max += new_coeff * lb;	4✔
674	}
675	}
676	else
677	{
678	act->n_inf_max++;	1✔
679	}
680
681	if (is_ub_finite)	17✔
682	{
683	if (act->n_inf_min == 0)	16✔
684	{
685	act->min += new_coeff * ub;	14✔
686	}
687	}
688	else
689	{
690	act->n_inf_min++;	1✔
691	}
692	}
693
694	#ifndef NDEBUG
695	if (n_inf_min_before == 0 && act->n_inf_min == 1)	104✔
696	{
697	act->min = INVALID_ACT_DEBUG;	×
698	}
699
700	if (n_inf_max_before == 0 && act->n_inf_max == 1)	104✔
701	{
702	act->max = INVALID_ACT_DEBUG;	×
703	}
704	#endif
705
706	// recompute from scratch if necessary
707	if (act->n_inf_min == 0 && n_inf_min_before == 1)	104✔
708	{
709	return MIN_ALTERED_RECOMPUTE;	4✔
710	}
711
712	if (act->n_inf_max == 0 && n_inf_max_before == 1)	100✔
713	{
714	return MAX_ALTERED_RECOMPUTE;	2✔
715	}
716
717	return NO_RECOMPUTE;	98✔
718	}
719
720	void remove_finite_lb_from_activities(const ConstColView col, Activity acts,	×
721	double bound)
722	{
723
UNCOV 724	for (int ii = 0; ii < *col->len; ii++)	×
725	{
UNCOV 726	int i = col->rows[ii];	×
727	Activity *act = acts + i;	×
728
UNCOV 729	if (col->vals[ii] > 0)	×
730	{
731	if (act->n_inf_min == 0)	×
732	{
733	act->min -= col->vals[ii] * bound;	×
734	}
735
736	act->n_inf_min++;	×
737	}
738	else if (col->vals[ii] < 0)	×
739	{
740	if (act->n_inf_max == 0)	×
741	{
UNCOV 742	act->max -= col->vals[ii] * bound;	×
743	}
UNCOV 744	act->n_inf_max++;	×
745	}
746
747	DEBUG(acts[i].min =	×
748	(acts[i].n_inf_min != 0) ? INVALID_ACT_DEBUG : acts[i].min);
749	DEBUG(acts[i].max =	×
750	(acts[i].n_inf_max != 0) ? INVALID_ACT_DEBUG : acts[i].max);
751	}
752
UNCOV 753	return;	×
754	}
755
756	void remove_finite_ub_from_activities(const ConstColView col, Activity acts,	7✔
757	double bound)
758	{
759
760	for (int ii = 0; ii < *col->len; ii++)	21✔
761	{
762	int i = col->rows[ii];	14✔
763	Activity *act = acts + i;	14✔
764
765	if (col->vals[ii] > 0)	14✔
766	{
767	if (act->n_inf_max == 0)	12✔
768	{
769	act->max -= col->vals[ii] * bound;	8✔
770	}
771
772	act->n_inf_max++;	12✔
773	}
774	else if (col->vals[ii] < 0)	2✔
775	{
776	if (act->n_inf_min == 0)	2✔
777	{
778	act->min -= col->vals[ii] * bound;	2✔
779	}
780	act->n_inf_min++;	2✔
781	}
782
783	DEBUG(acts[i].min =	14✔
784	(acts[i].n_inf_min != 0) ? INVALID_ACT_DEBUG : acts[i].min);
785	DEBUG(acts[i].max =	14✔
786	(acts[i].n_inf_max != 0) ? INVALID_ACT_DEBUG : acts[i].max);
787	}
788
789	return;	7✔
790	}
791
792	void recompute_n_infs(Activity act, const double vals, const int *cols, int len,	38✔
793	const ColTag *coltags)
794	{
795	int n_inf_max = 0;	38✔
796	int n_inf_min = 0;	38✔
797
798	for (int j = 0; j < len; ++j)	296✔
799	{
800	if (HAS_TAG(coltags[cols[j]], C_TAG_INACTIVE))	258✔
801	{
802	continue;	87✔
803	}
804
805	if (vals[j] > 0)	171✔
806	{
807	if (HAS_TAG(coltags[cols[j]], C_TAG_UB_INF))	111✔
808	{
UNCOV 809	n_inf_max++;	×
810	}
811
812	if (HAS_TAG(coltags[cols[j]], C_TAG_LB_INF))	111✔
813	{
UNCOV 814	n_inf_min++;	×
815	}
816	}
817	else
818	{
819	if (HAS_TAG(coltags[cols[j]], C_TAG_LB_INF))	60✔
820	{
821	n_inf_max++;	3✔
822	}
823
824	if (HAS_TAG(coltags[cols[j]], C_TAG_UB_INF))	60✔
825	{
826	n_inf_min++;	4✔
827	}
828	}
829	}
830
831	act->n_inf_max = n_inf_max;	38✔
832	act->n_inf_min = n_inf_min;	38✔
833	}	38✔

dance858 / PSLP / 22279069886

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous