1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 package org.sat4j.pb.constraints.pb;
29
30 import java.math.BigInteger;
31
32 import org.sat4j.core.VecInt;
33 import org.sat4j.minisat.constraints.cnf.Lits;
34 import org.sat4j.minisat.core.ILits;
35 import org.sat4j.minisat.core.VarActivityListener;
36 import org.sat4j.specs.IteratorInt;
37
38
39
40
41
42 public class ConflictMap extends MapPb implements IConflict {
43
44 private final ILits voc;
45
46
47
48
49 protected BigInteger currentSlack;
50
51 protected int currentLevel;
52
53
54
55
56
57
58 protected VecInt[] byLevel;
59
60
61
62
63
64
65
66
67
68
69 public static IConflict createConflict(PBConstr cpb, int level) {
70 return new ConflictMap(cpb, level);
71 }
72
73 ConflictMap(PBConstr cpb, int level) {
74 super(cpb);
75 this.voc = cpb.getVocabulary();
76 this.currentLevel = level;
77 initStructures();
78 }
79
80 private void initStructures() {
81 currentSlack = BigInteger.ZERO;
82 byLevel = new VecInt[levelToIndex(currentLevel) + 1];
83 int ilit, litLevel, index;
84 BigInteger tmp;
85 for (int i = 0; i < size(); i++) {
86 ilit = weightedLits.getLit(i);
87 litLevel = voc.getLevel(ilit);
88
89 tmp = weightedLits.getCoef(i);
90 if ((tmp.signum() > 0)
91 && (((!voc.isFalsified(ilit)) || litLevel == currentLevel)))
92 currentSlack = currentSlack.add(tmp);
93
94 index = levelToIndex(litLevel);
95 if (byLevel[index] == null) {
96 byLevel[index] = new VecInt();
97 }
98 byLevel[index].push(ilit);
99 }
100 }
101
102
103
104
105
106
107
108 private static final int levelToIndex(int level) {
109 return level + 1;
110 }
111
112
113
114
115
116
117
118 private static final int indexToLevel(int indLevel) {
119 return indLevel - 1;
120 }
121
122
123
124
125 protected BigInteger coefMult = BigInteger.ZERO;
126
127 protected BigInteger coefMultCons = BigInteger.ZERO;
128
129
130
131
132
133
134
135
136
137
138
139 public BigInteger resolve(PBConstr cpb, int litImplied,
140 VarActivityListener val) {
141 assert litImplied > 1;
142 int nLitImplied = litImplied ^ 1;
143 if (cpb == null || !weightedLits.containsKey(nLitImplied)) {
144
145
146 int litLevel = levelToIndex(voc.getLevel(litImplied));
147 int lit = 0;
148 if (byLevel[litLevel] != null) {
149 if (byLevel[litLevel].contains(litImplied)) {
150 lit = litImplied;
151 assert weightedLits.containsKey(litImplied);
152 } else if (byLevel[litLevel].contains(nLitImplied)) {
153 lit = nLitImplied;
154 assert weightedLits.containsKey(nLitImplied);
155 }
156 }
157
158 if (lit > 0) {
159 byLevel[litLevel].remove(lit);
160 if (byLevel[0] == null)
161 byLevel[0] = new VecInt();
162 byLevel[0].push(lit);
163 }
164 return degree;
165 }
166
167 assert slackConflict().signum() <= 0;
168 assert degree.signum() >= 0;
169
170
171
172 BigInteger[] coefsCons = null;
173 BigInteger degreeCons = cpb.getDegree();
174
175
176 int ind = 0;
177 while (cpb.get(ind) != litImplied)
178 ind++;
179
180 assert cpb.get(ind) == litImplied;
181 assert cpb.getCoef(ind) != BigInteger.ZERO;
182
183 if (cpb.getCoef(ind).equals(BigInteger.ONE)) {
184
185
186 coefMultCons = weightedLits.get(nLitImplied);
187 coefMult = BigInteger.ONE;
188
189 degreeCons = degreeCons.multiply(coefMultCons);
190 } else {
191 if (weightedLits.get(nLitImplied).equals(BigInteger.ONE)) {
192
193
194 coefMult = cpb.getCoef(ind);
195 coefMultCons = BigInteger.ONE;
196
197 degree = degree.multiply(coefMult);
198 } else {
199
200
201 WatchPb wpb = (WatchPb) cpb;
202 coefsCons = wpb.getCoefs();
203 assert positiveCoefs(coefsCons);
204 degreeCons = reduceUntilConflict(litImplied, ind, coefsCons,
205 wpb);
206
207 degreeCons = degreeCons.multiply(coefMultCons);
208 degree = degree.multiply(coefMult);
209 }
210
211
212 if (!coefMult.equals(BigInteger.ONE))
213 for (int i = 0; i < size(); i++) {
214 changeCoef(i, weightedLits.getCoef(i).multiply(coefMult));
215 }
216 }
217
218 assert slackConflict().signum() <= 0;
219
220
221 degree = cuttingPlane(cpb, degreeCons, coefsCons, coefMultCons, val);
222
223
224 assert !weightedLits.containsKey(litImplied);
225 assert !weightedLits.containsKey(nLitImplied);
226
227 assert getLevelByLevel(litImplied) == -1;
228 assert getLevelByLevel(nLitImplied) == -1;
229 assert degree.signum() > 0;
230 assert slackConflict().signum() <= 0;
231
232
233 degree = saturation();
234 assert slackConflict().signum() <= 0;
235
236 return degree;
237 }
238
239 protected BigInteger reduceUntilConflict(int litImplied, int ind,
240 BigInteger[] reducedCoefs, WatchPb wpb) {
241 BigInteger slackResolve = BigInteger.ONE.negate();
242 BigInteger slackThis = BigInteger.ZERO;
243 BigInteger slackIndex;
244 BigInteger slackConflict = slackConflict();
245 BigInteger ppcm;
246 BigInteger reducedDegree = wpb.getDegree();
247 BigInteger previousCoefLitImplied = BigInteger.ZERO;
248 BigInteger tmp;
249 BigInteger coefLitImplied = weightedLits.get(litImplied ^ 1);
250
251 do {
252 if (slackResolve.signum() >= 0) {
253 assert slackThis.signum() > 0;
254 tmp = reduceInConstraint(wpb, reducedCoefs, ind, reducedDegree);
255 assert ((tmp.compareTo(reducedDegree) < 0) && (tmp
256 .compareTo(BigInteger.ONE) >= 0));
257 reducedDegree = tmp;
258 }
259
260 assert weightedLits.get(litImplied ^ 1).signum() > 0;
261 assert reducedCoefs[ind].signum() > 0;
262
263 if (!reducedCoefs[ind].equals(previousCoefLitImplied)) {
264 assert coefLitImplied.equals(weightedLits.get(litImplied ^ 1));
265 ppcm = ppcm(reducedCoefs[ind], coefLitImplied);
266 assert ppcm.signum() > 0;
267 coefMult = ppcm.divide(coefLitImplied);
268 coefMultCons = ppcm.divide(reducedCoefs[ind]);
269
270 assert coefMultCons.signum() > 0;
271 assert coefMult.signum() > 0;
272 assert coefMult.multiply(coefLitImplied).equals(
273 coefMultCons.multiply(reducedCoefs[ind]));
274 previousCoefLitImplied = reducedCoefs[ind];
275 }
276
277
278 slackThis = wpb.slackConstraint(reducedCoefs, reducedDegree)
279 .multiply(coefMultCons);
280 assert slackConflict.equals(slackConflict());
281 slackIndex = slackConflict.multiply(coefMult);
282 assert slackIndex.signum() <= 0;
283
284 slackResolve = slackThis.add(slackIndex);
285 } while (slackResolve.signum() >= 0);
286 assert coefMult.multiply(weightedLits.get(litImplied ^ 1)).equals(
287 coefMultCons.multiply(reducedCoefs[ind]));
288 return reducedDegree;
289
290 }
291
292
293
294
295 public BigInteger slackConflict() {
296 BigInteger poss = BigInteger.ZERO;
297 BigInteger tmp;
298
299 for (int i = 0; i < size(); i++) {
300 tmp = weightedLits.getCoef(i);
301 if (tmp.signum() != 0 && !voc.isFalsified(weightedLits.getLit(i)))
302 poss = poss.add(tmp);
303 }
304 return poss.subtract(degree);
305 }
306
307 public boolean oldIsAssertive(int dl) {
308 BigInteger tmp;
309 int lit;
310 BigInteger slack = computeSlack(dl).subtract(degree);
311 if (slack.signum() < 0)
312 return false;
313 for (int i = 0; i < size(); i++) {
314 tmp = weightedLits.getCoef(i);
315 lit = weightedLits.getLit(i);
316 if ((tmp.signum() > 0)
317 && (voc.isUnassigned(lit) || voc.getLevel(lit) >= dl)
318 && (slack.compareTo(tmp) < 0))
319 return true;
320 }
321 return false;
322 }
323
324
325 private BigInteger computeSlack(int dl) {
326 BigInteger slack = BigInteger.ZERO;
327 int lit;
328 BigInteger tmp;
329 for (int i = 0; i < size(); i++) {
330 tmp = weightedLits.getCoef(i);
331 lit = weightedLits.getLit(i);
332 if ((tmp.signum() > 0)
333 && (((!voc.isFalsified(lit)) || voc.getLevel(lit) >= dl)))
334 slack = slack.add(tmp);
335 }
336 return slack;
337 }
338
339
340
341
342
343
344
345
346
347 public boolean isAssertive(int dl) {
348 assert dl <= currentLevel;
349 assert dl <= currentLevel;
350
351 currentLevel = dl;
352
353 BigInteger slack = currentSlack.subtract(degree);
354 if (slack.signum() < 0)
355 return false;
356 return isImplyingLiteral(slack);
357 }
358
359
360
361
362 private boolean isImplyingLiteral(BigInteger slack) {
363
364 int unassigned = levelToIndex(-1);
365 int lit;
366 if (byLevel[unassigned] != null) {
367 for (IteratorInt iterator = byLevel[unassigned].iterator(); iterator
368 .hasNext();) {
369 lit = iterator.next();
370 if (slack.compareTo(weightedLits.get(lit)) < 0) {
371 assertiveLiteral = weightedLits.allLits.get(lit);
372 return true;
373 }
374 }
375 }
376
377 BigInteger tmp;
378 int level = levelToIndex(currentLevel);
379 if (byLevel[level] != null)
380 for (IteratorInt iterator = byLevel[level].iterator(); iterator
381 .hasNext();) {
382 lit = iterator.next();
383 tmp = weightedLits.get(lit);
384 if (tmp != null && slack.compareTo(tmp) < 0) {
385 assertiveLiteral = weightedLits.allLits.get(lit);
386 return true;
387 }
388 }
389 return false;
390 }
391
392
393
394
395
396 private boolean isImplyingLiteralOrdered(int dl, BigInteger slack) {
397 int ilit, litLevel;
398 for (int i = 0; i < size(); i++) {
399 ilit = weightedLits.getLit(i);
400 litLevel = voc.getLevel(ilit);
401 if ((litLevel >= dl || voc.isUnassigned(ilit))
402 && (slack.compareTo(weightedLits.getCoef(i)) < 0))
403 return true;
404 }
405 return false;
406 }
407
408
409
410
411
412
413
414
415
416
417
418 protected static BigInteger ppcm(BigInteger a, BigInteger b) {
419 return a.divide(a.gcd(b)).multiply(b);
420 }
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439 public BigInteger reduceInConstraint(WatchPb wpb,
440 final BigInteger[] coefsBis, final int indLitImplied,
441 final BigInteger degreeBis) {
442
443 assert degreeBis.compareTo(BigInteger.ONE) > 0;
444
445 int lit = -1;
446 for (int ind = 0; (ind < wpb.lits.length) && (lit == -1); ind++)
447 if (coefsBis[ind].signum() != 0 && voc.isUnassigned(wpb.lits[ind])) {
448 assert coefsBis[ind].compareTo(degreeBis) < 0;
449 lit = ind;
450 }
451
452
453 if (lit == -1)
454 for (int ind = 0; (ind < wpb.lits.length) && (lit == -1); ind++)
455 if ((coefsBis[ind].signum() != 0)
456 && (voc.isSatisfied(wpb.lits[ind]))
457 && (ind != indLitImplied))
458 lit = ind;
459
460
461 assert lit != -1;
462
463 assert lit != indLitImplied;
464
465
466 BigInteger degUpdate = degreeBis.subtract(coefsBis[lit]);
467 coefsBis[lit] = BigInteger.ZERO;
468
469
470 degUpdate = saturation(coefsBis, degUpdate);
471
472 assert coefsBis[indLitImplied].signum() > 0;
473 assert degreeBis.compareTo(degUpdate) > 0;
474 return degUpdate;
475 }
476
477 static BigInteger saturation(BigInteger[] coefs, BigInteger degree) {
478 assert degree.signum() > 0;
479 BigInteger minimum = degree;
480 for (int i = 0; i < coefs.length; i++) {
481 if (coefs[i].signum() > 0)
482 minimum = minimum.min(coefs[i]);
483 coefs[i] = degree.min(coefs[i]);
484 }
485 if (minimum.equals(degree) && !degree.equals(BigInteger.ONE)) {
486
487
488 degree = BigInteger.ONE;
489 for (int i = 0; i < coefs.length; i++)
490 if (coefs[i].signum() > 0)
491 coefs[i] = degree;
492 }
493 return degree;
494 }
495
496 private static boolean positiveCoefs(final BigInteger[] coefsCons) {
497 for (int i = 0; i < coefsCons.length; i++) {
498 if (coefsCons[i].signum() <= 0)
499 return false;
500 }
501 return true;
502 }
503
504
505
506
507
508
509
510
511
512
513 public int getBacktrackLevel(int maxLevel) {
514
515
516 VecInt lits;
517 int level;
518 int indStop = levelToIndex(maxLevel) - 1;
519 int indStart = levelToIndex(0);
520 BigInteger slack = computeSlack(0).subtract(degree);
521 int previous = 0;
522 for (int indLevel = indStart; indLevel <= indStop; indLevel++) {
523 if (byLevel[indLevel] != null) {
524 level = indexToLevel(indLevel);
525 assert computeSlack(level).subtract(degree).equals(slack);
526 if (isImplyingLiteralOrdered(level, slack)) {
527 break;
528 }
529
530 lits = byLevel[indLevel];
531 int lit;
532 for (IteratorInt iterator = lits.iterator(); iterator.hasNext();) {
533 lit = iterator.next();
534 if (voc.isFalsified(lit)
535 && voc.getLevel(lit) == indexToLevel(indLevel))
536 slack = slack.subtract(weightedLits.get(lit));
537 }
538 if (!lits.isEmpty())
539 previous = level;
540 }
541 }
542 assert previous == oldGetBacktrackLevel(maxLevel);
543 return previous;
544 }
545
546 public int oldGetBacktrackLevel(int maxLevel) {
547 int litLevel;
548 int borneMax = maxLevel;
549 assert oldIsAssertive(borneMax);
550 int borneMin = -1;
551
552
553 for (int i = 0; i < size(); i++) {
554 litLevel = voc.getLevel(weightedLits.getLit(i));
555 if (litLevel < borneMax && litLevel > borneMin
556 && oldIsAssertive(litLevel))
557 borneMax = litLevel;
558 }
559
560
561 int retour = 0;
562 for (int i = 0; i < size(); i++) {
563 litLevel = voc.getLevel(weightedLits.getLit(i));
564 if (litLevel > retour && litLevel < borneMax) {
565 retour = litLevel;
566 }
567 }
568 return retour;
569 }
570
571 public void updateSlack(int level) {
572 int dl = levelToIndex(level);
573 if (byLevel[dl] != null) {
574 int lit;
575 for (IteratorInt iterator = byLevel[dl].iterator(); iterator
576 .hasNext();) {
577 lit = iterator.next();
578 if (voc.isFalsified(lit))
579 currentSlack = currentSlack.add(weightedLits.get(lit));
580 }
581 }
582 }
583
584 @Override
585 void increaseCoef(int lit, BigInteger incCoef) {
586 if ((!voc.isFalsified(lit)) || voc.getLevel(lit) == currentLevel) {
587 currentSlack = currentSlack.add(incCoef);
588 }
589 assert byLevel[levelToIndex(voc.getLevel(lit))].contains(lit);
590 super.increaseCoef(lit, incCoef);
591 }
592
593 @Override
594 void decreaseCoef(int lit, BigInteger decCoef) {
595 if ((!voc.isFalsified(lit)) || voc.getLevel(lit) == currentLevel) {
596 currentSlack = currentSlack.subtract(decCoef);
597 }
598 assert byLevel[levelToIndex(voc.getLevel(lit))].contains(lit);
599 super.decreaseCoef(lit, decCoef);
600 }
601
602 @Override
603 void setCoef(int lit, BigInteger newValue) {
604 int litLevel = voc.getLevel(lit);
605 if ((!voc.isFalsified(lit)) || litLevel == currentLevel) {
606 if (weightedLits.containsKey(lit))
607 currentSlack = currentSlack.subtract(weightedLits.get(lit));
608 currentSlack = currentSlack.add(newValue);
609 }
610 int indLitLevel = levelToIndex(litLevel);
611 if (!weightedLits.containsKey(lit)) {
612 if (byLevel[indLitLevel] == null) {
613 byLevel[indLitLevel] = new VecInt();
614 }
615 byLevel[indLitLevel].push(lit);
616
617 }
618 assert byLevel[indLitLevel] != null;
619 assert byLevel[indLitLevel].contains(lit);
620 super.setCoef(lit, newValue);
621 }
622
623 @Override
624 void changeCoef(int indLit, BigInteger newValue) {
625 int lit = weightedLits.getLit(indLit);
626 int litLevel = voc.getLevel(lit);
627 if ((!voc.isFalsified(lit)) || litLevel == currentLevel) {
628 if (weightedLits.containsKey(lit))
629 currentSlack = currentSlack.subtract(weightedLits.get(lit));
630 currentSlack = currentSlack.add(newValue);
631 }
632 int indLitLevel = levelToIndex(litLevel);
633 assert weightedLits.containsKey(lit);
634 assert byLevel[indLitLevel] != null;
635 assert byLevel[indLitLevel].contains(lit);
636 super.changeCoef(indLit, newValue);
637 }
638
639 @Override
640 void removeCoef(int lit) {
641 int litLevel = voc.getLevel(lit);
642 if ((!voc.isFalsified(lit)) || litLevel == currentLevel) {
643 currentSlack = currentSlack.subtract(weightedLits.get(lit));
644 }
645 int indLitLevel = levelToIndex(litLevel);
646 assert indLitLevel < byLevel.length;
647 assert byLevel[indLitLevel] != null;
648 assert byLevel[indLitLevel].contains(lit);
649 byLevel[indLitLevel].remove(lit);
650 super.removeCoef(lit);
651 }
652
653 private int getLevelByLevel(int lit) {
654 for (int i = 0; i < byLevel.length; i++)
655 if (byLevel[i] != null && byLevel[i].contains(lit))
656 return i;
657 return -1;
658 }
659
660 public boolean slackIsCorrect(int dl) {
661 return currentSlack.equals(computeSlack(dl));
662 }
663
664 @Override
665 public String toString() {
666 int lit;
667 StringBuffer stb = new StringBuffer();
668 for (int i = 0; i < size(); i++) {
669 lit = weightedLits.getLit(i);
670 stb.append(weightedLits.getCoef(i));
671 stb.append(".");
672 stb.append(Lits.toString(lit));
673 stb.append(" ");
674 stb.append("[");
675 stb.append(voc.valueToString(lit));
676 stb.append("@");
677 stb.append(voc.getLevel(lit));
678 stb.append("]");
679 }
680 return stb.toString() + " >= " + degree;
681 }
682
683 }