2
$\begingroup$

Switching over from CPLEX Optimization Studio, now I want to solve problems in C++ using the CPLEX API.

Being used to the CPLEX data types, I was wondering how they best translate to C++.

For example, using string arrays in CPLEX, what's the best way to represent them in C++? A vector? pointer?

Maybe there exists some kind of guide for this?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

There is no definitive answer and it depends on:

  • your background
  • the nature / characteristic of your problem
  • the nature / characteristic of your implementation (proof of concept; deployed software)

As CPLEX' types basically behave like smart pointers you are very flexible as this works well with most well-designed libraries.

I'm one of those people dropping all those CPLEX provided containers (don't like them) and the following 3 categories of types / containers dominate all my c++-based modelling-code:

My go-to categories of types

STL Containers / Algorithms

  • Already mentioned in comments
  • Typically:
    • vector, set/map, ...
  • Also compatible ones: boost containers, google's abseil, ...

Eigen (Link)

  • "Eigen is a C++ template library for linear algebra: matrices, vectors, numerical solvers, and related algorithms."

boost::graph (Link)

  • "A generic interface for traversing graphs, using C++ templates."

Detail: STL

Most C++ programmers are very familiar with STL containers and it's a good idea to use them.

At some point, those might not be enough howewer and some alternatives might become interesting:

  • e.g. matrices (vector of vector is ugly, inefficient and usage is sub-optimal) or graphs.

Disclaimer: Eigen + boost::graph

Eigen as well as boost::graph are state of the art battle-tested libraries i highly recommend.

Both howewer have some learning-curve.

Both are header-only libs which make integration / building much easier.

Detail: Eigen

If my model has (dense) vectors, matrices or tensors, it's likely that i'm using Eigen (limited to it's containers and related functionality; it offers much more we don't need).

It basically allows everything what people also do in numpy (python):

  • row/col-indexing
  • fancy-indexing by vectors
  • ...

The docs for the parts most interesting for us: Eigen: Slicing and Indexing

Some example of row/col-based indexing typically happening in assignment-like subproblems.

using MatrixVar = Eigen::Array<IloNumVar, Eigen::Dynamic, Eigen::Dynamic>;
using MatrixSol = Eigen::Array<double, Eigen::Dynamic, Eigen::Dynamic>;

MatrixVar pos_class_mat(n_sequence, n_classes);

// create variables
for(uint64_t s=0; s<n_sequence; ++s) {
  for(uint64_t c=0; c<n_classes; ++c) {
    pos_class_mat(s, c) = IloNumVar(env, 0, 1, ILOBOOL);
  }
} 

// exactly one classes chosen at each sequence-pos
for(uint64_t s=0; s<n_sequence; ++s) {
  IloExpr expr(env);
  for(auto& var : pos_class_mat(s, Eigen::all))
    expr += var;
  this->model.add(expr == 1);
}

In modern C++ we could also do nice things like:

static auto get_sol(const MatrixVar& matrix, IloCplex& cplex) {
  auto extract = [&matrix, &cplex] (Eigen::Index i) { return cplex.getValue(matrix(i)); };
  return MatrixSol::NullaryExpr(matrix.rows(), matrix.cols(), extract);
}

This allows us to easily print it:

std::cout << get_sol(pos_class_mat, cplex) << std::endl;

Detail: boost::graph

If my model has a graph-based structure i always use boost::graph which allows some powerful stuff.

I'm then able to structure the variable- and constraint objects.

A somewhat convoluted example trying to hint why this might be a good idea -> handle complexity!.

