solver.dart 26.3 KB
Newer Older
1
// Copyright 2016 The Chromium Authors. All rights reserved.
2 3 4
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5 6 7 8 9 10 11 12 13 14 15 16
import 'dart:collection';

import 'constraint.dart';
import 'expression.dart';
import 'priority.dart';
import 'result.dart';
import 'param.dart';
import 'term.dart';

enum _SymbolType { invalid, external, slack, error, dummy, }

class _Symbol {
17
  const _Symbol(this.type);
18

19
  final _SymbolType type;
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
}

class _Tag {
  _Tag(this.marker, this.other);
  _Tag.fromTag(_Tag tag)
      : this.marker = tag.marker,
        this.other = tag.other;
  _Symbol marker;
  _Symbol other;
}

class _EditInfo {
  _Tag tag;
  Constraint constraint;
  double constant;
}

bool _isValidNonRequiredPriority(double priority) {
  return (priority >= 0.0 && priority < Priority.required);
}

typedef Result _SolverBulkUpdate(dynamic item);

bool _nearZero(double value) {
  const double epsilon = 1.0e-8;
  return value < 0.0 ? -value < epsilon : value < epsilon;
}

class _Row {
  _Row(this.constant) : this.cells = new Map<_Symbol, double>();

  _Row.fromRow(_Row row)
      : this.cells = new Map<_Symbol, double>.from(row.cells),
        this.constant = row.constant;

  final Map<_Symbol, double> cells;

  double constant = 0.0;

  double add(double value) => constant += value;

  void insertSymbol(_Symbol symbol, [double coefficient = 1.0]) {
    double val = cells[symbol] ?? 0.0;

    if (_nearZero(val + coefficient)) {
      cells.remove(symbol);
    } else {
      cells[symbol] = val + coefficient;
    }
  }

  void insertRow(_Row other, [double coefficient = 1.0]) {
    constant += other.constant * coefficient;
    other.cells.forEach((_Symbol s, double v) => insertSymbol(s, v * coefficient));
  }

  void removeSymbol(_Symbol symbol) {
    cells.remove(symbol);
  }

  void reverseSign() {
    constant = -constant;
    cells.forEach((_Symbol s, double v) => cells[s] = -v);
  }

  void solveForSymbol(_Symbol symbol) {
    assert(cells.containsKey(symbol));
    double coefficient = -1.0 / cells[symbol];
    cells.remove(symbol);
    constant *= coefficient;
    cells.forEach((_Symbol s, double v) => cells[s] = v * coefficient);
  }

  void solveForSymbols(_Symbol lhs, _Symbol rhs) {
    insertSymbol(lhs, -1.0);
    solveForSymbol(rhs);
  }

  double coefficientForSymbol(_Symbol symbol) => cells[symbol] ?? 0.0;

  void substitute(_Symbol symbol, _Row row) {
    double coefficient = cells[symbol];

    if (coefficient == null) {
      return;
    }

    cells.remove(symbol);
    insertRow(row, coefficient);
  }

  @override
  String toString() {
    StringBuffer buffer = new StringBuffer();

    buffer.write(constant);

    cells.forEach((_Symbol symbol, double value) {
      buffer.write(" + " + value.toString() + " * " + symbol.toString());
    });

    return buffer.toString();
  }
}
124

