Linear Program

• LP/AAP_lp.cpp::initialize_solver_interface():
  This method returns an instance of an OsiSolverInterface. This is an interface to the LP solver that will be used to solve the linear programming relaxations. The decision for which LP solver to use is done at compile time (see the section on Build Process and Execution).

• LP/AAP_lp.cpp::compute_lower_bound():
  In this method, we generate a valid lower bound on the master LP. In order to do this, we need to solve the column generation subproblem $z_{SP}(\hat u, \hat \alpha )$. The subproblem is an instance of the Assignment Problem (AP). In the helper function generate_vars(), we calculate the reduced costs and construct an instance of AP. In addition, we use a bigM-method with the information contained in AAP_user_data to enforce the bounds determined by branching. We then solve the subproblem by calling solve_assignment_problem(), which constructs the AP as an LP using OSI. Then, any variables generated with negative reduced cost are saved as an AAP_var for use in the next method generate_vars_in_lp().

• LP/AAP_lp.cpp::generate_vars_in_lp()
  In this method, we look for variables with negative reduced cost to add into the master LP. The work has already been done in compute_lower_bound().

• LP/AAP_lp.cpp::restore_feasibility()
  This method is invoked before fathoming a search tree node if the LP has been found infeasible and no new variables were generated. Upon finding the LP infeasible, BCP attempts to produce a set of certificates, or dual rays. These are sent as arguments to restore_feasibility(), which we then use in generate_vars() in an attempt to find variables that restore feasibility.

• LP/AAP_lp.cpp::vars_to_cols()
  This method takes a variable (an assignment point) and expands it into a column in the LP. The assignment point is stored as a vector of $(i,j,k)$ indices in an AAP_var. From this, we construct a BCP_col.

Another method that a user typically needs to derive is test_feasibility. In our case, however, the default implementation, which checks for integrality is sufficient.