I am brand new to constraint programming and am trying to model my first problem as a constraint program using the ILOG CP Optimizer. I've installed ILOG Optimization Suite 20.1 and have successfully compiled and run many of the included example files.
What I'd like to do is schedule 5 tasks on 2 units. Each task has a release time and a due time. Moreover, on each unit, each task has a processing time and a processing cost.
The following is my code.
#include <ilcp/cp.h>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[])
{
IloEnv env;
try
{
IloModel model(env);
IloInt numUnits = 2;
IloInt numTasks = 5;
IloIntervalVarArray dummyTasks(env, numTasks);
IloInt taskReleaseTimes[] = {0, 21, 15, 37, 3};
IloInt taskDueTimes[] = {200, 190, 172, 194, 161};
IloArray<IloBoolArray> unitTaskAssignment(env, numUnits);
unitTaskAssignment[0] = IloBoolArray(env, numTasks, IloTrue, IloTrue, IloFalse, IloTrue, IloTrue);
unitTaskAssignment[1] = IloBoolArray(env, numTasks, IloTrue, IloFalse, IloTrue, IloFalse, IloTrue);
IloArray<IloIntArray> unitTaskTimes(env, numUnits);
IloArray<IloNumArray> unitTaskCosts(env, numUnits);
IloIntArray minTaskTimes(env, numTasks);
IloIntArray maxTaskTimes(env, numTasks);
IloNumExpr totalCost(env);
unitTaskTimes[0] = IloIntArray(env, numTasks, 51, 67, 0, 24, 76);
unitTaskTimes[1] = IloIntArray(env, numTasks, 32, 0, 49, 0, 102);
unitTaskCosts[0] = IloNumArray(env, numTasks, 3.1, 3.7, 0.0, 3.4, 3.6);
unitTaskCosts[1] = IloNumArray(env, numTasks, 3.2, 0.0, 3.9, 0.0, 3.2);
IloArray<IloIntervalVarArray> taskUnits(env, numTasks);
IloArray<IloIntervalVarArray> unitTasks(env, numUnits);
for(IloInt i = 0; i < numTasks; i++)
{
IloInt minTaskTime = unitTaskTimes[0][i];
IloInt maxTaskTime = unitTaskTimes[0][i];
for(IloInt j = 1; j < numUnits; j++)
{
if(unitTaskTimes[j][i] < minTaskTime) minTaskTime = unitTaskTimes[j][i];
if(unitTaskTimes[j][i] > maxTaskTime) maxTaskTime = unitTaskTimes[j][i];
}
minTaskTimes[i] = minTaskTime;
maxTaskTimes[i] = maxTaskTime;
/* cout << "Minimum task time for task " << i << ": " << minTaskTimes[i] << endl;*/
/* cout << "Maximum task time for task " << i << ": " << maxTaskTimes[i] << endl;*/
}
char name[128];
for(IloInt i = 0; i < numTasks; i++)
{
taskUnits[i] = IloIntervalVarArray(env, numUnits);
sprintf(name, "dummyTask_%ld", i);
dummyTasks[i] = IloIntervalVar(env, minTaskTimes[i], maxTaskTimes[i]);
dummyTasks[i].setStartMin(taskReleaseTimes[i]);
dummyTasks[i].setEndMax(taskDueTimes[i]);
for(IloInt j = 0; j < numUnits; j++)
{
sprintf(name, "task%ld_in_unit%ld", j, i);
taskUnits[i][j] = IloIntervalVar(env, unitTaskTimes[j][i], name);
taskUnits[i][j].setOptional();
taskUnits[i][j].setStartMin(taskReleaseTimes[i]);
taskUnits[i][j].setEndMax(taskDueTimes[i]);
if(!unitTaskAssignment[j][i]) taskUnits[i][j].setAbsent();
totalCost += unitTaskCosts[j][i]*IloPresenceOf(env, taskUnits[i][j]);
}
model.add(IloAlternative(env, dummyTasks[i], taskUnits[i]));
}
for(IloInt j = 0; j < numUnits; j++)
{
unitTasks[j] = IloIntervalVarArray(env, numTasks);
for(IloInt i = 1; i < numTasks; i++)
{
unitTasks[j][i] = taskUnits[i][j];
}
model.add(IloNoOverlap(env, unitTasks[j]));
}
model.add(IloMinimize(env, totalCost));
IloCP cp(model);
cp.setParameter(IloCP::TimeLimit, 20);
if (cp.solve())
{
cout << "There's a solution." << endl;
}
else
{
cp.out() << "No solution found. " << std::endl;
}
}
catch (IloException & ex)
{
env.out() << "Caught " << ex << std::endl;
}
env.end();
return 0;
}
Perhaps there is a better logic that could be applied, and I'm happy to take suggestions on how to better model the problem, but that really isn't the question.
The question is, if I comment out the line
model.add(IloNoOverlap(env, unitTasks[j]));
everything compiles and runs fine, but if I leave it in, the program compiles, but seg faults on execution. Why?
Here's the valgrind output if it helps:
==361075== Memcheck, a memory error detector
==361075== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==361075== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==361075== Command: ./CP_test
==361075==
! --------------------------------------------------- CP Optimizer 20.1.0.0 --
! Minimization problem - 15 variables, 5 constraints
! TimeLimit = 20
! Initial process time : 1.00s (0.99s extraction + 0.02s propagation)
! . Log search space : 18.3 (before), 18.3 (after)
! . Memory usage : 335.4 kB (before), 335.4 kB (after)
! Using parallel search with 8 workers.
! ----------------------------------------------------------------------------
! Best Branches Non-fixed W Branch decision
0 15 -
+ New bound is 17.30000
^C==361075==
==361075== Process terminating with default action of signal 2 (SIGINT)
==361075== at 0x4882A9A: futex_wait (futex-internal.h:141)
==361075== by 0x4882A9A: futex_wait_simple (futex-internal.h:172)
==361075== by 0x4882A9A: pthread_barrier_wait (pthread_barrier_wait.c:184)
==361075== by 0xCEFA06: IlcParallel::SynchronizedMaster::workerSynchronize(IlcParallel::ThreadWorker*) (in /home/nate/Dropbox/Princeton/Maravelias/DCA_Branch_and_Cut/cplex_implementation/CP_optimizer_test_instance/CP_test)
==361075== by 0x66F224: IlcParallelEngineI::SynchronizedMaster::workerSynchronize(IlcParallel::ThreadWorker*) (in /home/nate/Dropbox/Princeton/Maravelias/DCA_Branch_and_Cut/cplex_implementation/CP_optimizer_test_instance/CP_test)
==361075== by 0xCF3B60: IlcParallel::SynchronizedMaster::ThreadIO::workerWaitInput() (in /home/nate/Dropbox/Princeton/Maravelias/DCA_Branch_and_Cut/cplex_implementation/CP_optimizer_test_instance/CP_test)
==361075== by 0xCF4182: IlcParallel::ThreadWorker::startup() (in /home/nate/Dropbox/Princeton/Maravelias/DCA_Branch_and_Cut/cplex_implementation/CP_optimizer_test_instance/CP_test)
==361075== by 0xCF5929: IlcThread::CallStartup(void*) (in /home/nate/Dropbox/Princeton/Maravelias/DCA_Branch_and_Cut/cplex_implementation/CP_optimizer_test_instance/CP_test)
==361075== by 0x487A608: start_thread (pthread_create.c:477)
==361075== by 0x4D0A292: clone (clone.S:95)
==361075==
==361075== HEAP SUMMARY:
==361075== in use at exit: 1,161,688 bytes in 353 blocks
==361075== total heap usage: 942 allocs, 589 frees, 2,260,411 bytes allocated
==361075==
==361075== LEAK SUMMARY:
==361075== definitely lost: 19,728 bytes in 1 blocks
==361075== indirectly lost: 9,752 bytes in 13 blocks
==361075== possibly lost: 2,304 bytes in 8 blocks
==361075== still reachable: 1,129,904 bytes in 331 blocks
==361075== of which reachable via heuristic:
==361075== stdstring : 35 bytes in 1 blocks
==361075== suppressed: 0 bytes in 0 blocks
==361075== Rerun with --leak-check=full to see details of leaked memory
==361075==
==361075== For lists of detected and suppressed errors, rerun with: -s
==361075== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Any advice is appreciated. Please note that I attempted to post to the IBM forum, but I apparently don't have permission for some reason.
You have a segmentation fault because unitTasks[j][0] is null pointer since your array initialization loop starts at 1. Also, you should try to compile in debug mode (without -DNDEBUG) and thus you would get an assertion failure when the null handle is used.