125 126 127 128
/// Solves cassowary constraints.
///
/// Typically clients will create a solver, [addConstraints], and then call
/// [flushUpdates] to actually solve the constraints.
129
class Solver {
130 131 132 133 134 135
  final Map<Constraint, _Tag> _constraints = new Map<Constraint, _Tag>();
  final Map<_Symbol, _Row> _rows = new Map<_Symbol, _Row>();
  final Map<Variable, _Symbol> _vars = new Map<Variable, _Symbol>();
  final Map<Variable, _EditInfo> _edits = new Map<Variable, _EditInfo>();
  final List<_Symbol> _infeasibleRows = new List<_Symbol>();
  final _Row _objective = new _Row(0.0);
136

137
  _Row _artificial = new _Row(0.0);
138

139 140 141
  /// Attempts to add the constraints in the list to the solver. If it cannot
  /// add any for some reason, a cleanup is attempted so that either all
  /// constraints will be added or none.
142 143 144 145 146 147 148 149 150 151 152 153 154 155
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: All constraints successfully added.
  /// * [Result.duplicateConstraint]: One of the constraints in the list was
  ///   already in the solver or the same constraint was specified multiple
  ///   times in the argument list. Remove the duplicates and try again.
  /// * [Result.unsatisfiableConstraint]: One or more constraints were at
  ///   [Priority.required] but could not added because of conflicts with other
  ///   constraints at the same priority. Lower the priority of these
  ///   constraints and try again.
156
  Result addConstraints(List<Constraint> constraints) {
157 158
    _SolverBulkUpdate applier = (Constraint c) => addConstraint(c);
    _SolverBulkUpdate undoer = (Constraint c) => removeConstraint(c);
159

160
    return _bulkEdit(constraints, applier, undoer);
161 162
  }

163 164 165 166 167 168 169 170 171 172 173 174 175 176
  /// Attempts to add an individual [Constraint] to the solver.
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The constraint was successfully added.
  /// * [Result.duplicateConstraint]: The constraint was already present in the
  ///   solver.
  /// * [Result.unsatisfiableConstraint]: The constraint was at
  ///   [Priority.required] but could not be added because of a conflict with
  ///   another constraint at that priority already in the solver. Try lowering
  ///   the priority of the constraint and try again.
177
  Result addConstraint(Constraint constraint) {
178
    if (_constraints.containsKey(constraint))
179 180
      return Result.duplicateConstraint;

181 182
    _Tag tag = new _Tag(new _Symbol(_SymbolType.invalid),
                        new _Symbol(_SymbolType.invalid));
183

184
    _Row row = _createRow(constraint, tag);
185

186
    _Symbol subject = _chooseSubjectForRow(row, tag);
187

188
    if (subject.type == _SymbolType.invalid && _allDummiesInRow(row)) {
189 190 191 192 193 194 195
      if (!_nearZero(row.constant)) {
        return Result.unsatisfiableConstraint;
      } else {
        subject = tag.marker;
      }
    }

196
    if (subject.type == _SymbolType.invalid) {
197
      if (!_addWithArtificialVariableOnRow(row))
198 199 200 201 202 203 204 205 206
        return Result.unsatisfiableConstraint;
    } else {
      row.solveForSymbol(subject);
      _substitute(subject, row);
      _rows[subject] = row;
    }

    _constraints[constraint] = tag;

207
    return _optimizeObjectiveRow(_objective);
208 209
  }

210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
  /// Attempts to remove a list of constraints from the solver. Either all
  /// constraints are removed or none. If more fine-grained control over the
  /// removal is required (for example, not failing on removal of constraints
  /// not already present in the solver), try removing the each [Constraint]
  /// individually and check the result on each attempt.
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The constraints were successfully removed from the
  ///   solver.
  /// * [Result.unknownConstraint]: One or more constraints in the list were
  ///   not in the solver. So there was nothing to remove.
225 226 227 228 229 230 231
  Result removeConstraints(List<Constraint> constraints) {
    _SolverBulkUpdate applier = (Constraint c) => removeConstraint(c);
    _SolverBulkUpdate undoer = (Constraint c) => addConstraint(c);

    return _bulkEdit(constraints, applier, undoer);
  }

232 233 234 235 236 237 238 239 240 241 242
  /// Attempt to remove an individual [Constraint] from the solver.
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The [Constraint] was successfully removed from the
  ///   solver.
  /// * [Result.unknownConstraint]: The [Constraint] was not in the solver so
  ///   there was nothing to remove.
243
  Result removeConstraint(Constraint constraint) {
244
    _Tag tag = _constraints[constraint];
245
    if (tag == null)
246 247
      return Result.unknownConstraint;

248
    tag = new _Tag.fromTag(tag);
249 250 251 252
    _constraints.remove(constraint);

    _removeConstraintEffects(constraint, tag);

253
    _Row row = _rows[tag.marker];
254 255 256
    if (row != null) {
      _rows.remove(tag.marker);
    } else {
257 258
      _Symbol leaving = _leavingSymbolForMarkerSymbol(tag.marker);
      assert(leaving != null);
259

260 261
      row = _rows.remove(leaving);
      assert(row != null);
262 263 264 265 266
      row.solveForSymbols(leaving, tag.marker);
      _substitute(tag.marker, row);
    }

    return _optimizeObjectiveRow(_objective);
267 268
  }

269
  /// Returns whether the given [Constraint] is present in the solver.
270 271
  bool hasConstraint(Constraint constraint) {
    return _constraints.containsKey(constraint);
272 273
  }

274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294
  /// Adds a list of edit [Variable]s to the [Solver] at a given priority.
  /// Either all edit [Variable] are added or none. No edit variables may be
  /// added at `Priority.required`.
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The edit variables were successfully added to [Solver]
  ///   at the specified priority.
  /// * [Result.duplicateEditVariable]: One of more edit variables were already
  ///   present in the [Solver] or the same edit variables were specified
  ///   multiple times in the list. Remove the duplicates and try again.
  /// * [Result.badRequiredStrength]: The edit variables were added at
  ///   [Priority.required]. Edit variables are used to
  ///   suggest values to the solver. Since suggestions can't be mandatory,
  ///   priorities cannot be [Priority.required]. If variable values need to be
  ///   fixed at [Priority.required], add that preference as a constraint. This
  ///   allows the solver to check for satisfiability of the constraint (w.r.t
  ///   other constraints at [Priority.required]) and check for duplicates.
295 296 297 298 299 300 301
  Result addEditVariables(List<Variable> variables, double priority) {
    _SolverBulkUpdate applier = (Variable v) => addEditVariable(v, priority);
    _SolverBulkUpdate undoer = (Variable v) => removeEditVariable(v);

    return _bulkEdit(variables, applier, undoer);
  }

302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321
  /// Attempt to add a single edit [Variable] to the [Solver] at the given
  /// priority. No edit variables may be added to the [Solver] at
  /// `Priority.required`.
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The edit variable was successfully added to [Solver]
  ///   at the specified priority.
  /// * [Result.duplicateEditVariable]: The edit variable was already present
  ///   in the [Solver].
  /// * [Result.badRequiredStrength]: The edit variable was added at
  ///   [Priority.required]. Edit variables are used to
  ///   suggest values to the solver. Since suggestions can't be mandatory,
  ///   priorities cannot be [Priority.required]. If variable values need to be
  ///   fixed at [Priority.required], add that preference as a constraint. This
  ///   allows the solver to check for satisfiability of the constraint (w.r.t
  ///   other constraints at [Priority.required]) and check for duplicates.
322
  Result addEditVariable(Variable variable, double priority) {
323
    if (_edits.containsKey(variable))
324 325
      return Result.duplicateEditVariable;

326
    if (!_isValidNonRequiredPriority(priority))
327 328 329
      return Result.badRequiredStrength;

    Constraint constraint = new Constraint(
330
      new Expression(<Term>[new Term(variable, 1.0)], 0.0),
331 332
      Relation.equalTo
    );
333
    constraint.priority = priority;
334

335
    assert(addConstraint(constraint) == Result.success);
336

337
    _EditInfo info = new _EditInfo();
338 339 340 341 342 343 344
    info.tag = _constraints[constraint];
    info.constraint = constraint;
    info.constant = 0.0;

    _edits[variable] = info;

    return Result.success;
345 346
  }

347 348 349 350 351 352 353 354 355 356 357 358
  /// Attempt the remove the list of edit [Variable] from the solver. Either
  /// all the specified edit variables are removed or none.
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The edit variables were successfully removed from the
  ///   [Solver].
  /// * [Result.unknownEditVariable]: One of more edit variables were not
  ///   already present in the solver.
359 360 361 362 363 364 365 366
  Result removeEditVariables(List<Variable> variables) {
    _SolverBulkUpdate applier = (Variable v) => removeEditVariable(v);
    _SolverBulkUpdate undoer = (Variable v) =>
        addEditVariable(v, _edits[v].constraint.priority);

    return _bulkEdit(variables, applier, undoer);
  }

367 368 369 370 371 372 373 374 375 376 377
  /// Attempt to remove the specified edit [Variable] from the solver.
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The edit variable was successfully removed from the
  ///   solver.
  /// * [Result.unknownEditVariable]: The edit variable was not present in the
  ///   solver. There was nothing to remove.
378
  Result removeEditVariable(Variable variable) {
379
    _EditInfo info = _edits[variable];
380
    if (info == null)
381 382
      return Result.unknownEditVariable;

383
    assert(removeConstraint(info.constraint) == Result.success);
384 385 386

    _edits.remove(variable);
    return Result.success;
387 388
  }

389
  /// Returns whether the given edit [Variable] is present in the solver.
390 391
  bool hasEditVariable(Variable variable) {
    return _edits.containsKey(variable);
392 393
  }

394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416
  /// Suggest an updated value for the edit variable. The edit variable
  /// must already be added to the solver.
  ///
  /// Suggestions update values of variables within the [Solver] but take into
  /// account all the constraints already present in the [Solver]. Depending
  /// on the constraints, the value of the [Variable] may not actually be the
  /// value specified. The actual value can be read after the next
  /// `flushUpdates` call. Since these updates are merely "suggestions", they
  /// cannot be at `Priority.required`.
  ///
  ///
  /// Check the [Result] returned to make sure the operation succeeded. Any
  /// errors will be reported via the `message` property on the [Result].
  ///
  /// Possible [Result]s:
  ///
  /// * [Result.success]: The suggestion was successfully applied to the
  ///   variable within the solver.
  /// * [Result.unknownEditVariable]: The edit variable was not already present
  ///   in the [Solver]. So the suggestion could not be applied. Add this edit
  ///   variable to the solver and then apply the value again. If you have
  ///   already added the variable to the [Solver], make sure the [Result]
  ///   was `Result.success`.
417
  Result suggestValueForVariable(Variable variable, double value) {
418
    if (!_edits.containsKey(variable))
419 420 421 422 423
      return Result.unknownEditVariable;

    _suggestValueForEditInfoWithoutDualOptimization(_edits[variable], value);

    return _dualOptimize();
424 425
  }

426 427 428 429 430 431 432 433 434 435
  /// Flush the results of solver. The set of all `context` objects associated
  /// with variables in the [Solver] is returned. If a [Variable] does not
  /// contain an associated context, its updates are ignored.
  ///
  /// The addition and removal of constraints and edit variables to and from the
  /// [Solver] as well as the application of suggestions to the added edit
  /// variables leads to the modification of values on a lot of other variables.
  /// External entities that rely on the values of the variables within the
  /// [Solver] can read these updates in one shot by "flushing" out these
  /// updates.
436 437
  Set<dynamic> flushUpdates() {
    Set<dynamic> updates = new HashSet<dynamic>();
438

439
    for (Variable variable in _vars.keys) {
440 441
      _Symbol symbol = _vars[variable];
      _Row row = _rows[symbol];
442 443 444

      double updatedValue = row == null ? 0.0 : row.constant;

445 446
      if (variable.applyUpdate(updatedValue) && variable.owner != null) {
        dynamic context = variable.owner.context;
447
        if (context != null)
448
          updates.add(context);
449 450
      }
    }
451

452
    return updates;
453
  }
454

455 456 457 458 459 460
  Result _bulkEdit(
    Iterable<dynamic> items,
    _SolverBulkUpdate applier,
    _SolverBulkUpdate undoer
  ) {
    List<dynamic> applied = <dynamic>[];
461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
    bool needsCleanup = false;

    Result result = Result.success;

    for (dynamic item in items) {
      result = applier(item);
      if (result == Result.success) {
        applied.add(item);
      } else {
        needsCleanup = true;
        break;
      }
    }

    if (needsCleanup) {
476
      for (dynamic item in applied.reversed)
477 478 479 480 481 482
        undoer(item);
    }

    return result;
  }

483
  _Symbol _symbolForVariable(Variable variable) {
484
    _Symbol symbol = _vars[variable];
485

486
    if (symbol != null)
487 488
      return symbol;

489
    symbol = new _Symbol(_SymbolType.external);
490 491 492 493 494
    _vars[variable] = symbol;

    return symbol;
  }

495
  _Row _createRow(Constraint constraint, _Tag tag) {
496
    Expression expr = new Expression.fromExpression(constraint.expression);
497
    _Row row = new _Row(expr.constant);
498

499
    expr.terms.forEach((Term term) {
500
      if (!_nearZero(term.coefficient)) {
501
        _Symbol symbol = _symbolForVariable(term.variable);
502

503
        _Row foundRow = _rows[symbol];
504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519

        if (foundRow != null) {
          row.insertRow(foundRow, term.coefficient);
        } else {
          row.insertSymbol(symbol, term.coefficient);
        }
      }
    });

    switch (constraint.relation) {
      case Relation.lessThanOrEqualTo:
      case Relation.greaterThanOrEqualTo:
        {
          double coefficient =
              constraint.relation == Relation.lessThanOrEqualTo ? 1.0 : -1.0;

520
          _Symbol slack = new _Symbol(_SymbolType.slack);
521 522 523
          tag.marker = slack;
          row.insertSymbol(slack, coefficient);

524
          if (constraint.priority < Priority.required) {
525
            _Symbol error = new _Symbol(_SymbolType.error);
526 527 528 529 530 531 532
            tag.other = error;
            row.insertSymbol(error, -coefficient);
            _objective.insertSymbol(error, constraint.priority);
          }
        }
        break;
      case Relation.equalTo:
533
        if (constraint.priority < Priority.required) {
534 535
          _Symbol errPlus = new _Symbol(_SymbolType.error);
          _Symbol errMinus = new _Symbol(_SymbolType.error);
536 537 538 539 540 541 542
          tag.marker = errPlus;
          tag.other = errMinus;
          row.insertSymbol(errPlus, -1.0);
          row.insertSymbol(errMinus, 1.0);
          _objective.insertSymbol(errPlus, constraint.priority);
          _objective.insertSymbol(errMinus, constraint.priority);
        } else {
543
          _Symbol dummy = new _Symbol(_SymbolType.dummy);
544 545 546 547 548 549 550 551 552 553 554 555 556
          tag.marker = dummy;
          row.insertSymbol(dummy);
        }
        break;
    }

    if (row.constant < 0.0) {
      row.reverseSign();
    }

    return row;
  }

557 558
  _Symbol _chooseSubjectForRow(_Row row, _Tag tag) {
    for (_Symbol symbol in row.cells.keys) {
559
      if (symbol.type == _SymbolType.external)
560 561 562
        return symbol;
    }

563 564
    if (tag.marker.type == _SymbolType.slack ||
        tag.marker.type == _SymbolType.error) {
565
      if (row.coefficientForSymbol(tag.marker) < 0.0)
566 567 568
        return tag.marker;
    }

569 570
    if (tag.other.type == _SymbolType.slack ||
        tag.other.type == _SymbolType.error) {
571
      if (row.coefficientForSymbol(tag.other) < 0.0)
572 573 574
        return tag.other;
    }

575
    return new _Symbol(_SymbolType.invalid);
576 577
  }

578 579
  bool _allDummiesInRow(_Row row) {
    for (_Symbol symbol in row.cells.keys) {
580
      if (symbol.type != _SymbolType.dummy)
581 582 583 584 585
        return false;
    }
    return true;
  }

586
  bool _addWithArtificialVariableOnRow(_Row row) {
587
    _Symbol artificial = new _Symbol(_SymbolType.slack);
588 589
    _rows[artificial] = new _Row.fromRow(row);
    _artificial = new _Row.fromRow(row);
590 591 592 593 594 595 596 597 598

    Result result = _optimizeObjectiveRow(_artificial);

    if (result.error) {
      // FIXME(csg): Propagate this up!
      return false;
    }

    bool success = _nearZero(_artificial.constant);
599
    _artificial = new _Row(0.0);
600

601
    _Row foundRow = _rows[artificial];
602 603
    if (foundRow != null) {
      _rows.remove(artificial);
604
      if (foundRow.cells.isEmpty)
605 606
        return success;

607
      _Symbol entering = _anyPivotableSymbol(foundRow);
608
      if (entering.type == _SymbolType.invalid)
609 610 611 612 613 614 615
        return false;

      foundRow.solveForSymbols(artificial, entering);
      _substitute(entering, foundRow);
      _rows[entering] = foundRow;
    }

616
    for (_Row row in _rows.values)
617 618 619 620 621
      row.removeSymbol(artificial);
    _objective.removeSymbol(artificial);
    return success;
  }

622
  Result _optimizeObjectiveRow(_Row objective) {
623
    while (true) {
624
      _Symbol entering = _enteringSymbolForObjectiveRow(objective);
625
      if (entering.type == _SymbolType.invalid)
626 627
        return Result.success;

628 629
      _Symbol leaving = _leavingSymbolForEnteringSymbol(entering);
      assert(leaving != null);
630

631
      _Row row = _rows.remove(leaving);
632 633 634 635 636 637
      row.solveForSymbols(leaving, entering);
      _substitute(entering, row);
      _rows[entering] = row;
    }
  }

638
  _Symbol _enteringSymbolForObjectiveRow(_Row objective) {
639
    Map<_Symbol, double> cells = objective.cells;
640

641
    for (_Symbol symbol in cells.keys) {
642
      if (symbol.type != _SymbolType.dummy && cells[symbol] < 0.0)
643 644 645
        return symbol;
    }

646
    return new _Symbol(_SymbolType.invalid);
647 648
  }

649
  _Symbol _leavingSymbolForEnteringSymbol(_Symbol entering) {
650
    double ratio = double.MAX_FINITE;
651
    _Symbol result;
652
    _rows.forEach((_Symbol symbol, _Row row) {
653
      if (symbol.type != _SymbolType.external) {
654 655
        double temp = row.coefficientForSymbol(entering);
        if (temp < 0.0) {
Hixie's avatar
Hixie committed
656 657 658
          double tempRatio = -row.constant / temp;
          if (tempRatio < ratio) {
            ratio = tempRatio;
659
            result = symbol;
660 661 662 663 664 665 666
          }
        }
      }
    });
    return result;
  }

667
  void _substitute(_Symbol symbol, _Row row) {
668
    _rows.forEach((_Symbol first, _Row second) {
669
      second.substitute(symbol, row);
670
      if (first.type != _SymbolType.external && second.constant < 0.0) {
671 672 673 674
        _infeasibleRows.add(first);
      }
    });
    _objective.substitute(symbol, row);
675
    if (_artificial != null)
676 677 678
      _artificial.substitute(symbol, row);
  }

679 680
  _Symbol _anyPivotableSymbol(_Row row) {
    for (_Symbol symbol in row.cells.keys) {
681 682
      if (symbol.type == _SymbolType.slack ||
          symbol.type == _SymbolType.error) {
683 684 685
        return symbol;
      }
    }
686
    return new _Symbol(_SymbolType.invalid);
687
  }
688

689
  void _removeConstraintEffects(Constraint cn, _Tag tag) {
690
    if (tag.marker.type == _SymbolType.error) {
691 692
      _removeMarkerEffects(tag.marker, cn.priority);
    }
693
    if (tag.other.type == _SymbolType.error) {
694 695 696 697
      _removeMarkerEffects(tag.other, cn.priority);
    }
  }

698 699
  void _removeMarkerEffects(_Symbol marker, double strength) {
    _Row row = _rows[marker];
700 701 702 703 704 705 706
    if (row != null) {
      _objective.insertRow(row, -strength);
    } else {
      _objective.insertSymbol(marker, -strength);
    }
  }

707
  _Symbol _leavingSymbolForMarkerSymbol(_Symbol marker) {
708 709 710
    double r1 = double.MAX_FINITE;
    double r2 = double.MAX_FINITE;

711
    _Symbol first, second, third;
712

713
    _rows.forEach((_Symbol symbol, _Row row) {
714
      double c = row.coefficientForSymbol(marker);
715
      if (c == 0.0)
716
        return;
717
      if (symbol.type == _SymbolType.external) {
718
        third = symbol;
719 720 721 722
      } else if (c < 0.0) {
        double r = -row.constant / c;
        if (r < r1) {
          r1 = r;
723
          first = symbol;
724 725 726 727 728
        }
      } else {
        double r = row.constant / c;
        if (r < r2) {
          r2 = r;
729
          second = symbol;
730 731 732 733
        }
      }
    });

734
    return first ?? second ?? third;
735
  }
736 737

