Google OR-Tools: ortools/graph/min_cost

Google OR-Tools: ortools/graph/min_cost_flow.h Source File

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168#ifndef ORTOOLS_GRAPH_MIN_COST_FLOW_H_

169#define ORTOOLS_GRAPH_MIN_COST_FLOW_H_

170

171#include <cstdint>

172#include <stack>

173#include <string>

174#include <vector>

175

176#include "absl/log/log.h"

177#include "absl/strings/string_view.h"

181

183

184

185template <typename Graph, typename ArcFlowType, typename ArcScaledCostType>

187

188

189

191 public:

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

247 };

248};

249

250

251

252

253

254

255

256

257

259 public:

264

265

266

267

268

269

270

272 ArcIndex reserve_num_arcs = 0);

273

274#ifndef SWIG

275

278#endif

279

280

281

282

283

284

285

289

290

291

292

294

295

296

297

299

300

301

302

303

305 return SolveWithPossibleAdjustment(SupplyAdjustment::DONT_ADJUST);

306 }

307

308

309

310

311

312

314 return SolveWithPossibleAdjustment(SupplyAdjustment::ADJUST);

315 }

316

317

318

320

321

322

324

325

326

327

328

329

330

332

333

334

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

361

362 private:

363 typedef ::util::ReverseArcStaticGraph<NodeIndex, ArcIndex> Graph;

364 enum SupplyAdjustment { ADJUST, DONT_ADJUST };

365

366

368

369

370 Status SolveWithPossibleAdjustment(SupplyAdjustment adjustment);

371 void ResizeNodeVectors(NodeIndex node);

372

373 std::vector<NodeIndex> arc_tail_;

374 std::vector<NodeIndex> arc_head_;

375 std::vector<FlowQuantity> arc_capacity_;

376 std::vector<FlowQuantity> node_supply_;

377 std::vector<CostValue> arc_cost_;

378 std::vector<ArcIndex> arc_permutation_;

379 std::vector<FlowQuantity> arc_flow_;

382

383 bool scale_prices_ = true;

384};

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403template <typename Graph, typename ArcFlowType = int64_t,

404 typename ArcScaledCostType = int64_t>

406 public:

414

415

416

417

419

420#ifndef SWIG

421

424#endif

425

426

428

429

430

431

433

434

435

437

438

440

441

443

444

446

447

448

449

450

451

453

454

455

457

458

459

460

461

463

464

466

467

468

470

471

472

473

474

475

476

478

479

482

483 private:

484

485

486

487

488 bool CheckFeasibility();

489

490

491

492

493 bool IsAdmissible(ArcIndex arc) const;

494 bool FastIsAdmissible(ArcIndex arc, CostValue tail_potential) const;

495

496

497 bool IsActive(NodeIndex node) const;

498

499

502

503

504 ArcIndex GetFirstOutgoingOrOppositeIncomingArc(NodeIndex node) const;

505

506

507

508 bool CheckInputConsistency();

509

510

511

512

513

514 bool CheckResult() const;

515

516

517

518

519

520 bool CheckRelabelPrecondition(NodeIndex node) const;

521

522

523

524 std::string DebugString(absl::string_view context, ArcIndex arc) const;

525

526

527

528 void ResetFirstAdmissibleArcs();

529

530

531

532 bool ScaleCosts();

533

534

535 void UnscaleCosts();

536

537

538

539 bool Optimize();

540

541

542 void SaturateAdmissibleArcs();

543

544

545

546

547

550

551

552 void InitializeActiveNodeStack();

553

554

555

556

557

558

559 bool UpdatePrices();

560

561

562

563

564 bool Refine();

565

566

567

568

570

571

572

573 bool NodeHasAdmissibleArc(NodeIndex node);

574

575

576

577

578

580

581

585 bool IsArcDirect(ArcIndex arc) const;

586 bool IsArcValid(ArcIndex arc) const;

587

588

589 const Graph* graph_;

590

591

592

593 std::unique_ptr<FlowQuantity[]> node_excess_;

594

595

596

597 std::unique_ptr<CostValue[]> node_potential_;

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618 ZVector<ArcFlowType> residual_arc_capacity_;

619

620

621 std::unique_ptr<ArcIndex[]> first_admissible_arc_;

622

623

624

625

626 std::stack<NodeIndex> active_nodes_;

627

628

630

631

632

633 const int64_t alpha_;

634

635

636 CostValue cost_scaling_factor_ = 1;

637

638

639

641

642

643 ZVector<ArcScaledCostType> scaled_arc_unit_cost_;

644

645

647

648

649

650 std::unique_ptr<FlowQuantity[]> initial_node_excess_;

651

652

653 StatsGroup stats_;

654

655

656 int num_relabels_since_last_price_update_ = 0;

657

658

659 bool feasibility_checked_ = false;

660

661

