Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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?
There is no definitive answer and it depends on:
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:
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:
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.
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):
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;
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).
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:
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;
};
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*>)
};
}
}
}
IloNumArray and co.)
numpy / networkx quite frequently, despite the availability of high-lvl Python-based modelling-APIs (e.g. docplex)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.