Here the code does not use CPLEX, but SCIP, but it does not matter. The concept is the same. Only the handles for variables and constraints would be different (and i'm lazy).

Graphs-setup

We have a global-graph and many local-graphs with some implicit linking.

Think "decomposition".

The goal is to have a single model allowing to be reused for:

  • greedy-algorithms
    • solve first n parts only
    • solve first n+1 parts only but fix decision of first n parts
    • ...
  • large-neighborhood search
    • free some small ratio of decisions of some solution and resolve

just by using this structure (fixed or non-fixed variables).

// either a variable yet to be optimized or fixed (e.g. partially-fixed problem or full-fixed solution)
using MaybeContVar = std::variant<std::monostate, SCIP_VAR*, double>;
using MaybeUintVar = std::variant<std::monostate, SCIP_VAR*, uint64_t>;
using MaybeBoolVar = std::variant<std::monostate, SCIP_VAR*, bool>;

struct GlobalGraphNodeParameters {
  std::optional<uint64_t> capacity;
};

struct GlobalGraphNodeVariables {
  
};

struct GlobalGraphNodeConstraints {
  SCIP_CONS* capacity_bound_in;
  SCIP_CONS* capacity_bound_out;
};

struct GlobalGraphNode {
  GlobalGraphNodeParameters parameters;
  GlobalGraphNodeVariables variables;
  GlobalGraphNodeConstraints constraints;
};

// -----

struct GlobalGraphArcParameters {
  bool is_integral;
  boost::dynamic_bitset<> colors;
  std::optional<uint64_t> capacity;
  double cost_fixed;
  double cost_dynamic;
};

struct GlobalGraphArcVariables {
  MaybeBoolVar is_open_negated;
  MaybeContVar is_open;
};

struct GlobalGraphArcConstraints {
  SCIP_CONS* var_bool_open_neg_link;
  SCIP_CONS* capacity_bound_shared;
};

struct GlobalGraphArc {
  uint64_t id;

  GlobalGraphArcParameters parameters;
  GlobalGraphArcVariables variables;
  GlobalGraphArcConstraints constraints;
};

using GlobalGraph = boost::adjacency_list<
  boost::vecS, boost::vecS, boost::bidirectionalS,
  GlobalGraphNode,
  GlobalGraphArc>;

// --------------------

struct LocalGraphNodeParameters {
  // positive -> can send at most
  // negative -> must receive at least
  int64_t flow_imbalance_capacity;
};

struct LocalGraphNodeVariables {
};

struct LocalGraphNodeConstraints {
  SCIP_CONS* flow_conservation_generalized;
};

struct LocalGraphNode {
  bool is_valid;

  LocalGraphNodeParameters parameters;
  LocalGraphNodeVariables variables;
  LocalGraphNodeConstraints constraints;
};

// -----

struct LocalGraphArcParameters {
  double cost_dynamic;
  std::optional<uint64_t> capacity;
};

struct LocalGraphArcVariables {
  MaybeContVar flow;
};

struct LocalGraphArcConstraints {
  SCIP_CONS* openess_indicator;
};

struct LocalGraphArc {
  uint64_t id;

  LocalGraphArcParameters parameters;
  LocalGraphArcVariables variables;
  LocalGraphArcConstraints constraints;
};

// -----

struct LocalGraphAuxParameters {
  std::optional<double> penalized_unperformed_allowed;
};

struct LocalGraphAuxVariables {
  MaybeBoolVar is_unperformed;
};

struct LocalGraphAuxConstraints {
};

struct LocalGraphAux {
  LocalGraphAuxParameters parameters;
  LocalGraphAuxVariables variables;
  LocalGraphAuxConstraints constraints;
};

using LocalGraph = boost::adjacency_list<
  boost::vecS, boost::vecS, boost::bidirectionalS,
  LocalGraphNode,
  LocalGraphArc,
  LocalGraphAux>;

// Link global and local graph (decomposed parts) together

struct Model {
  GlobalGraph global_graph;
  std::vector<std::optional<LocalGraph>> local_graphs;
};

Example usage

Then we could do cool things like:

  auto es = boost::edges(lgraph);
  for(auto eit = es.first; eit != es.second; ++eit) {
    auto l_source_vertex = boost::source(*eit, lgraph); 
    
    auto edge_in_global_graph_opt = get_specific_arc_incident(problem.global_graph, l_source_vertex, lgraph[*eit].id);
    assert(edge_in_global_graph_opt.has_value());

    auto& props = lgraph[*eit];
    auto& props_in_global = problem.global_graph[edge_in_global_graph_opt.value()];

    double flow_var_capacity = props.parameters.capacity.value_or(SCIPinfinity(scip));
    double cost_dynamic = props.parameters.cost_dynamic;

    // flow
    if(std::holds_alternative<SCIP_VAR*>(props.variables.flow)) {
      // unfixed
      if(props_in_global.parameters.is_integral)
        SCIPcreateVar(scip, &std::get<SCIP_VAR*>(props.variables.flow), "flow", 0.0, flow_var_capacity, cost_dynamic, SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL);
      else
        SCIPcreateVar(scip, &std::get<SCIP_VAR*>(props.variables.flow), "flow", 0.0, flow_var_capacity, cost_dynamic, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL);
      SCIPaddVar(scip, std::get<SCIP_VAR*>(props.variables.flow));  
    }
    else if(std::holds_alternative<double>(props.variables.flow)) {
      // fixed
      double fixed_value = std::get<double>(props.variables.flow);
      props.variables.flow = MaybeContVar(std::in_place_type<SCIP_VAR*>);

      if(props_in_global.parameters.is_integral)
        SCIPcreateVar(scip, &std::get<SCIP_VAR*>(props.variables.flow), "flow", 0.0, flow_var_capacity, cost_dynamic, SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL);
      else
        SCIPcreateVar(scip, &std::get<SCIP_VAR*>(props.variables.flow), "flow", 0.0, flow_var_capacity, cost_dynamic, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL);
      SCIPaddVar(scip, std::get<SCIP_VAR*>(props.variables.flow));
      SCIP_Bool infeasible;
      SCIP_Bool fixed;
      SCIPfixVar(scip, std::get<SCIP_VAR*>(props.variables.flow), fixed_value, &infeasible, &fixed);     
    }

and also a minimal large-neighborhood search (changing fixed/sol -> unfixed/var for some parts):

void Lns::parameterize_unstructured() {
  // Lets keep it sample -> randomize each decision
  std::bernoulli_distribution p_unfix(options.lns_unfix_probability);

  // global
  {
    // GlobalGraphArcVariables
    auto es = boost::edges(working_model.global_graph);
    for (auto eit = es.first; eit != es.second; ++eit) {
      if(p_unfix(prng))
        working_model.global_graph[*eit].variables = GlobalGraphArcVariables {
          .is_open_negated = MaybeBoolVar(std::in_place_type<SCIP_VAR*>),
          .is_open = MaybeContVar(std::in_place_type<SCIP_VAR*>)
        };
    }
  }

  // local
  for(auto& lgraph_opt : working_model.local_graphs) {
    assert(lgraph_opt.has_value());

    // LocalGraphAuxVariables
    if(p_unfix(prng))
      lgraph_opt.value()[boost::graph_bundle].variables = LocalGraphAuxVariables {
        .is_unperformed = MaybeBoolVar(std::in_place_type<SCIP_VAR*>)
      };

    // LocalGraphArcVariables
    auto es = boost::edges(lgraph_opt.value());
    for (auto eit = es.first; eit != es.second; ++eit) {
      if(p_unfix(prng))
        lgraph_opt.value()[*eit].variables = LocalGraphArcVariables {
          .flow = MaybeContVar(std::in_place_type<SCIP_VAR*>)
        };
    }
  }
}

Summary / Recommendations

  • Don't be scared not to use the provided types (IloNumArray and co.)
    • If: stick to well-established alternatives (STL; maybe Eigen, boost::graph and co.)
      • Much larger community to help you out (usage is orthogonal to optimization and even non-optimization people can help)
      • You can reuse concepts easily when changing the solver
        • CPLEX, Gurobi, SCIP, CoinOR Cbc, ... It's just a different handle-type within your containers
    • Fun fact: Using python, i'm also using numpy / networkx quite frequently, despite the availability of high-lvl Python-based modelling-APIs (e.g. docplex)
  • Pick what's working for you
    • If you cannot invest the time to get ready for Eigen/boost::graph (both metaprogramming-heavy), it's probably not worth it
  • Ask yourself why you are using C++ and how you should make the best out of it
    • Some do it because of performance (e.g. compared to python; only matters for model-setup)
    • I mostly do it because of all those C++ capabilities
      • Strong type-system, metaprogramming
      • Also:
        • Availability of high-quality libraries
    • Meaning: Small POCs won't always be C++-based and for sure won't look like above graph example
      • But at some point investing into the core-design helps to limit error-finding later!
$\endgroup$
1
  • $\begingroup$ Wow, thanks for that in-depth write up! I'll check out the libraries you mentioned. $\endgroup$ Aug 28, 2023 at 7:39
1
$\begingroup$

I would suggest taking a look at the C++ source code examples that ship with CPLEX Optimization Studio. Then have a look at the documentation for the C++ API, specifically for the optim.concert group. You'll find built in support for a lot of array types.

$\endgroup$
1
  • $\begingroup$ Thank you, very good suggestion! $\endgroup$ Aug 28, 2023 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.