bisection_solver.h File Reference

Binary search for the smallest, or largest, feasible value of ONE variable. More...

#include <chrono>
#include <cmath>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "line/opt/problem.h"
#include "line/util/error.h"

Include dependency graph for bisection_solver.h:

Go to the source code of this file.

Classes
class	line::opt::BisectionSolver

Namespaces
namespace	line
namespace	line::opt

Detailed Description

Binary search for the smallest, or largest, feasible value of ONE variable.

Where the feasible set is an interval in a single integer variable – "how few servers meet this response-time target" – a population search is the wrong tool: feasibility is monotone in the variable, so bisection finds the boundary in log(range) solves. direction is min_feasible or max_feasible.

It REFUSES anything else: the problem must have exactly one dimension-1 variable whose bounds are integral, and it throws rather than falling back to a general search, because a silent fallback would hide that the monotonicity assumption does not hold. Probes are cached by value, so a repeated midpoint costs nothing.

Formatting note: written compactly, one member per line, unlike the rest of the tree.

Definition in file bisection_solver.h.