summaryrefslogtreecommitdiff
path: root/src/theory/arith/soi_simplex.h
diff options
context:
space:
mode:
authorAina Niemetz <aina.niemetz@gmail.com>2021-04-12 12:31:43 -0700
committerGitHub <noreply@github.com>2021-04-12 19:31:43 +0000
commit7ec30058750611786b1b597816c8a23e28bb5812 (patch)
treee59b1de0078dc04d3a9c212cf9e6ebfd70cbb7f4 /src/theory/arith/soi_simplex.h
parent7361b587e9a1b717dfa906d02f66feb6896e80dd (diff)
Refactor and update copyright headers. (#6316)
Diffstat (limited to 'src/theory/arith/soi_simplex.h')
-rw-r--r--src/theory/arith/soi_simplex.h103
1 files changed, 52 insertions, 51 deletions
diff --git a/src/theory/arith/soi_simplex.h b/src/theory/arith/soi_simplex.h
index 605d23767..f6d97523d 100644
--- a/src/theory/arith/soi_simplex.h
+++ b/src/theory/arith/soi_simplex.h
@@ -1,54 +1,55 @@
-/********************* */
-/*! \file soi_simplex.h
- ** \verbatim
- ** Top contributors (to current version):
- ** Tim King, Morgan Deters, Mathias Preiner
- ** This file is part of the CVC4 project.
- ** Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
- ** in the top-level source directory and their institutional affiliations.
- ** All rights reserved. See the file COPYING in the top-level source
- ** directory for licensing information.\endverbatim
- **
- ** \brief This is an implementation of the Simplex Module for the Simplex for
- ** DPLL(T) decision procedure.
- **
- ** This implements the Simplex module for the Simpelx for DPLL(T) decision
- ** procedure.
- ** See the Simplex for DPLL(T) technical report for more background.(citation?)
- ** This shares with the theory a Tableau, and a PartialModel that:
- ** - satisfies the equalities in the Tableau, and
- ** - the assignment for the non-basic variables satisfies their bounds.
- ** This is required to either produce a conflict or satisifying PartialModel.
- ** Further, we require being told when a basic variable updates its value.
- **
- ** During the Simplex search we maintain a queue of variables.
- ** The queue is required to contain all of the basic variables that voilate
- ** their bounds.
- ** As elimination from the queue is more efficient to be done lazily,
- ** we do not maintain that the queue of variables needs to be only basic
- ** variables or only variables that satisfy their bounds.
- **
- ** The simplex procedure roughly follows Alberto's thesis. (citation?)
- ** There is one round of selecting using a heuristic pivoting rule.
- ** (See PreferenceFunction Documentation for the available options.)
- ** The non-basic variable is the one that appears in the fewest pivots.
- ** (Bruno says that Leonardo invented this first.)
- ** After this, Bland's pivot rule is invoked.
- **
- ** During this proccess, we periodically inspect the queue of variables to
- ** 1) remove now extraneous extries,
- ** 2) detect conflicts that are "waiting" on the queue but may not be detected
- ** by the current queue heuristics, and
- ** 3) detect multiple conflicts.
- **
- ** Conflicts are greedily slackened to use the weakest bounds that still
- ** produce the conflict.
- **
- ** Extra things tracked atm: (Subject to change at Tim's whims)
- ** - A superset of all of the newly pivoted variables.
- ** - A queue of additional conflicts that were discovered by Simplex.
- ** These are theory valid and are currently turned into lemmas
- **/
+/******************************************************************************
+ * Top contributors (to current version):
+ * Tim King, Morgan Deters, Mathias Preiner
+ *
+ * This file is part of the cvc5 project.
+ *
+ * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
+ * in the top-level source directory and their institutional affiliations.
+ * All rights reserved. See the file COPYING in the top-level source
+ * directory for licensing information.
+ * ****************************************************************************
+ *
+ * This is an implementation of the Simplex Module for the Simplex for
+ * DPLL(T) decision procedure.
+ *
+ * This implements the Simplex module for the Simpelx for DPLL(T) decision
+ * procedure.
+ * See the Simplex for DPLL(T) technical report for more background.(citation?)
+ * This shares with the theory a Tableau, and a PartialModel that:
+ * - satisfies the equalities in the Tableau, and
+ * - the assignment for the non-basic variables satisfies their bounds.
+ * This is required to either produce a conflict or satisifying PartialModel.
+ * Further, we require being told when a basic variable updates its value.
+ *
+ * During the Simplex search we maintain a queue of variables.
+ * The queue is required to contain all of the basic variables that voilate
+ * their bounds.
+ * As elimination from the queue is more efficient to be done lazily,
+ * we do not maintain that the queue of variables needs to be only basic
+ * variables or only variables that satisfy their bounds.
+ *
+ * The simplex procedure roughly follows Alberto's thesis. (citation?)
+ * There is one round of selecting using a heuristic pivoting rule.
+ * (See PreferenceFunction Documentation for the available options.)
+ * The non-basic variable is the one that appears in the fewest pivots.
+ * (Bruno says that Leonardo invented this first.)
+ * After this, Bland's pivot rule is invoked.
+ *
+ * During this proccess, we periodically inspect the queue of variables to
+ * 1) remove now extraneous extries,
+ * 2) detect conflicts that are "waiting" on the queue but may not be detected
+ * by the current queue heuristics, and
+ * 3) detect multiple conflicts.
+ *
+ * Conflicts are greedily slackened to use the weakest bounds that still
+ * produce the conflict.
+ *
+ * Extra things tracked atm: (Subject to change at Tim's whims)
+ * - A superset of all of the newly pivoted variables.
+ * - A queue of additional conflicts that were discovered by Simplex.
+ * These are theory valid and are currently turned into lemmas
+ */
#include "cvc4_private.h"
generated by cgit on debian on lair
contact matthew@masot.net with questions or feedback