Burglar - Formulating logical constraints

// (c) 2024-2025 Fair Isaac Corporation
#include <xpress.hpp>
#include <stdexcept>  // For throwing exceptions

using namespace xpress;
using namespace xpress::objects;
using xpress::objects::utils::scalarProduct;

/*
 * Knapsack problem. This example shows how to setup a simple knapsack type
 * problem in which an item selection should be made maximally profitable under
 * some weight restriction. We first solve a pure knapsack problem. Then, we
 * add more constraints by explicitly forbidding certain item combinations,
 * thereby showing multiple ways how to create indicator constraints.
*/

std::vector<double> values = { 15, 100, 90, 60, 40, 15, 10, 1 };
std::vector<double> weights = { 2, 20, 20, 30, 40, 30, 60, 10 };
std::vector<std::string> names = { "camera", "necklace", "vase", "picture", "tv", "video", "chest", "brick" };
int MAX_WEIGHT = 102;

int main() {
    try {
        // Create a problem instance with verbose messages printed to Console
        XpressProblem prob;
        prob.callbacks.addMessageCallback(XpressProblem::console);

        // Binary variables, 1 if we put item i in the knapsack, 0 if not
        std::vector<Variable> x = prob.addVariables(static_cast<int>(values.size()))
            .withType(ColumnType::Binary)
            .withName([&](int i) { return names[i]; })
            .toArray();

        // Weight restriction on the knapsack
        prob.addConstraint(scalarProduct(x, weights) <= double(MAX_WEIGHT));

        // Objective: Maximze total value
        prob.setObjective(scalarProduct(x, values), xpress::ObjSense::Maximize);

        // Optimize
        // prob.writeProb("BinBurglar.lp");
        prob.optimize();

        // Check the solution status
        if (prob.attributes.getSolStatus() != xpress::SolStatus::Optimal ) {
            std::ostringstream oss; oss << prob.attributes.getSolStatus(); // Convert xpress::SolStatus to String
            throw std::runtime_error("Problem not solved to optimality: " + oss.str());
        }

        // Print out the solution
        std::cout << std::endl << "*** Solution ***" << std::endl;
        std::cout << "Objective: " << prob.attributes.getObjVal() << std::endl;
        std::vector<double> sol = prob.getSolution();
        for (Variable v : x) std::cout << v.getName() << " = " << v.getValue(sol) << std::endl;
        std::cout << std::endl;


        /*
        * Now to show some additionaly functionaly, we add constraints to consider the items
        * "vase" and "picture" as one pair and the items "tv" and "video" as a second pair so
        * that the pairs are always taken together
        */
        // Create a map (using for_each and lambda function) to facilitate easy look up of the variables by name
        std::map<std::string, Variable> nameToVariableMap;
        std::for_each(x.begin(), x.end(), [&](Variable var) {
            nameToVariableMap[var.getName()] = var;
        });

        // Add constraint x["vase"] == x["picture"]
        prob.addConstraint(nameToVariableMap["vase"] == nameToVariableMap["picture"]);
        // Add constraint x["tv"] == x["video"]
        prob.addConstraint(nameToVariableMap["tv"] == nameToVariableMap["video"]);

        /*
        * Logical constraint: Take exactly one of the two pairs of variables (i.e. take either the
        * first pair "vase" and "picture" or the second pair "tv" and "video", but not both pairs)
        */
        // x["vase"]=1 -> x["tv"]+x["video"]=0 */
        Variable vase = nameToVariableMap["vase"];
        Expression tvPlusVideo = nameToVariableMap["tv"] + nameToVariableMap["video"];
        prob.addConstraint(vase.ifThen(tvPlusVideo <= 0.0));

        // x["vase"]=0 -> x["tv"]+x["video"]=2
        // Instead of `vase.ifNotThen()`, we can use this alternative way to create the implication constraint
        Inequality enablePairTwo = prob.addConstraint(tvPlusVideo >= 2.0);
        prob.setIndicator(vase, false, enablePairTwo);

        // By inspecting the problem, we can see the two methods of adding implication constraints
        // indeed yield similar constraint
        prob.writeProb("BinBurglar.lp");

        // Optimize again
        prob.optimize();

        // Check the solution status again
        if (prob.attributes.getSolStatus() != xpress::SolStatus::Optimal ) {
            std::ostringstream oss; oss << prob.attributes.getSolStatus(); // Convert xpress::SolStatus to String
            throw std::runtime_error("Problem not solved to optimality: " + oss.str());
        }

        // Print out the new solution
        std::cout << std::endl << "*** Solution ***" << std::endl;
        std::cout << "Objective: " << prob.attributes.getObjVal() << std::endl;
        sol = prob.getSolution();
        for (Variable v : x) std::cout << v.getName() << " = " << v.getValue(sol) << std::endl;
        std::cout << std::endl;
        return 0;
    }
    catch (std::exception& e) {
        std::cout << "Exception: " << e.what() << std::endl;
        return -1;
    }
}