1 /******************************************************************************* 2 * SAT4J: a SATisfiability library for Java Copyright (C) 2004-2008 Daniel Le Berre 3 * 4 * All rights reserved. This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License v1.0 6 * which accompanies this distribution, and is available at 7 * http://www.eclipse.org/legal/epl-v10.html 8 * 9 * Alternatively, the contents of this file may be used under the terms of 10 * either the GNU Lesser General Public License Version 2.1 or later (the 11 * "LGPL"), in which case the provisions of the LGPL are applicable instead 12 * of those above. If you wish to allow use of your version of this file only 13 * under the terms of the LGPL, and not to allow others to use your version of 14 * this file under the terms of the EPL, indicate your decision by deleting 15 * the provisions above and replace them with the notice and other provisions 16 * required by the LGPL. If you do not delete the provisions above, a recipient 17 * may use your version of this file under the terms of the EPL or the LGPL. 18 * 19 * Based on the pseudo boolean algorithms described in: 20 * A fast pseudo-Boolean constraint solver Chai, D.; Kuehlmann, A. 21 * Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on 22 * Volume 24, Issue 3, March 2005 Page(s): 305 - 317 23 * 24 * and 25 * Heidi E. Dixon, 2004. Automating Pseudo-Boolean Inference within a DPLL 26 * Framework. Ph.D. Dissertation, University of Oregon. 27 *******************************************************************************/ 28 package org.sat4j.pb.constraints.pb; 29 30 import java.math.BigInteger; 31 32 import org.sat4j.minisat.core.ILits; 33 import org.sat4j.minisat.core.UnitPropagationListener; 34 import org.sat4j.specs.ContradictionException; 35 36 public final class PuebloMinWatchPb extends MinWatchPb { 37 38 private static final long serialVersionUID = 1L; 39 40 /** 41 * Constructeur de base des contraintes 42 * 43 * @param voc 44 * Informations sur le vocabulaire employ??? 45 * @param ps 46 * Liste des litt???raux 47 * @param weightedLits 48 * Liste des coefficients 49 * @param moreThan 50 * Indication sur le comparateur 51 * @param degree 52 * Stockage du degr??? de la contrainte 53 */ 54 private PuebloMinWatchPb(ILits voc, int[] lits, BigInteger[] coefs, 55 BigInteger degree) { 56 super(voc, lits, coefs, degree); 57 } 58 59 private PuebloMinWatchPb(ILits voc, IDataStructurePB mpb) { 60 61 super(voc, mpb); 62 } 63 64 /** 65 * @param s 66 * a unit propagation listener 67 * @param voc 68 * the vocabulary 69 * @param lits 70 * the literals 71 * @param coefs 72 * the coefficients 73 * @param degree 74 * the degree of the constraint to normalize. 75 * @return a new PB constraint or null if a trivial inconsistency is 76 * detected. 77 */ 78 public static PuebloMinWatchPb normalizedMinWatchPbNew( 79 UnitPropagationListener s, ILits voc, int[] lits, 80 BigInteger[] coefs, BigInteger degree) 81 throws ContradictionException { 82 // Il ne faut pas modifier les param?tres 83 PuebloMinWatchPb outclause = new PuebloMinWatchPb(voc, lits, coefs, 84 degree); 85 86 if (outclause.degree.signum() <= 0) { 87 return null; 88 } 89 90 outclause.computeWatches(); 91 92 outclause.computePropagation(s); 93 94 return outclause; 95 96 } 97 98 public static WatchPb normalizedWatchPbNew(ILits voc, IDataStructurePB mpb) { 99 return new PuebloMinWatchPb(voc, mpb); 100 } 101 102 @Override 103 protected BigInteger maximalCoefficient(int pIndice) { 104 return coefs[0]; 105 } 106 107 @Override 108 protected BigInteger updateWatched(BigInteger mc, int pIndice) { 109 BigInteger maxCoef = mc; 110 if (watchingCount < size()) { 111 BigInteger upWatchCumul = watchCumul.subtract(coefs[pIndice]); 112 BigInteger borneSup = degree.add(maxCoef); 113 for (int ind = 0; ind < lits.length 114 && upWatchCumul.compareTo(borneSup) < 0; ind++) { 115 if (!voc.isFalsified(lits[ind]) && !watched[ind]) { 116 upWatchCumul = upWatchCumul.add(coefs[ind]); 117 watched[ind] = true; 118 assert watchingCount < size(); 119 watching[watchingCount++] = ind; 120 voc.watch(lits[ind] ^ 1, this); 121 } 122 } 123 watchCumul = upWatchCumul.add(coefs[pIndice]); 124 } 125 return maxCoef; 126 } 127 128 }