2025-01-10 11:33:35 +01:00
|
|
|
// Copyright 2010-2025 Google LLC
|
2019-02-04 16:48:12 +01:00
|
|
|
// 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.
|
2021-08-31 11:58:46 +02:00
|
|
|
|
|
|
|
|
package com.google.ortools.constraintsolver;
|
|
|
|
|
|
|
|
|
|
import static com.google.common.truth.Truth.assertThat;
|
2026-01-28 17:42:53 +01:00
|
|
|
import static org.junit.jupiter.api.Assertions.assertEquals;
|
|
|
|
|
import static org.junit.jupiter.api.Assertions.assertFalse;
|
|
|
|
|
import static org.junit.jupiter.api.Assertions.assertNotNull;
|
|
|
|
|
import static org.junit.jupiter.api.Assertions.assertTrue;
|
2019-02-04 16:48:12 +01:00
|
|
|
|
2021-09-17 09:44:04 +02:00
|
|
|
import com.google.common.collect.Iterables;
|
2021-12-10 16:59:43 +01:00
|
|
|
import com.google.ortools.Loader;
|
2021-08-31 11:58:46 +02:00
|
|
|
import com.google.ortools.constraintsolver.ConstraintSolverParameters;
|
|
|
|
|
import com.google.ortools.constraintsolver.RegularLimitParameters;
|
|
|
|
|
import java.util.ArrayList;
|
2019-02-08 13:08:37 +01:00
|
|
|
import java.util.concurrent.atomic.AtomicInteger;
|
|
|
|
|
import java.util.function.Consumer;
|
|
|
|
|
import java.util.function.Supplier;
|
2026-01-28 17:42:53 +01:00
|
|
|
import org.junit.jupiter.api.BeforeEach;
|
|
|
|
|
import org.junit.jupiter.api.Test;
|
2019-02-04 16:48:12 +01:00
|
|
|
|
|
|
|
|
/** Tests the Constraint solver java interface. */
|
2021-08-31 11:58:46 +02:00
|
|
|
public final class ConstraintSolverTest {
|
2026-01-28 17:42:53 +01:00
|
|
|
@BeforeEach
|
2021-08-31 11:58:46 +02:00
|
|
|
public void setUp() {
|
|
|
|
|
Loader.loadNativeLibraries();
|
2019-03-29 17:35:04 +01:00
|
|
|
}
|
|
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
@Test
|
|
|
|
|
public void testSolverCtor() {
|
|
|
|
|
final Solver solver = new Solver("TestSolver");
|
|
|
|
|
assertNotNull(solver);
|
|
|
|
|
assertEquals("TestSolver", solver.model_name());
|
|
|
|
|
assertNotNull(solver.toString());
|
|
|
|
|
}
|
2019-02-04 16:48:12 +01:00
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
@Test
|
2021-08-31 11:58:46 +02:00
|
|
|
public void testIntVar() {
|
|
|
|
|
final Solver solver = new Solver("Solver");
|
|
|
|
|
final IntVar var = solver.makeIntVar(3, 11, "IntVar");
|
|
|
|
|
assertEquals(3, var.min());
|
|
|
|
|
assertEquals(11, var.max());
|
2024-01-10 14:23:02 +01:00
|
|
|
assertEquals("IntVar", var.name());
|
|
|
|
|
var.setName("renamed");
|
|
|
|
|
assertEquals("renamed", var.name());
|
2021-08-31 11:58:46 +02:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testIntVarArray() {
|
|
|
|
|
final Solver solver = new Solver("Solver");
|
|
|
|
|
final IntVar[] vars = solver.makeIntVarArray(7, 3, 5, "vars");
|
|
|
|
|
assertThat(vars).hasLength(7);
|
|
|
|
|
for (IntVar var : vars) {
|
|
|
|
|
assertEquals(3, var.min());
|
|
|
|
|
assertEquals(5, var.max());
|
2020-09-23 12:10:52 +02:00
|
|
|
}
|
2019-03-01 09:41:22 +01:00
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
@Test
|
2021-08-31 11:58:46 +02:00
|
|
|
public void testRabbitsPheasants() {
|
|
|
|
|
final Solver solver = new Solver("testRabbitsPheasants");
|
|
|
|
|
final IntVar rabbits = solver.makeIntVar(0, 100, "rabbits");
|
|
|
|
|
final IntVar pheasants = solver.makeIntVar(0, 100, "pheasants");
|
|
|
|
|
solver.addConstraint(solver.makeEquality(solver.makeSum(rabbits, pheasants), 20));
|
|
|
|
|
solver.addConstraint(solver.makeEquality(
|
|
|
|
|
solver.makeSum(solver.makeProd(rabbits, 4), solver.makeProd(pheasants, 2)), 56));
|
|
|
|
|
final DecisionBuilder db =
|
|
|
|
|
solver.makePhase(rabbits, pheasants, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
|
|
|
|
|
solver.newSearch(db);
|
|
|
|
|
solver.nextSolution();
|
|
|
|
|
assertEquals(8, rabbits.value());
|
|
|
|
|
assertEquals(12, pheasants.value());
|
|
|
|
|
solver.endSearch();
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// A Decision builder that does nothing.
|
|
|
|
|
static class DummyDecisionBuilder extends JavaDecisionBuilder {
|
|
|
|
|
@Override
|
|
|
|
|
public Decision next(Solver solver) throws Solver.FailException {
|
|
|
|
|
System.out.println("In Dummy Decision Builder");
|
|
|
|
|
return null;
|
2020-09-23 12:10:52 +02:00
|
|
|
}
|
2021-08-31 11:58:46 +02:00
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
public String toString() {
|
|
|
|
|
return "DummyDecisionBuilder";
|
2020-09-23 12:10:52 +02:00
|
|
|
}
|
2019-03-01 09:41:22 +01:00
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
@Test
|
2021-08-31 11:58:46 +02:00
|
|
|
public void testDummyDecisionBuilder() {
|
|
|
|
|
final Solver solver = new Solver("testDummyDecisionBuilder");
|
|
|
|
|
final DecisionBuilder db = new DummyDecisionBuilder();
|
|
|
|
|
assertTrue(solver.solve(db));
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* A decision builder that fails.
|
|
|
|
|
*/
|
|
|
|
|
static class FailDecisionBuilder extends JavaDecisionBuilder {
|
|
|
|
|
@Override
|
|
|
|
|
public Decision next(Solver solver) throws Solver.FailException {
|
|
|
|
|
System.out.println("In Fail Decision Builder");
|
|
|
|
|
solver.fail();
|
|
|
|
|
return null;
|
2020-09-23 12:10:52 +02:00
|
|
|
}
|
2021-08-31 11:58:46 +02:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testFailDecisionBuilder() {
|
|
|
|
|
final Solver solver = new Solver("testFailDecisionBuilder");
|
|
|
|
|
final DecisionBuilder db = new FailDecisionBuilder();
|
|
|
|
|
assertFalse(solver.solve(db));
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/** Golomb Ruler test */
|
|
|
|
|
@Test
|
|
|
|
|
public void testGolombRuler() {
|
|
|
|
|
final int m = 8;
|
|
|
|
|
final Solver solver = new Solver("GR " + m);
|
|
|
|
|
|
|
|
|
|
final IntVar[] ticks = solver.makeIntVarArray(m, 0, (1 << (m + 1)) - 1, "ticks");
|
|
|
|
|
|
|
|
|
|
solver.addConstraint(solver.makeEquality(ticks[0], 0));
|
|
|
|
|
|
|
|
|
|
for (int i = 0; i < ticks.length - 1; i++) {
|
|
|
|
|
solver.addConstraint(solver.makeLess(ticks[i], ticks[i + 1]));
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
final ArrayList<IntVar> diff = new ArrayList<>();
|
|
|
|
|
for (int i = 0; i < m - 1; i++) {
|
|
|
|
|
for (int j = i + 1; j < m; j++) {
|
|
|
|
|
diff.add(solver.makeDifference(ticks[j], ticks[i]).var());
|
2020-09-23 12:10:52 +02:00
|
|
|
}
|
2021-08-31 11:58:46 +02:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
solver.addConstraint(solver.makeAllDifferent(diff.toArray(new IntVar[0]), true));
|
|
|
|
|
|
|
|
|
|
// break symetries
|
|
|
|
|
if (m > 2) {
|
|
|
|
|
solver.addConstraint(solver.makeLess(diff.get(0), Iterables.getLast(diff)));
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
final OptimizeVar opt = solver.makeMinimize(ticks[m - 1], 1);
|
|
|
|
|
final DecisionBuilder db =
|
|
|
|
|
solver.makePhase(ticks, Solver.CHOOSE_MIN_SIZE_LOWEST_MIN, Solver.ASSIGN_MIN_VALUE);
|
|
|
|
|
final SearchMonitor log = solver.makeSearchLog(10000, opt);
|
|
|
|
|
assertTrue(solver.solve(db, opt, log));
|
|
|
|
|
assertEquals(34, opt.best());
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testElementFunction() {
|
|
|
|
|
final Solver solver = new Solver("testElementFunction");
|
|
|
|
|
final IntVar index = solver.makeIntVar(0, 10, "index");
|
|
|
|
|
final IntExpr element = solver.makeElement((long x) -> x * 2, index);
|
|
|
|
|
assertEquals(0, element.min());
|
|
|
|
|
assertEquals(20, element.max());
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testSolverParameters() {
|
2021-12-10 16:59:43 +01:00
|
|
|
final ConstraintSolverParameters parameters =
|
|
|
|
|
Solver.defaultSolverParameters().toBuilder().setTraceSearch(true).build();
|
2021-08-31 11:58:46 +02:00
|
|
|
final Solver solver = new Solver("testSolverParameters", parameters);
|
|
|
|
|
final ConstraintSolverParameters stored = solver.parameters();
|
|
|
|
|
assertTrue(stored.getTraceSearch());
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testRegularLimitParameters() {
|
|
|
|
|
final Solver solver = new Solver("testRegularLimitParameters");
|
|
|
|
|
final RegularLimitParameters protoLimit =
|
2021-12-10 16:59:43 +01:00
|
|
|
solver.makeDefaultRegularLimitParameters().toBuilder().setFailures(20000).build();
|
2021-08-31 11:58:46 +02:00
|
|
|
assertEquals(20000, protoLimit.getFailures());
|
|
|
|
|
final SearchLimit limit = solver.makeLimit(protoLimit);
|
|
|
|
|
assertNotNull(limit);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// verify Closure in Decision.
|
|
|
|
|
@Test
|
|
|
|
|
public void testClosureDecision() {
|
|
|
|
|
final StringProperty call = new StringProperty("");
|
|
|
|
|
final Solver solver = new Solver("ClosureDecisionTest");
|
|
|
|
|
final Decision decision = solver.makeDecision(
|
|
|
|
|
(Solver s) -> call.setValue("Apply"), (Solver s) -> call.setValue("Refute"));
|
|
|
|
|
System.gc();
|
|
|
|
|
|
|
|
|
|
decision.apply(solver);
|
|
|
|
|
assertEquals("Apply", call.toString());
|
|
|
|
|
|
|
|
|
|
decision.refute(solver);
|
|
|
|
|
assertEquals("Refute", call.toString());
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Test
|
|
|
|
|
public void testSolverInClosureDecision() {
|
|
|
|
|
final Solver solver = new Solver("SolverTestName");
|
|
|
|
|
final String modelName = solver.model_name();
|
|
|
|
|
// Lambda can only capture final or implicit final.
|
|
|
|
|
final AtomicInteger countApply = new AtomicInteger(0);
|
|
|
|
|
final AtomicInteger countRefute = new AtomicInteger(0);
|
|
|
|
|
assertEquals(0, countApply.intValue());
|
|
|
|
|
assertEquals(0, countRefute.intValue());
|
|
|
|
|
final Decision decision = solver.makeDecision(
|
2022-02-16 16:19:26 +01:00
|
|
|
(Solver s)
|
|
|
|
|
-> {
|
2021-08-31 11:58:46 +02:00
|
|
|
assertEquals(s.model_name(), modelName);
|
|
|
|
|
countApply.addAndGet(1);
|
|
|
|
|
},
|
|
|
|
|
(Solver s) -> {
|
|
|
|
|
assertEquals(s.model_name(), modelName);
|
|
|
|
|
countRefute.addAndGet(1);
|
|
|
|
|
});
|
|
|
|
|
System.gc(); // verify lambda are kept alive
|
|
|
|
|
|
|
|
|
|
decision.apply(solver);
|
|
|
|
|
assertEquals(1, countApply.intValue());
|
|
|
|
|
assertEquals(0, countRefute.intValue());
|
|
|
|
|
|
|
|
|
|
decision.refute(solver);
|
|
|
|
|
assertEquals(1, countApply.intValue());
|
|
|
|
|
assertEquals(1, countRefute.intValue());
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// A Decision builder that does nothing
|
|
|
|
|
public static class ActionDecisionBuilder extends JavaDecisionBuilder {
|
|
|
|
|
Consumer<Solver> apply;
|
|
|
|
|
Consumer<Solver> refute;
|
|
|
|
|
boolean passed;
|
|
|
|
|
|
|
|
|
|
public ActionDecisionBuilder(Consumer<Solver> a, Consumer<Solver> r) {
|
|
|
|
|
apply = a;
|
|
|
|
|
refute = r;
|
|
|
|
|
passed = false;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
public Decision next(Solver solver) throws Solver.FailException {
|
|
|
|
|
if (passed) {
|
|
|
|
|
return null;
|
2020-09-23 12:10:52 +02:00
|
|
|
}
|
2021-08-31 11:58:46 +02:00
|
|
|
passed = true;
|
|
|
|
|
return solver.makeDecision(apply, refute);
|
2019-03-01 09:41:22 +01:00
|
|
|
}
|
2021-08-31 11:58:46 +02:00
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
public String toString() {
|
|
|
|
|
return "ActionDecisionBuilder";
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Tests the ActionDecisionBuilder.
|
|
|
|
|
@Test
|
|
|
|
|
public void testActionDecisionBuilder() {
|
|
|
|
|
final Solver solver = new Solver("testActionDecisionBuilder");
|
|
|
|
|
// Lambda can only capture final or implicit final
|
|
|
|
|
final AtomicInteger countApply = new AtomicInteger(0);
|
|
|
|
|
final AtomicInteger countRefute = new AtomicInteger(0);
|
|
|
|
|
assertEquals(0, countApply.intValue());
|
|
|
|
|
assertEquals(0, countRefute.intValue());
|
|
|
|
|
final DecisionBuilder db = new ActionDecisionBuilder(
|
2022-02-16 16:19:26 +01:00
|
|
|
(Solver s) -> countApply.addAndGet(1), (Solver s) -> countRefute.addAndGet(1));
|
2021-08-31 11:58:46 +02:00
|
|
|
solver.newSearch(db);
|
|
|
|
|
assertTrue(solver.nextSolution());
|
|
|
|
|
assertEquals(1, countApply.intValue());
|
|
|
|
|
assertEquals(0, countRefute.intValue());
|
|
|
|
|
assertTrue(solver.nextSolution());
|
|
|
|
|
assertEquals(1, countApply.intValue());
|
|
|
|
|
assertEquals(1, countRefute.intValue());
|
|
|
|
|
solver.endSearch();
|
2019-03-01 09:41:22 +01:00
|
|
|
}
|
|
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
// ----- LocalSearch Test -----
|
2020-09-14 23:49:23 +02:00
|
|
|
private static class MoveOneVar extends IntVarLocalSearchOperator {
|
2019-03-01 09:41:22 +01:00
|
|
|
public MoveOneVar(IntVar[] variables) {
|
|
|
|
|
super(variables);
|
|
|
|
|
variableIndex = 0;
|
|
|
|
|
moveUp = false;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
protected boolean oneNeighbor() {
|
|
|
|
|
long currentValue = oldValue(variableIndex);
|
|
|
|
|
if (moveUp) {
|
|
|
|
|
setValue(variableIndex, currentValue + 1);
|
|
|
|
|
variableIndex = (variableIndex + 1) % size();
|
|
|
|
|
} else {
|
|
|
|
|
setValue(variableIndex, currentValue - 1);
|
|
|
|
|
}
|
|
|
|
|
moveUp = !moveUp;
|
|
|
|
|
return true;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
public void onStart() {}
|
|
|
|
|
|
|
|
|
|
// Index of the next variable to try to restore
|
|
|
|
|
private long variableIndex;
|
|
|
|
|
// Direction of the modification.
|
|
|
|
|
private boolean moveUp;
|
|
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
@Test
|
2021-08-31 11:58:46 +02:00
|
|
|
public void testSolver() {
|
|
|
|
|
final Solver solver = new Solver("Solver");
|
|
|
|
|
final IntVar[] vars = solver.makeIntVarArray(4, 0, 4, "vars");
|
|
|
|
|
final IntVar sumVar = solver.makeSum(vars).var();
|
|
|
|
|
final OptimizeVar obj = solver.makeMinimize(sumVar, 1);
|
|
|
|
|
final DecisionBuilder db =
|
2019-03-01 09:41:22 +01:00
|
|
|
solver.makePhase(vars, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MAX_VALUE);
|
2021-08-31 11:58:46 +02:00
|
|
|
final MoveOneVar moveOneVar = new MoveOneVar(vars);
|
|
|
|
|
final LocalSearchPhaseParameters lsParams =
|
2020-09-23 12:10:52 +02:00
|
|
|
solver.makeLocalSearchPhaseParameters(sumVar, moveOneVar, db);
|
2021-08-31 11:58:46 +02:00
|
|
|
final DecisionBuilder ls = solver.makeLocalSearchPhase(vars, db, lsParams);
|
|
|
|
|
final SolutionCollector collector = solver.makeLastSolutionCollector();
|
2019-03-01 09:41:22 +01:00
|
|
|
collector.addObjective(sumVar);
|
2021-08-31 11:58:46 +02:00
|
|
|
final SearchMonitor log = solver.makeSearchLog(1000, obj);
|
|
|
|
|
|
|
|
|
|
assertTrue(solver.solve(ls, collector, obj, log));
|
2019-03-01 09:41:22 +01:00
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
private static class SumFilter extends IntVarLocalSearchFilter {
|
2019-03-01 09:41:22 +01:00
|
|
|
public SumFilter(IntVar[] vars) {
|
|
|
|
|
super(vars);
|
|
|
|
|
sum = 0;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
protected void onSynchronize(Assignment unusedDelta) {
|
|
|
|
|
sum = 0;
|
|
|
|
|
for (int index = 0; index < size(); ++index) {
|
|
|
|
|
sum += value(index);
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
2019-08-06 15:57:08 -07:00
|
|
|
public boolean accept(Assignment delta, Assignment unusedDeltadelta, long unusedObjectiveMin,
|
2020-09-23 12:10:52 +02:00
|
|
|
long unusedObjectiveMax) {
|
2019-03-01 09:41:22 +01:00
|
|
|
AssignmentIntContainer solutionDelta = delta.intVarContainer();
|
|
|
|
|
int solutionDeltaSize = solutionDelta.size();
|
|
|
|
|
|
|
|
|
|
for (int i = 0; i < solutionDeltaSize; ++i) {
|
|
|
|
|
if (!solutionDelta.element(i).activated()) {
|
|
|
|
|
return true;
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
long newSum = sum;
|
|
|
|
|
for (int index = 0; index < solutionDeltaSize; ++index) {
|
|
|
|
|
int touchedVar = index(solutionDelta.element(index).var());
|
|
|
|
|
long oldValue = value(touchedVar);
|
|
|
|
|
long newValue = solutionDelta.element(index).value();
|
|
|
|
|
newSum += newValue - oldValue;
|
|
|
|
|
}
|
|
|
|
|
return newSum < sum;
|
|
|
|
|
}
|
|
|
|
|
private long sum;
|
|
|
|
|
}
|
|
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
private static class StringProperty {
|
|
|
|
|
public StringProperty(String initialValue) {
|
|
|
|
|
value = initialValue;
|
|
|
|
|
}
|
|
|
|
|
public void setValue(String newValue) {
|
|
|
|
|
value = newValue;
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
public String toString() {
|
|
|
|
|
return value;
|
|
|
|
|
}
|
|
|
|
|
private String value;
|
|
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
@Test
|
2021-08-31 11:58:46 +02:00
|
|
|
public void testSolverWithLocalSearchFilter() {
|
|
|
|
|
final Solver solver = new Solver("Solver");
|
|
|
|
|
final IntVar[] vars = solver.makeIntVarArray(4, 0, 4, "vars");
|
|
|
|
|
final IntVar sumVar = solver.makeSum(vars).var();
|
|
|
|
|
final OptimizeVar obj = solver.makeMinimize(sumVar, 1);
|
|
|
|
|
final DecisionBuilder db =
|
2019-03-01 09:41:22 +01:00
|
|
|
solver.makePhase(vars, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MAX_VALUE);
|
|
|
|
|
MoveOneVar moveOneVar = new MoveOneVar(vars);
|
|
|
|
|
SumFilter filter = new SumFilter(vars);
|
|
|
|
|
IntVarLocalSearchFilter[] filters = new IntVarLocalSearchFilter[1];
|
|
|
|
|
filters[0] = filter;
|
2021-08-31 11:58:46 +02:00
|
|
|
LocalSearchFilterManager filterManager = new LocalSearchFilterManager(filters);
|
2019-03-01 09:41:22 +01:00
|
|
|
LocalSearchPhaseParameters lsParams =
|
2021-08-31 11:58:46 +02:00
|
|
|
solver.makeLocalSearchPhaseParameters(sumVar, moveOneVar, db, null, filterManager);
|
2019-03-01 09:41:22 +01:00
|
|
|
DecisionBuilder ls = solver.makeLocalSearchPhase(vars, db, lsParams);
|
|
|
|
|
SolutionCollector collector = solver.makeLastSolutionCollector();
|
|
|
|
|
collector.addObjective(sumVar);
|
|
|
|
|
SearchMonitor log = solver.makeSearchLog(1000, obj);
|
|
|
|
|
solver.solve(ls, collector, obj, log);
|
|
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
private static class OneVarLns extends BaseLns {
|
2019-03-01 09:41:22 +01:00
|
|
|
public OneVarLns(IntVar[] vars) {
|
|
|
|
|
super(vars);
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
public void initFragments() {
|
2021-08-31 11:58:46 +02:00
|
|
|
index = 0;
|
2019-03-01 09:41:22 +01:00
|
|
|
}
|
|
|
|
|
|
|
|
|
|
@Override
|
|
|
|
|
public boolean nextFragment() {
|
|
|
|
|
int size = size();
|
2021-08-31 11:58:46 +02:00
|
|
|
if (index < size) {
|
|
|
|
|
appendToFragment(index);
|
|
|
|
|
++index;
|
2019-03-01 09:41:22 +01:00
|
|
|
return true;
|
|
|
|
|
} else {
|
|
|
|
|
return false;
|
|
|
|
|
}
|
|
|
|
|
}
|
2021-08-31 11:58:46 +02:00
|
|
|
private int index;
|
2019-03-01 09:41:22 +01:00
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
@Test
|
2021-08-31 11:58:46 +02:00
|
|
|
public void testSolverLns() {
|
|
|
|
|
final Solver solver = new Solver("Solver");
|
|
|
|
|
final IntVar[] vars = solver.makeIntVarArray(4, 0, 4, "vars");
|
|
|
|
|
final IntVar sumVar = solver.makeSum(vars).var();
|
|
|
|
|
final OptimizeVar obj = solver.makeMinimize(sumVar, 1);
|
|
|
|
|
final DecisionBuilder db =
|
2019-03-01 09:41:22 +01:00
|
|
|
solver.makePhase(vars, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MAX_VALUE);
|
2021-08-31 11:58:46 +02:00
|
|
|
final OneVarLns oneVarLns = new OneVarLns(vars);
|
|
|
|
|
final LocalSearchPhaseParameters lsParams =
|
2020-09-23 12:10:52 +02:00
|
|
|
solver.makeLocalSearchPhaseParameters(sumVar, oneVarLns, db);
|
2021-08-31 11:58:46 +02:00
|
|
|
final DecisionBuilder ls = solver.makeLocalSearchPhase(vars, db, lsParams);
|
|
|
|
|
final SolutionCollector collector = solver.makeLastSolutionCollector();
|
2019-03-01 09:41:22 +01:00
|
|
|
collector.addObjective(sumVar);
|
2021-08-31 11:58:46 +02:00
|
|
|
final SearchMonitor log = solver.makeSearchLog(1000, obj);
|
2019-03-01 09:41:22 +01:00
|
|
|
solver.solve(ls, collector, obj, log);
|
|
|
|
|
}
|
|
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
// ----- SearchLog Test -----
|
|
|
|
|
// TODO(user): Improve search log tests; currently only tests coverage and callback.
|
|
|
|
|
// note: this is more or less what is done in search_test.cc
|
2019-02-04 16:48:12 +01:00
|
|
|
private static void runSearchLog(SearchMonitor searchlog) {
|
|
|
|
|
searchlog.enterSearch();
|
|
|
|
|
searchlog.exitSearch();
|
|
|
|
|
searchlog.acceptSolution();
|
|
|
|
|
searchlog.atSolution();
|
|
|
|
|
searchlog.beginFail();
|
|
|
|
|
searchlog.noMoreSolutions();
|
|
|
|
|
searchlog.beginInitialPropagation();
|
|
|
|
|
searchlog.endInitialPropagation();
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
// Simple Coverage test...
|
2020-09-14 23:49:23 +02:00
|
|
|
@Test
|
2021-08-31 11:58:46 +02:00
|
|
|
public void testSearchLog() {
|
|
|
|
|
final Solver solver = new Solver("TestSearchLog");
|
|
|
|
|
final IntVar var = solver.makeIntVar(1, 1, "Variable");
|
|
|
|
|
solver.makeMinimize(var, 1);
|
|
|
|
|
final SearchMonitor searchlog = solver.makeSearchLog(0);
|
2019-02-04 16:48:12 +01:00
|
|
|
runSearchLog(searchlog);
|
|
|
|
|
}
|
|
|
|
|
|
2020-09-14 23:49:23 +02:00
|
|
|
private static class SearchCount implements Supplier<String> {
|
2021-08-31 11:58:46 +02:00
|
|
|
public SearchCount(AtomicInteger initialCount) {
|
|
|
|
|
count = initialCount;
|
2019-02-04 16:48:12 +01:00
|
|
|
}
|
|
|
|
|
@Override
|
2019-02-08 13:08:37 +01:00
|
|
|
public String get() {
|
|
|
|
|
count.addAndGet(1);
|
|
|
|
|
return "display callback called...";
|
2019-02-04 16:48:12 +01:00
|
|
|
}
|
2021-08-31 11:58:46 +02:00
|
|
|
private final AtomicInteger count;
|
2019-02-04 16:48:12 +01:00
|
|
|
}
|
|
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
@Test
|
|
|
|
|
public void testSearchLogWithCallback() {
|
|
|
|
|
final Solver solver = new Solver("TestSearchLog");
|
|
|
|
|
final AtomicInteger count = new AtomicInteger(0);
|
2021-09-07 18:39:00 +02:00
|
|
|
final SearchMonitor searchlog = solver.makeSearchLog(0, // branch period
|
2019-02-04 16:48:12 +01:00
|
|
|
new SearchCount(count));
|
2021-08-31 11:58:46 +02:00
|
|
|
System.gc(); // verify SearchCount is kept alive by the searchlog
|
2019-02-04 16:48:12 +01:00
|
|
|
runSearchLog(searchlog);
|
2021-08-31 11:58:46 +02:00
|
|
|
assertEquals(1, count.intValue());
|
|
|
|
|
}
|
2019-02-08 13:08:37 +01:00
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
@Test
|
|
|
|
|
public void testSearchLogWithLambdaCallback() {
|
|
|
|
|
final Solver solver = new Solver("TestSearchLog");
|
|
|
|
|
final AtomicInteger count = new AtomicInteger(0);
|
2021-09-07 18:39:00 +02:00
|
|
|
final SearchMonitor searchlog = solver.makeSearchLog(0, // branch period
|
2021-08-31 11:58:46 +02:00
|
|
|
() -> {
|
|
|
|
|
count.addAndGet(1);
|
|
|
|
|
return "display callback called...";
|
|
|
|
|
});
|
|
|
|
|
System.gc(); // verify lambda is kept alive by the searchlog
|
|
|
|
|
runSearchLog(searchlog);
|
|
|
|
|
assertEquals(1, count.intValue());
|
2019-02-04 16:48:12 +01:00
|
|
|
}
|
|
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
@Test
|
|
|
|
|
public void testSearchLogWithIntVarCallback() {
|
|
|
|
|
final Solver solver = new Solver("TestSearchLog");
|
|
|
|
|
final IntVar var = solver.makeIntVar(1, 1, "Variable");
|
|
|
|
|
final AtomicInteger count = new AtomicInteger(0);
|
2021-09-07 18:39:00 +02:00
|
|
|
final SearchMonitor searchlog = solver.makeSearchLog(0, // branch period
|
2019-02-08 13:08:37 +01:00
|
|
|
var, // IntVar to monitor
|
|
|
|
|
new SearchCount(count));
|
2021-08-31 11:58:46 +02:00
|
|
|
System.gc();
|
2019-02-08 13:08:37 +01:00
|
|
|
runSearchLog(searchlog);
|
2021-08-31 11:58:46 +02:00
|
|
|
assertEquals(1, count.intValue());
|
2019-02-08 13:08:37 +01:00
|
|
|
}
|
|
|
|
|
|
2021-08-31 11:58:46 +02:00
|
|
|
@Test
|
|
|
|
|
public void testSearchLogWithObjectiveCallback() {
|
|
|
|
|
final Solver solver = new Solver("TestSearchLog");
|
|
|
|
|
final IntVar var = solver.makeIntVar(1, 1, "Variable");
|
|
|
|
|
final OptimizeVar objective = solver.makeMinimize(var, 1);
|
|
|
|
|
final AtomicInteger count = new AtomicInteger(0);
|
2021-09-07 18:39:00 +02:00
|
|
|
final SearchMonitor searchlog = solver.makeSearchLog(0, // branch period
|
2019-02-04 16:48:12 +01:00
|
|
|
objective, // objective var to monitor
|
|
|
|
|
new SearchCount(count));
|
2021-08-31 11:58:46 +02:00
|
|
|
System.gc();
|
2019-02-04 16:48:12 +01:00
|
|
|
runSearchLog(searchlog);
|
2021-08-31 11:58:46 +02:00
|
|
|
assertEquals(1, count.intValue());
|
2019-02-04 16:48:12 +01:00
|
|
|
}
|
|
|
|
|
}
|
