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