I’m writing a program in C# using Unity to find the optimal solution to a linear programming problem using the simplex method, for my computer science coursework. Unfortunately I’m not very experienced with C# or Unity, and I’ve run into an issue with one section of my code.
Here’s a short breakdown of linear programming for some context: (I’m only coding for one-stage linear programming with two variables) You have an objective function which you’re trying to maximise e.g. P = 3x + 2y There are also a number of limiting constraints on the problem e.g. 2x + y <= 18 or 3x + y <= 24 The most common method used to solve a problem like this is the simplex method, where all the values are stored in a table and then operated on until the optimal solutions for x and y are found (this website explains it a lot better: https://www.phpsimplex.com/en/simplex_method_example.htm#google_vignette).
In my project, the code to carry out the simplex method gets executed over a number of Unity scenes. In the first scene, the number of constraints on the problem is obtained from the user and the values in each constraint itself are stored to a matrix class 2D float array called simplexTable. The dimensions and elements of simplexTable are stored using the Player Prefs class so they can be accessed from the next scene. In the next scene, the user enters the objective function on the problem and the x and y coefficients are stored to simplexTable. Then, they click on a ‘next’ button which takes them to the next scene. In this scene, I call the method which actually carries out the simplex method and this scene is where my issue is.
Using Debug.Log statements, I’ve managed to verify that the method is called and the data in simplexMethod is successfully retrieved from Player Prefs and restored into the simplexTable array - everything works as it should up to here.
After this, I use a while loop, since I only want to continue applying the simplex method while the table is unmaximised (i.e. while an optimal solution has not been found) but whenever the code reaches this part, my Unity Editor app just freezes and I have to force quit it. I’ve done some research on this problem and apparently it can happen when your code has an infinite loop, but I’ve included a break statement which should be logically sound, and the values I’m entering while testing the program should give a solution which allows the loop to be broken out of. It could be because my laptop is quite old and only has 4GB of RAM, but I’m not sure.
I’ve pasted the part of my code that includes the while loop below.
So sorry for the bad explanation but I would really appreciate it if someone could help. Thank you so much in advance!
My Code:
bool maximised = false;//while the table is unmaximised
while (!maximised)
{
Debug.Log("while loop started");
int count = 0;
float[] pivotValueArr = new float[numberOfConstraints + 4];
float[] pivotColumn = new float[numberOfConstraints];
float pivotValueCol;
//iterates through each element in the objective row to check for negative values
for (int ii = 0; ii < simplexTable.GetColumns(); ii++)
{
if (ii < simplexTable.GetColumns())
{
Debug.Log($"ii: {ii}, Rows: {simplexTable.GetRows()}, Columns: {simplexTable.GetColumns()}");
if (simplexTable[0, ii] < 0)//IndexOutOfRangeException: Index was outside the bounds of the array
{
pivotValueArr[ii] = simplexTable[0, ii];
count++;
}
else
{
pivotValueArr[ii] = 0;
}
}
else
{
Debug.LogError($"Index out of bounds: ii={ii}, Columns={simplexTable.GetColumns()}");
}
}
Debug.Log($"Loop execution: count = {count}, maximised = {maximised}");
if (count == 0)
{
//maximised = true;
Debug.Log("break actually gets called");
break;
}
pivotValueCol = pivotValueArr.Min();
int pivotValueIndex = Array.IndexOf(pivotValueArr, pivotValueArr.Min());
for (int i = 0; i < numberOfConstraints; i++)
{
pivotColumn[i] = simplexTable[i, pivotValueIndex];
}
float[] ratioTestArr = new float[numberOfConstraints];
ratioTestArr[0] = 0;
for (int i = 1; i < pivotColumn.Length; i++)
{
if (simplexTable[i, pivotValueIndex] > 0)
{
ratioTestArr[i] = simplexTable[i, numberOfConstraints + 3] / simplexTable[i, pivotValueIndex];
}
}
int pivotRow = Array.IndexOf(ratioTestArr, ratioTestArr.Min());
float pivotCell = simplexTable[pivotRow, pivotValueIndex];
for (int i = 0; i < numberOfConstraints; i++)
{
if (i == pivotRow)
{
for (int j = 0; j <= numberOfConstraints + 3; j++)
{
simplexTable[i, j] = simplexTable[i, j] / pivotCell;
}
}
else
{
simplexTable[i, pivotValueIndex] = 0;
for (int j = 0; j <= numberOfConstraints + 3; j++)
{
if (j != pivotValueIndex)
{
simplexTable[i, j] = simplexTable[i, j] - simplexTable[i, j] * (simplexTable[pivotRow, j] / pivotCell);
}
}
}
}
}
I’ve tried adding Debug.Log statements to identify the error, shutting down all my other apps in case they were taking up too much memory, and checking for logic errors which would cause the loop to execute infinitely.
As mentioned Unity is single threaded - meaning most of the Unity API can only be used on the Unity main thread.
If you have a long processing code like your loop might be then it will block any further execution until it is done.
So in general in order to allow the UI main thread to continue while you are waiting for a result you want to either only process as much as you can within one frame and continue in the next or move the entire execution to asynchronous code - meaning it is handled on a separate thread.
If it freezes completely for a wast amount of time - you most probably have an infinite loop there.
There are a couple of things you could check first. For instance
if (ii < simplexTable.GetColumns())
when should this ever not be the case? Your for loop iterates over ii = 0 up until ii = simplexTable.GetColumns() - 1 so this check is pretty redundant. For the rest you have to ensure yourself that your iteration algorithm terminates at some point. If it doesn't Debug your code and find out why.
Also as a sidenote that continuous creation of new arrays will cause a lot of GC (Garbage Collector) work and you should try to reduce that to a minimum reusing arrays.
Anyway here are a couple of ways for either splitting up the work over multiple UI frames (Coroutines) or moving the entire execution async.
These are kind of temporary Update methods and not really asynchronous. They just allow you to spread a "method run over multiple frames". This is a very Unity specific pattern and not encouraged by everyone ;)
For example you could try and use a target frame-rate like
private void YourMethod()
{
StartCoroutine(YourRoutine());
}
private IEnumerator YourRoutine()
{
...
var sw = new StopWatch();
var targetMs = Mathf.FloorToInt(1000f / FRAMES_PER_SECOND);
sw.Start();
while(!maxed)
{
if(sw.ElapsedMilliseconds >= targetMs)
{
// This basically means, "pause" this routine, render this frame
// and continue from here in the next frame
yield return null;
sw.Restart();
}
...
}
// Handle result
}
In general it is probably better though to rather directly go for asynchronous programming and use a proper Thread or async Task.
Which of these is better again depends on your use-case - I think in yours I would recommend a Task or even use UniTask which provides some advanced Unity integrations and more lightweight async implementation
Alternatively more advanced stuff like Compute Shaders or Unity's JobSystem + Burst could even boost the processing so much that maybe you don't even need to wait for too long