csls_api.cs

// Copyright 2010-2022 Google LLC
// 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.

using System;
using Google.OrTools.ConstraintSolver;

/**
 * Shows how to write a custom lns operator.
 */

public class OneVarLns : BaseLns
{
    public OneVarLns(IntVar[] vars) : base(vars)
    {
    }

    public override void InitFragments()
    {
        index_ = 0;
    }

    public override bool NextFragment()
    {
        int size = Size();
        if (index_ < size)
        {
            AppendToFragment(index_);
            ++index_;
            return true;
        }
        else
        {
            return false;
        }
    }

    private int index_;
}

class MoveOneVar : IntVarLocalSearchOperator
{
    public MoveOneVar(IntVar[] variables) : base(variables)
    {
        variable_index_ = 0;
        move_up_ = false;
    }

    protected override bool MakeOneNeighbor()
    {
        long current_value = OldValue(variable_index_);
        if (move_up_)
        {
            SetValue(variable_index_, current_value + 1);
            variable_index_ = (variable_index_ + 1) % Size();
        }
        else
        {
            SetValue(variable_index_, current_value - 1);
        }
        move_up_ = !move_up_;
        return true;
    }

    // Index of the next variable to try to restore
    private long variable_index_;
    // Direction of the modification.
    private bool move_up_;
};

public class SumFilter : IntVarLocalSearchFilter
{
    public SumFilter(IntVar[] vars) : base(vars)
    {
        sum_ = 0;
    }

    protected override void OnSynchronize(Assignment delta)
    {
        sum_ = 0;
        for (int index = 0; index < Size(); ++index)
        {
            sum_ += Value(index);
        }
    }

    public override bool Accept(Assignment delta, Assignment unused_deltadelta, long unused_objective_min,
                                long unused_objective_max)
    {
        AssignmentIntContainer solution_delta = delta.IntVarContainer();
        int solution_delta_size = solution_delta.Size();

        for (int i = 0; i < solution_delta_size; ++i)
        {
            if (!solution_delta.Element(i).Activated())
            {
                return true;
            }
        }
        long new_sum = sum_;
        for (int index = 0; index < solution_delta_size; ++index)
        {
            int touched_var = Index(solution_delta.Element(index).Var());
            long old_value = Value(touched_var);
            long new_value = solution_delta.Element(index).Value();
            new_sum += new_value - old_value;
        }
        return new_sum < sum_;
    }

    private long sum_;
};

public class CsLsApi
{
    private static void BasicLns()
    {
        Console.WriteLine("BasicLns");
        Solver solver = new Solver("BasicLns");
        IntVar[] vars = solver.MakeIntVarArray(4, 0, 4, "vars");
        IntVar sum_var = vars.Sum().Var();
        OptimizeVar obj = sum_var.Minimize(1);
        DecisionBuilder db = solver.MakePhase(vars, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MAX_VALUE);
        OneVarLns one_var_lns = new OneVarLns(vars);
        LocalSearchPhaseParameters ls_params = solver.MakeLocalSearchPhaseParameters(sum_var, one_var_lns, db);
        DecisionBuilder ls = solver.MakeLocalSearchPhase(vars, db, ls_params);
        SolutionCollector collector = solver.MakeLastSolutionCollector();
        collector.AddObjective(sum_var);
        SearchMonitor log = solver.MakeSearchLog(1000, obj);
        solver.Solve(ls, collector, obj, log);
        Console.WriteLine("Objective value = {0}", collector.ObjectiveValue(0));
    }

    private static void BasicLs()
    {
        Console.WriteLine("BasicLs");
        Solver solver = new Solver("BasicLs");
        IntVar[] vars = solver.MakeIntVarArray(4, 0, 4, "vars");
        IntVar sum_var = vars.Sum().Var();
        OptimizeVar obj = sum_var.Minimize(1);
        DecisionBuilder db = solver.MakePhase(vars, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MAX_VALUE);
        MoveOneVar move_one_var = new MoveOneVar(vars);
        LocalSearchPhaseParameters ls_params = solver.MakeLocalSearchPhaseParameters(sum_var, move_one_var, db);
        DecisionBuilder ls = solver.MakeLocalSearchPhase(vars, db, ls_params);
        SolutionCollector collector = solver.MakeLastSolutionCollector();
        collector.AddObjective(sum_var);
        SearchMonitor log = solver.MakeSearchLog(1000, obj);
        solver.Solve(ls, collector, obj, log);
        Console.WriteLine("Objective value = {0}", collector.ObjectiveValue(0));
    }

    private static void BasicLsWithFilter()
    {
        Console.WriteLine("BasicLsWithFilter");
        Solver solver = new Solver("BasicLs");
        IntVar[] vars = solver.MakeIntVarArray(4, 0, 4, "vars");
        IntVar sum_var = vars.Sum().Var();
        OptimizeVar obj = sum_var.Minimize(1);
        DecisionBuilder db = solver.MakePhase(vars, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MAX_VALUE);
        MoveOneVar move_one_var = new MoveOneVar(vars);
        SumFilter filter = new SumFilter(vars);
        IntVarLocalSearchFilter[] filters = new IntVarLocalSearchFilter[] { filter };
        LocalSearchFilterManager filter_manager = new LocalSearchFilterManager(filters);
        LocalSearchPhaseParameters ls_params =
            solver.MakeLocalSearchPhaseParameters(sum_var, move_one_var, db, null, filter_manager);
        DecisionBuilder ls = solver.MakeLocalSearchPhase(vars, db, ls_params);
        SolutionCollector collector = solver.MakeLastSolutionCollector();
        collector.AddObjective(sum_var);
        SearchMonitor log = solver.MakeSearchLog(1000, obj);
        solver.Solve(ls, collector, obj, log);
        Console.WriteLine("Objective value = {0}", collector.ObjectiveValue(0));
    }

    public static void Main(String[] args)
    {
        BasicLns();
        BasicLs();
        BasicLsWithFilter();
    }
}