Previous bonus - Next bonus

Packet 5: Bonus 18

The integer variant of a problem described by this adjective reduces to the standard version when the constraint matrix is unimodular. For 10 points each:
[10e] Name this adjective that describes optimization problems solved using Dantzig’s simplex algorithm. This type of “programming” maximizes an affine objective function subject to first-degree polynomial constraints.
ANSWER: linear [accept linear programming or linear optimization]
[10m] This integer programming problem maximizes the sum of v-i (“V-eye”) times x-i, where the weighted sum of the x-i is below a total weight. When each x-i term must be binary, this problem can be solved with dynamic programming.
ANSWER: knapsack problem [accept zero–one knapsack problem]
[10h] A standard integer programming approach combines this method with constraints called cutting planes. This optimization method splits a problem into simpler subproblems and discards ones that cannot contain the optimum.
ANSWER: branch and bound [accept BB or B&B or BnB] (The integer programming technique is called branch and cut.)
<Editors, Other Science> | E. Prelims 5 - Indiana + Vanderbilt + MIT

HeardPPBE %M %H %
1611.8863%56%0%

Back to bonuses

Conversion

TeamOpponentPart 1Part 2Part 3TotalParts
BrownStanford B1010020EM
BruinNorthwestern A1010020EM
Chicago BStanford A1010020EM
GeorgetownChicago A0000
Johns HopkinsUC Berkeley B100010E
Maryland AWaterloo100010E
MichiganIllinois B100010E
MinnesotaToronto A0000
Ohio StateGeorgia Tech A0000
Penn StatePurdue1010020EM
PittsburghColumbia B010010M
TexasHarvard010010M
Toronto BGeorgia Tech C1010020EM
UC Berkeley AUCF1010020EM
UCLAVirginia Tech010010M
VirginiaColumbia A100010E

Summary

TournamentEditionMatchHeardPPBE %M %H %
Main Site2026-04-17✓1611.8863%56%0%