662 bool use_price_update_ = false;

663

664

665 bool check_feasibility_ = false;

666

667

668 bool scale_prices_ = true;

669};

670

671#if !SWIG

672

673

674

675

679 ::util::ReverseArcStaticGraph<uint16_t, int32_t>>;

681 ::util::ReverseArcListGraph<int64_t, int64_t>, int64_t, int64_t>;

683 ::util::ReverseArcStaticGraph<uint16_t, int32_t>,

684 int16_t,

685 int32_t>;

686

687

688

690 template <typename = void>

692 LOG(FATAL) << "MinCostFlow is deprecated. Use `SimpleMinCostFlow` or "

693 "`GenericMinCostFlow` with a specific graph type instead.";

694 }

695};

696

697#endif

698

699}

700#endif

Definition min_cost_flow.h:405

FlowQuantity Flow(ArcIndex arc) const

void SetArcUnitCost(ArcIndex arc, ArcScaledCostType unit_cost)

Graph::OutgoingOrOppositeIncomingArcIterator OutgoingOrOppositeIncomingArcIterator

Definition min_cost_flow.h:412

int64_t CostValue

Definition min_cost_flow.h:409

GenericMinCostFlow & operator=(const GenericMinCostFlow &)=delete

GenericMinCostFlow(const Graph *graph)

void SetArcCapacity(ArcIndex arc, ArcFlowType new_capacity)

GenericMinCostFlow(const GenericMinCostFlow &)=delete

void SetNodeSupply(NodeIndex node, FlowQuantity supply)

void SetUseUpdatePrices(bool value)

Definition min_cost_flow.h:480

ZVector< ArcIndex > ArcIndexArray

Definition min_cost_flow.h:413

const Graph * graph() const

Definition min_cost_flow.h:427

CostValue UnitCost(ArcIndex arc) const

FlowQuantity Supply(NodeIndex node) const

void SetCheckFeasibility(bool value)

Definition min_cost_flow.h:477

void SetPriceScaling(bool value)

Definition min_cost_flow.h:481

Graph::NodeIndex NodeIndex

Definition min_cost_flow.h:407

int64_t FlowQuantity

Definition min_cost_flow.h:410

Status status() const

Definition min_cost_flow.h:432

Graph::ArcIndex ArcIndex

Definition min_cost_flow.h:408

FlowQuantity Capacity(ArcIndex arc) const

CostValue GetOptimalCost()

Definition min_cost_flow.h:190

Status

Definition min_cost_flow.h:192

@ BAD_RESULT

Definition min_cost_flow.h:198

@ BAD_CAPACITY_RANGE

Definition min_cost_flow.h:246

@ BAD_COST_RANGE

Definition min_cost_flow.h:225

@ NOT_SOLVED

Definition min_cost_flow.h:193

@ OPTIMAL

Definition min_cost_flow.h:194

@ FEASIBLE

Definition min_cost_flow.h:195

@ UNBALANCED

Definition min_cost_flow.h:197

@ INFEASIBLE

Definition min_cost_flow.h:196

int64_t CostValue

Definition min_cost_flow.h:263

int32_t NodeIndex

Definition min_cost_flow.h:260

Status SolveMaxFlowWithMinCost()

Definition min_cost_flow.h:313

NodeIndex Tail(ArcIndex arc) const

CostValue OptimalCost() const

void SetNodeSupply(NodeIndex node, FlowQuantity supply)

void SetArcCapacity(ArcIndex arc, FlowQuantity capacity)

FlowQuantity Flow(ArcIndex arc) const

int32_t ArcIndex

Definition min_cost_flow.h:261

FlowQuantity Capacity(ArcIndex arc) const

void SetPriceScaling(bool value)

Definition min_cost_flow.h:360

CostValue UnitCost(ArcIndex arc) const

NodeIndex NumNodes() const

ArcIndex AddArcWithCapacityAndUnitCost(NodeIndex tail, NodeIndex head, FlowQuantity capacity, CostValue unit_cost)

SimpleMinCostFlow(const SimpleMinCostFlow &)=delete

FlowQuantity MaximumFlow() const

NodeIndex Head(ArcIndex arc) const

SimpleMinCostFlow(NodeIndex reserve_num_nodes=0, ArcIndex reserve_num_arcs=0)

SimpleMinCostFlow & operator=(const SimpleMinCostFlow &)=delete

FlowQuantity Supply(NodeIndex node) const

Status Solve()

Definition min_cost_flow.h:304

int64_t FlowQuantity

Definition min_cost_flow.h:262

NodeIndexType Tail(ArcIndexType arc) const

NodeIndexType Head(ArcIndexType arc) const

BlossomGraph::CostValue CostValue

BlossomGraph::NodeIndex NodeIndex

util::ReverseArcStaticGraph Graph

MinCostFlow()

Definition min_cost_flow.h:691