| line |
true |
false |
branch |
|
64
|
5 |
0 |
SolverImpl() : m_objective( new Row() ), m_id_tick( 1 ) {}
|
|
|
5 |
0 |
SolverImpl() : m_objective( new Row() ), m_id_tick( 1 ) {}
|
|
|
5 |
0 |
SolverImpl() : m_objective( new Row() ), m_id_tick( 1 ) {}
|
|
|
5 |
0 |
SolverImpl() : m_objective( new Row() ), m_id_tick( 1 ) {}
|
|
|
5 |
0 |
SolverImpl() : m_objective( new Row() ), m_id_tick( 1 ) {}
|
|
|
5 |
0 |
SolverImpl() : m_objective( new Row() ), m_id_tick( 1 ) {}
|
|
85
|
3216 |
0 |
if( m_cns.find( constraint ) != m_cns.end() )
|
|
|
0 |
3216 |
if( m_cns.find( constraint ) != m_cns.end() )
|
|
86
|
0 |
0 |
throw DuplicateConstraint( constraint );
|
|
95
|
3216 |
0 |
std::unique_ptr<Row> rowptr( createRow( constraint, tag ) );
|
|
96
|
3216 |
0 |
Symbol subject( chooseSubject( *rowptr, tag ) );
|
|
104
|
415 |
2801 |
if( subject.type() == Symbol::Invalid && allDummies( *rowptr ) )
|
|
|
415 |
0 |
if( subject.type() == Symbol::Invalid && allDummies( *rowptr ) )
|
|
|
0 |
415 |
if( subject.type() == Symbol::Invalid && allDummies( *rowptr ) )
|
|
|
0 |
3216 |
if( subject.type() == Symbol::Invalid && allDummies( *rowptr ) )
|
|
106
|
0 |
0 |
if( !nearZero( rowptr->constant() ) )
|
|
107
|
0 |
0 |
throw UnsatisfiableConstraint( constraint );
|
|
115
|
415 |
2801 |
if( subject.type() == Symbol::Invalid )
|
|
117
|
415 |
0 |
if( !addWithArtificialVariable( *rowptr ) )
|
|
|
0 |
415 |
if( !addWithArtificialVariable( *rowptr ) )
|
|
118
|
0 |
0 |
throw UnsatisfiableConstraint( constraint );
|
|
122
|
2801 |
0 |
rowptr->solveFor( subject );
|
|
123
|
2801 |
0 |
substitute( subject, *rowptr );
|
|
124
|
2801 |
0 |
m_rows[ subject ] = rowptr.release();
|
|
127
|
3216 |
0 |
m_cns[ constraint ] = tag;
|
|
132
|
3216 |
0 |
optimize( *m_objective );
|
|
145
|
0 |
0 |
auto cn_it = m_cns.find( constraint );
|
|
146
|
0 |
0 |
if( cn_it == m_cns.end() )
|
|
147
|
0 |
0 |
throw UnknownConstraint( constraint );
|
|
150
|
0 |
0 |
m_cns.erase( cn_it );
|
|
155
|
0 |
0 |
removeConstraintEffects( constraint, tag );
|
|
159
|
0 |
0 |
auto row_it = m_rows.find( tag.marker );
|
|
160
|
0 |
0 |
if( row_it != m_rows.end() )
|
|
163
|
0 |
0 |
m_rows.erase( row_it );
|
|
167
|
0 |
0 |
row_it = getMarkerLeavingRow( tag.marker );
|
|
168
|
0 |
0 |
if( row_it == m_rows.end() )
|
|
169
|
0 |
0 |
throw InternalSolverError( "failed to find leaving row" );
|
|
172
|
0 |
0 |
m_rows.erase( row_it );
|
|
173
|
0 |
0 |
rowptr->solveFor( leaving, tag.marker );
|
|
174
|
0 |
0 |
substitute( tag.marker, *rowptr );
|
|
180
|
0 |
0 |
optimize( *m_objective );
|
|
188
|
0 |
0 |
return m_cns.find( constraint ) != m_cns.end();
|
|
207
|
719 |
0 |
if( m_edits.find( variable ) != m_edits.end() )
|
|
|
0 |
719 |
if( m_edits.find( variable ) != m_edits.end() )
|
|
208
|
0 |
0 |
throw DuplicateEditVariable( variable );
|
|
210
|
0 |
719 |
if( strength == strength::required )
|
|
212
|
719 |
0 |
Constraint cn( Expression( variable ), OP_EQ, strength );
|
|
|
719 |
0 |
Constraint cn( Expression( variable ), OP_EQ, strength );
|
|
|
719 |
0 |
Constraint cn( Expression( variable ), OP_EQ, strength );
|
|
213
|
719 |
0 |
addConstraint( cn );
|
|
214
|
719 |
0 |
EditInfo info;
|
|
215
|
719 |
0 |
info.tag = m_cns[ cn ];
|
|
216
|
719 |
0 |
info.constraint = cn;
|
|
218
|
719 |
0 |
m_edits[ variable ] = info;
|
|
|
719 |
0 |
m_edits[ variable ] = info;
|
|
231
|
0 |
0 |
auto it = m_edits.find( variable );
|
|
232
|
0 |
0 |
if( it == m_edits.end() )
|
|
233
|
0 |
0 |
throw UnknownEditVariable( variable );
|
|
234
|
0 |
0 |
removeConstraint( it->second.constraint );
|
|
235
|
0 |
0 |
m_edits.erase( it );
|
|
243
|
0 |
0 |
return m_edits.find( variable ) != m_edits.end();
|
|
259
|
619 |
0 |
auto it = m_edits.find( variable );
|
|
260
|
0 |
619 |
if( it == m_edits.end() )
|
|
261
|
0 |
0 |
throw UnknownEditVariable( variable );
|
|
269
|
619 |
0 |
auto row_it = m_rows.find( info.tag.marker );
|
|
270
|
3 |
616 |
if( row_it != m_rows.end() )
|
|
272
|
2 |
1 |
if( row_it->second->add( -delta ) < 0.0 )
|
|
273
|
2 |
0 |
m_infeasible_rows.push_back( row_it->first );
|
|
278
|
616 |
0 |
row_it = m_rows.find( info.tag.other );
|
|
279
|
0 |
616 |
if( row_it != m_rows.end() )
|
|
281
|
0 |
0 |
if( row_it->second->add( delta ) < 0.0 )
|
|
282
|
0 |
0 |
m_infeasible_rows.push_back( row_it->first );
|
|
287
|
277222 |
616 |
for (const auto & rowPair : m_rows)
|
|
|
616 |
3 |
for (const auto & rowPair : m_rows)
|
|
289
|
277222 |
0 |
double coeff = rowPair.second->coefficientFor( info.tag.marker );
|
|
290
|
3 |
1826 |
if( coeff != 0.0 &&
|
|
|
3 |
277219 |
if( coeff != 0.0 &&
|
|
291
|
1829 |
275393 |
rowPair.second->add( delta * coeff ) < 0.0 &&
|
|
|
3 |
0 |
rowPair.second->add( delta * coeff ) < 0.0 &&
|
|
293
|
3 |
0 |
m_infeasible_rows.push_back( rowPair.first );
|
|
304
|
3710 |
8 |
for (auto &varPair : m_vars)
|
|
307
|
3710 |
0 |
auto row_it = m_rows.find( varPair.second );
|
|
308
|
0 |
3710 |
if( row_it == row_end )
|
|
309
|
0 |
0 |
var.setValue( 0.0 );
|
|
311
|
3710 |
0 |
var.setValue( row_it->second->constant() );
|
|
331
|
0 |
0 |
m_objective.reset( new Row() );
|
|
345
|
3216 |
0 |
void operator()( T& pair ) { delete pair.second; }
|
|
350
|
5 |
0 |
std::for_each( m_rows.begin(), m_rows.end(), RowDeleter() );
|
|
361
|
6121 |
0 |
auto it = m_vars.find( variable );
|
|
362
|
3638 |
2483 |
if( it != m_vars.end() )
|
|
365
|
2483 |
0 |
m_vars[ variable ] = symbol;
|
|
389
|
3216 |
0 |
std::unique_ptr<Row> row( new Row( expr.constant() ) );
|
|
|
3216 |
0 |
std::unique_ptr<Row> row( new Row( expr.constant() ) );
|
|
392
|
6121 |
3216 |
for (const auto &term : expr.terms())
|
|
394
|
6121 |
0 |
if( !nearZero( term.coefficient() ) )
|
|
396
|
6121 |
0 |
Symbol symbol( getVarSymbol( term.variable() ) );
|
|
397
|
6121 |
0 |
auto row_it = m_rows.find( symbol );
|
|
398
|
2639 |
3482 |
if( row_it != m_rows.end() )
|
|
399
|
2639 |
0 |
row->insert( *row_it->second, term.coefficient() );
|
|
401
|
3482 |
0 |
row->insert( symbol, term.coefficient() );
|
|
406
|
3216 |
0 |
switch( constraint.op() )
|
|
411
|
759 |
0 |
double coeff = constraint.op() == OP_LE ? 1.0 : -1.0;
|
|
|
382 |
377 |
double coeff = constraint.op() == OP_LE ? 1.0 : -1.0;
|
|
414
|
759 |
0 |
row->insert( slack, coeff );
|
|
415
|
759 |
0 |
if( constraint.strength() < strength::required )
|
|
|
0 |
759 |
if( constraint.strength() < strength::required )
|
|
419
|
0 |
0 |
row->insert( error, -coeff );
|
|
420
|
0 |
0 |
m_objective->insert( error, constraint.strength() );
|
|
|
0 |
0 |
m_objective->insert( error, constraint.strength() );
|
|
426
|
2457 |
0 |
if( constraint.strength() < strength::required )
|
|
|
720 |
1737 |
if( constraint.strength() < strength::required )
|
|
432
|
720 |
0 |
row->insert( errplus, -1.0 ); // v = eplus - eminus
|
|
433
|
720 |
0 |
row->insert( errminus, 1.0 ); // v - eplus + eminus = 0
|
|
434
|
720 |
0 |
m_objective->insert( errplus, constraint.strength() );
|
|
|
720 |
0 |
m_objective->insert( errplus, constraint.strength() );
|
|
435
|
720 |
0 |
m_objective->insert( errminus, constraint.strength() );
|
|
|
720 |
0 |
m_objective->insert( errminus, constraint.strength() );
|
|
441
|
1737 |
0 |
row->insert( dummy );
|
|
448
|
578 |
2638 |
if( row->constant() < 0.0 )
|
|
449
|
578 |
0 |
row->reverseSign();
|
|
470
|
24420 |
733 |
for (const auto &cellPair : row.cells())
|
|
472
|
2483 |
21937 |
if( cellPair.first.type() == Symbol::External )
|
|
475
|
232 |
501 |
if( tag.marker.type() == Symbol::Slack || tag.marker.type() == Symbol::Error )
|
|
|
7 |
225 |
if( tag.marker.type() == Symbol::Slack || tag.marker.type() == Symbol::Error )
|
|
|
508 |
225 |
if( tag.marker.type() == Symbol::Slack || tag.marker.type() == Symbol::Error )
|
|
477
|
316 |
192 |
if( row.coefficientFor( tag.marker ) < 0.0 )
|
|
480
|
417 |
0 |
if( tag.other.type() == Symbol::Slack || tag.other.type() == Symbol::Error )
|
|
|
2 |
415 |
if( tag.other.type() == Symbol::Slack || tag.other.type() == Symbol::Error )
|
|
|
2 |
415 |
if( tag.other.type() == Symbol::Slack || tag.other.type() == Symbol::Error )
|
|
482
|
2 |
0 |
if( row.coefficientFor( tag.other ) < 0.0 )
|
|
497
|
415 |
0 |
m_rows[ art ] = new Row( row );
|
|
|
415 |
0 |
m_rows[ art ] = new Row( row );
|
|
|
415 |
0 |
m_rows[ art ] = new Row( row );
|
|
498
|
415 |
0 |
m_artificial.reset( new Row( row ) );
|
|
|
415 |
0 |
m_artificial.reset( new Row( row ) );
|
|
502
|
415 |
0 |
optimize( *m_artificial );
|
|
508
|
415 |
0 |
auto it = m_rows.find( art );
|
|
509
|
0 |
415 |
if( it != m_rows.end() )
|
|
512
|
0 |
0 |
m_rows.erase( it );
|
|
513
|
0 |
0 |
if( rowptr->cells().empty() )
|
|
515
|
0 |
0 |
Symbol entering( anyPivotableSymbol( *rowptr ) );
|
|
516
|
0 |
0 |
if( entering.type() == Symbol::Invalid )
|
|
518
|
0 |
0 |
rowptr->solveFor( art, entering );
|
|
519
|
0 |
0 |
substitute( entering, *rowptr );
|
|
520
|
0 |
0 |
m_rows[ entering ] = rowptr.release();
|
|
|
0 |
0 |
m_rows[ entering ] = rowptr.release();
|
|
524
|
171839 |
415 |
for (auto &rowPair : m_rows)
|
|
525
|
171839 |
0 |
rowPair.second->remove(art);
|
|
527
|
415 |
0 |
m_objective->remove( art );
|
|
539
|
3064421 |
10753 |
for( auto& rowPair : m_rows )
|
|
541
|
3064421 |
0 |
rowPair.second->substitute( symbol, row );
|
|
542
|
2 |
3064419 |
if( rowPair.first.type() != Symbol::External &&
|
|
544
|
2 |
0 |
m_infeasible_rows.push_back( rowPair.first );
|
|
547
|
2937 |
7816 |
if( m_artificial.get() )
|
|
566
|
11577 |
0 |
Symbol entering( getEnteringSymbol( objective ) );
|
|
567
|
3631 |
7946 |
if( entering.type() == Symbol::Invalid )
|
|
569
|
7946 |
0 |
auto it = getLeavingRow( entering );
|
|
570
|
0 |
7946 |
if( it == m_rows.end() )
|
|
571
|
0 |
0 |
throw InternalSolverError( "The objective is unbounded." );
|
|
575
|
7946 |
0 |
m_rows.erase( it );
|
|
576
|
7946 |
0 |
row->solveFor( leaving, entering );
|
|
577
|
7946 |
0 |
substitute( entering, *row );
|
|
578
|
7946 |
0 |
m_rows[ entering ] = row;
|
|
597
|
7 |
619 |
while( !m_infeasible_rows.empty() )
|
|
602
|
7 |
0 |
auto it = m_rows.find( leaving );
|
|
603
|
7 |
0 |
if( it != m_rows.end() && !nearZero( it->second->constant() ) &&
|
|
|
7 |
0 |
if( it != m_rows.end() && !nearZero( it->second->constant() ) &&
|
|
|
6 |
1 |
if( it != m_rows.end() && !nearZero( it->second->constant() ) &&
|
|
606
|
6 |
0 |
Symbol entering( getDualEnteringSymbol( *it->second ) );
|
|
607
|
0 |
6 |
if( entering.type() == Symbol::Invalid )
|
|
608
|
0 |
0 |
throw InternalSolverError( "Dual optimize failed." );
|
|
611
|
6 |
0 |
m_rows.erase( it );
|
|
612
|
6 |
0 |
row->solveFor( leaving, entering );
|
|
613
|
6 |
0 |
substitute( entering, *row );
|
|
614
|
6 |
0 |
m_rows[ entering ] = row;
|
|
629
|
1602470 |
3631 |
for (const auto &cellPair : objective.cells())
|
|
631
|
1336961 |
265509 |
if( cellPair.first.type() != Symbol::Dummy && cellPair.second < 0.0 )
|
|
|
7946 |
1329015 |
if( cellPair.first.type() != Symbol::Dummy && cellPair.second < 0.0 )
|
|
|
7946 |
1594524 |
if( cellPair.first.type() != Symbol::Dummy && cellPair.second < 0.0 )
|
|
650
|
2681 |
6 |
for (const auto &cellPair : row.cells())
|
|
652
|
1166 |
1515 |
if( cellPair.second > 0.0 && cellPair.first.type() != Symbol::Dummy )
|
|
|
589 |
577 |
if( cellPair.second > 0.0 && cellPair.first.type() != Symbol::Dummy )
|
|
|
589 |
2092 |
if( cellPair.second > 0.0 && cellPair.first.type() != Symbol::Dummy )
|
|
654
|
589 |
0 |
double coeff = m_objective->coefficientFor( cellPair.first );
|
|
656
|
6 |
583 |
if( r < ratio )
|
|
673
|
0 |
0 |
for (const auto &cellPair : row.cells())
|
|
676
|
0 |
0 |
if( sym.type() == Symbol::Slack || sym.type() == Symbol::Error )
|
|
|
0 |
0 |
if( sym.type() == Symbol::Slack || sym.type() == Symbol::Error )
|
|
|
0 |
0 |
if( sym.type() == Symbol::Slack || sym.type() == Symbol::Error )
|
|
695
|
1781143 |
7946 |
for( auto it = m_rows.begin(); it != end; ++it )
|
|
697
|
674527 |
1106616 |
if( it->first.type() != Symbol::External )
|
|
699
|
674527 |
0 |
double temp = it->second->coefficientFor( entering );
|
|
700
|
183815 |
490712 |
if( temp < 0.0 )
|
|
703
|
131700 |
52115 |
if( temp_ratio < ratio )
|
|
742
|
0 |
0 |
for( auto it = m_rows.begin(); it != end; ++it )
|
|
744
|
0 |
0 |
double c = it->second->coefficientFor( marker );
|
|
745
|
0 |
0 |
if( c == 0.0 )
|
|
747
|
0 |
0 |
if( it->first.type() == Symbol::External )
|
|
751
|
0 |
0 |
else if( c < 0.0 )
|
|
754
|
0 |
0 |
if( r < r1 )
|
|
763
|
0 |
0 |
if( r < r2 )
|
|
770
|
0 |
0 |
if( first != end )
|
|
772
|
0 |
0 |
if( second != end )
|
|
782
|
0 |
0 |
if( tag.marker.type() == Symbol::Error )
|
|
784
|
0 |
0 |
if( tag.other.type() == Symbol::Error )
|
|
793
|
0 |
0 |
auto row_it = m_rows.find( marker );
|
|
794
|
0 |
0 |
if( row_it != m_rows.end() )
|
|
795
|
0 |
0 |
m_objective->insert( *row_it->second, -strength );
|
|
797
|
0 |
0 |
m_objective->insert( marker, -strength );
|
|
805
|
478 |
0 |
for (const auto &rowPair : row.cells())
|
|
807
|
415 |
63 |
if( rowPair.first.type() != Symbol::Dummy )
|