  void _suggestValueForEditInfoWithoutDualOptimization(
738
      _EditInfo info, double value) {
739 740 741 742
    double delta = value - info.constant;
    info.constant = value;

    {
743 744
      _Symbol symbol = info.tag.marker;
      _Row row = _rows[info.tag.marker];
745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763

      if (row != null) {
        if (row.add(-delta) < 0.0) {
          _infeasibleRows.add(symbol);
        }
        return;
      }

      symbol = info.tag.other;
      row = _rows[info.tag.other];

      if (row != null) {
        if (row.add(delta) < 0.0) {
          _infeasibleRows.add(symbol);
        }
        return;
      }
    }

764 765
    for (_Symbol symbol in _rows.keys) {
      _Row row = _rows[symbol];
766 767 768
      double coeff = row.coefficientForSymbol(info.tag.marker);
      if (coeff != 0.0 &&
          row.add(delta * coeff) < 0.0 &&
769
          symbol.type != _SymbolType.external) {
770 771 772 773 774 775 776
        _infeasibleRows.add(symbol);
      }
    }
  }

  Result _dualOptimize() {
    while (_infeasibleRows.length != 0) {
777 778
      _Symbol leaving = _infeasibleRows.removeLast();
      _Row row = _rows[leaving];
779 780

      if (row != null && row.constant < 0.0) {
781
        _Symbol entering = _dualEnteringSymbolForRow(row);
782

783
        assert(entering.type != _SymbolType.invalid);
784 785 786 787 788 789 790 791 792 793 794

        _rows.remove(leaving);

        row.solveForSymbols(leaving, entering);
        _substitute(entering, row);
        _rows[entering] = row;
      }
    }
    return Result.success;
  }

795
  _Symbol _dualEnteringSymbolForRow(_Row row) {
796
    _Symbol entering;
797 798 799

    double ratio = double.MAX_FINITE;

800
    Map<_Symbol, double> rowCells = row.cells;
801

802
    for (_Symbol symbol in rowCells.keys) {
803 804
      double value = rowCells[symbol];

805
      if (value > 0.0 && symbol.type != _SymbolType.dummy) {
806 807 808 809 810 811 812 813 814
        double coeff = _objective.coefficientForSymbol(symbol);
        double r = coeff / value;
        if (r < ratio) {
          ratio = r;
          entering = symbol;
        }
      }
    }

815
    return entering ?? new _Symbol(_SymbolType.invalid);
816
  }
817

818
  @override
819 820 821 822 823 824 825 826 827 828
  String toString() {
    StringBuffer buffer = new StringBuffer();
    String separator = "\n~~~~~~~~~";

    // Objective
    buffer.writeln(separator + " Objective");
    buffer.writeln(_objective.toString());

    // Tableau
    buffer.writeln(separator + " Tableau");
829 830
    _rows.forEach((_Symbol symbol, _Row row) {
      buffer.writeln('$symbol | $row');
831 832 833 834
    });

    // Infeasible
    buffer.writeln(separator + " Infeasible");
835 836 837
    _infeasibleRows.forEach((_Symbol symbol) {
      buffer.writeln(symbol);
    });
838 839 840

    // Variables
    buffer.writeln(separator + " Variables");
841 842 843
    _vars.forEach((Variable variable, _Symbol symbol) {
      buffer.writeln('$variable = $symbol');
    });
844 845 846

    // Edit Variables
    buffer.writeln(separator + " Edit Variables");
847 848 849
    _edits.forEach((Variable variable, _EditInfo editinfo) {
      buffer.writeln(variable);
    });
850 851 852

    // Constraints
    buffer.writeln(separator + " Constraints");
853 854 855
    _constraints.forEach((Constraint constraint, _Tag tag) {
      buffer.writeln(constraint);
    });
856 857 858

    return buffer.toString();
  }
859
}