Valid Inequalities

Each cut is implemented in a separate class that uses public inheritance from the Cut base class. Each cut returns a vector with CutReturn structs (see below or cut.h for the struct).

The derived cut classes separate the valid inequalities and are independent of the solver (e.g., CPLEX or Gurobi) that is used. The derived cut classes return an std::vector<CutReturn>, which the Cut base class transforms into a vector of CPLEX expressions. If you want to use another solver (say Gurobi), you only have to add a function create_gurobiConstraint.cc to the Cut base class and call this function in Cut::getCuts().

Below we discuss the following topics in more detail

1. Initializing and using cuts
2. Implementing a new cut
3. Using another solver
4. Implementation details

Initializing and using cuts

TODO: explain/discuss cut constructor

The first step is to construct the Cut objects (details on the constructor are discussed below). A single Cut object can be constructed as

Cut aCut(.. arguments here ..);

To call the separation algorithm implemented by aCut one uses

std::vector<IloRange> someCuts = aCut.getCuts(..);

To be more flexible, we decided to store all cuts into a std::vector<shared_ptr<Cut>> all_cuts. One could also choose to 1) store them as raw pointers, or 2) store them as an object directly. However, with option 1) one has to manually call the destructor which is likely to result in memory leaks. And for option 2) there is less flexibility for passing the vector around as we do not want to copy the objects (to keep the internal statistics correct).

With the vector all_cuts, we can easily loop over all cuts, call the separation algorithms, and print the results as follows:

for (auto const &cut_ptr: all_cuts)
{
  auto const cuts = cut_ptr->getCuts(model.d_env, model.d_x, x_val, true);
  
  for (auto const &cut: cuts)
  {
    std::cout << cut << std::endl;
  }
}

Implementing a new cut

TODO: copy the folder cut_example and replace "Cut_example" by the name of the new cut (three strings in Cut_example.h, one in Cut_example.ih, and two in findCuts.cc). (2) Add the header file to allCuts.h. (3) Implement the findCuts functions.

Your separation magic can be implemented in Cut::findCuts. One is free to add as many private/public data members and functions to the derived classes as he/she likes, as long as the derived class implements the virtual function Cut::findCuts. An implementation to return the cut 8 * x[1][2] + 1 * x[2][1] <= 1 could be as follows:

#include "./Cut_example.ih"

vector<CutReturn> Cut_example::findCuts(vector<vector<double>> const &x)
{
  vector<CutReturn> cuts;

  CutReturn cut;

  cut.rhs = 1;
  cut.add(8, 1, 2);
  cut.add(1, 2, 1);

  cuts.push_back(cut);

  return cuts;
}

The minimum code that a derived cut class requires is provided in the folder cuts/Cut_example.

Using another solver

If you wish to use another solver, you only have to edit the Cut base class since all derived cut classes are solver independent. As a user, one calls the Cut::getCuts function, which does nothing else (besides keeping track of some statistics) than calling the virtual private function Cut::findCuts and transforming the resulting cuts into the appropriate format such that the solver can use them.

Suppose you want to use Gurobi, then you add a private function Cut::create_gurobiConstraint and in the function Cut::getCuts you replace

vector<IloRange> cuts (createIloRange(env, variables, findCuts(x)));

by

vector<GRBLinExpr> cuts (create_gurobiConstraint(env, variables, findCuts(x)));

Implementation details

Dependencies

The separation algorithms share many functions that perform some actions on a graph. We have implemented these functions in the namespace graphFunctions which can be loaded by including the graphFunction.h header file. The header file is automatically loaded if the folders 'cuts' and 'graphFunctions' are at the same level. If the folder 'graphFunctions' is stored at another location, the file 'cuts/cut.ih' should be changed accordingly.

CutReturn struct

struct CutReturn
{
  double rhs;
  std::vector<std::array<int, 3>> coeff;

  void add(int coefficient, int i, int j)
  {
    coeff.push_back({coefficient, i, j});
  }
};