A DepthFirst Branching Algorithm

/***********************************************************************
   Xpress Optimizer Examples
   =========================

   file depthfirst.c
   `````````````````
   A DepthFirst Branching Algorithm.
   Demonstrate the Xpress-MP node callbacks.

   (c) 2017 Fair Isaac Corporation       
***********************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include "xprs.h"


FILE* logFile;

typedef struct {
    int *mStack;
    int iSize;
    int iCurrentNode;
} nodeStack;


void deleteFromStack(XPRSprob prob, nodeStack *stack)
{
    int iNode;
    XPRSgetintattrib(prob, XPRS_NODES, &iNode);

    fprintf(logFile, "%d == %d\n", iNode, (*stack).mStack[(*stack).iSize-1]);
    if( (*stack).mStack[(*stack).iSize-1] == iNode )
	(*stack).iSize--;
}

void XPRS_CC nodeSelection(XPRSprob prob, void *vstack, int *iNode)
{
    nodeStack *stack = (nodeStack*) vstack;

    XPRSgetintattrib(prob, XPRS_NODES, iNode);
    fprintf(logFile, "iNode %d --------------------- pop\n", *iNode);
    if( (*stack).mStack[(*stack).iSize-1] != *iNode )
	*iNode = (*stack).mStack[--(*stack).iSize];

    fprintf(logFile,"--- Push Node From stack --- Next Node to Branch on is %d ---\n", *iNode);
}

void XPRS_CC nodeInfeasible(XPRSprob prob, void *stack)
{
    deleteFromStack(prob,stack);
    fprintf(logFile, "--- Infeasible : Delete Node ---\n");
}

void XPRS_CC nodeIntegerFeasible(XPRSprob prob, void *stack)
{
    deleteFromStack(prob,stack);
    fprintf(logFile,"--- Integer Feasible : Delete Node ---\n");
}

void XPRS_CC nodeCutOff(XPRSprob prob, void* stack, int iNode) {
    deleteFromStack(prob,stack);
    fprintf(logFile, "--- Cut Off : Delete Node ---\n");
}

void XPRS_CC nodeOptimal(XPRSprob prob, void *vstack, int* iFeasible) {
    int i;  /**/
    int iNode;
    nodeStack *stack = (nodeStack*) vstack;
    XPRSgetintattrib(prob, XPRS_NODES, &iNode);
    if( !iNode) iNode++;

    /* push on top of the stack */
    (*stack).mStack[((*stack).iSize)++] = iNode;
    (*stack).iCurrentNode = iNode;
    fprintf(logFile,"--- Node Optimal : Push Node %d ---\nStack", iNode); /**/
    for( i=0; i<(*stack).iSize; i++ ) fprintf(logFile, "%d, ",  (*stack).mStack[i]); /**/
    fprintf(logFile,"\n"); /**/
}

int XPRS_CC nodeStats(XPRSprob prob, void *vstack) {
    static int iNode = 0;
    nodeStack *stack = (nodeStack*) vstack;
    fprintf(logFile, "### This was node: %d ### The Stack has Size %d ###\n", ++iNode, (*stack).iSize);
    return 0;
}



int main( int argc, char *argv[] )
{

    XPRSprob prob;

    nodeStack stack;
    int nColumns;
    int nResult;

    logFile = fopen("dfb.log","w+");

    XPRSinit(NULL);
    XPRScreateprob(&prob);

    nResult = XPRSreadprob(prob, argv[1], "");
    if(nResult != 0 && nResult != 32) {
      printf("Unable to use problem name from commandline : '%s'\n",argv[1]);
      return(0);
    }
    printf("Start solving problem '%s'. Output to log file 'dfb.log'.\n",argv[1]);
    XPRSminim(prob, "");

    XPRSgetintattrib(prob, XPRS_COLS, &nColumns);
    XPRSsetintcontrol(prob, XPRS_MIPLOG, 3);
    XPRSsetintcontrol(prob, XPRS_CUTSTRATEGY, 0);
    XPRSsetintcontrol(prob, XPRS_NODESELECTION, 2);

    /* setup node stack */
    stack.mStack = (int*) malloc(sizeof(int)*nColumns);
    stack.iSize = 0;

    XPRSsetcbchgnode(prob, nodeSelection, &stack);
    XPRSsetcbinfnode(prob, nodeInfeasible, &stack);
    XPRSsetcbintsol(prob, nodeIntegerFeasible, &stack);
    XPRSsetcbnodecutoff(prob, nodeCutOff, &stack);
    XPRSsetcboptnode(prob, nodeOptimal, &stack);
    XPRSsetcbgloballog(prob, nodeStats, &stack);

    XPRSglobal(prob);

    free(stack.mStack);

    XPRSfree();
    printf("Solving complete.\n");
    fclose(logFile);
    return 0;
}