HiGHS
HiGHS copied to clipboard
ERGO-Code
Warm start provokes solver failure
I have an example, where a warm restarted solver fails, whereas with one warm start less, it succeeds:
$ cat warmstart-incorrect.c
#include "interfaces/highs_c_api.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
int main ()
{
{
const double col_cost[7] =
{ 0.000, 0.000, 0.000, 0.000, 0.000, 0.000, 0.000 };
const double col_lower[7] =
{ -69.000, -47.000, -91.000, -73.000, -50.000, -89.000, -94.000 };
const double col_upper[7] =
{ 74.000, 86.000, 101.000, 85.000, 61.000, 64.000, 68.000 };
const double row_lower[0] = { };
const double row_upper[0] = { };
const int a_start[1] = { 0 };
const int a_index[0] = { };
const double a_value[0] = { };
void *highs = Highs_create ();
printf ("%p = Highs_create()\n", highs);
Highs_setBoolOptionValue (highs, "output_flag", 0);
int run_status = Highs_passLp (highs,
7, 0, 0,
kHighsMatrixFormatRowwise,
kHighsObjSenseMaximize,
0, col_cost,
col_lower, col_upper, row_lower, row_upper,
a_start, a_index, a_value);
assert (run_status == kHighsStatusOk);
{
const double col_cost[7] =
{ 10.000, 0.000, 0.000, -4.000, 0.000, 0.000, 0.000 };
const double row_lower[5] =
{ -1000000000000000000000000000000.000, -126.000,
-1000000000000000000000000000000.000, 9.000, -85.000
};
const double row_upper[5] =
{ 15.000, -88.000, 7.000, 1000000000000000000000000000000.000,
-47.000
};
const HighsInt a_start[5] = { 0, 3, 7, 9, 10 };
const HighsInt a_index[13] = { 3, 5, 6, 1, 3, 4, 5, 3, 4, 1, 0, 4, 6 };
const double a_value[13] =
{ -3.000, -7.000, 6.000, -7.000, -10.000, 1.000, -6.000, -3.000,
-3.000, 8.000, 1.000, 9.000, -10.000
};
Highs_addRows (highs, 5, row_lower, row_upper, 13, a_start, a_index,
a_value);
Highs_changeColsCostByRange (highs, 0, 6, col_cost);
}
#ifdef PROVOKE_FAILURE
{
Highs_setStringOptionValue (highs, "solver", "simplex");
Highs_changeObjectiveSense (highs, kHighsObjSenseMinimize);
assert (Highs_run (highs) == kHighsStatusOk);
printf ("model_status %d, objective %.4f\n",
Highs_getModelStatus (highs), Highs_getObjectiveValue (highs));
assert (Highs_getModelStatus (highs) == kHighsModelStatusOptimal);
double col_value[7], col_dual[7];
double row_value[5], row_dual[5];
Highs_getSolution (highs, col_value, col_dual, row_value, row_dual);
}
#endif
{
const double col_cost[7] =
{ 0.000, 0.000, 0.000, 0.000, 0.000, 2.000, 0.000 };
const double row_lower[1] = { -1000000000000000000000000000000.000 };
const double row_upper[1] = { -848.688 };
const HighsInt a_start[1] = { 0 };
const HighsInt a_index[2] = { 0, 3 };
const double a_value[2] = { 10.000, -4.000 };
Highs_addRows (highs, 1,
row_lower, row_upper, 2, a_start, a_index, a_value);
Highs_changeColsCostByRange (highs, 0, 6, col_cost);
}
{
Highs_setStringOptionValue (highs, "solver", "simplex");
Highs_changeObjectiveSense (highs, kHighsObjSenseMinimize);
assert (Highs_run (highs) == kHighsStatusOk);
printf ("model_status %d, objective %.4f\n",
Highs_getModelStatus (highs), Highs_getObjectiveValue (highs));
assert (Highs_getModelStatus (highs) == kHighsModelStatusOptimal);
double col_value[7], col_dual[7];
double row_value[6], row_dual[6];
Highs_getSolution (highs, col_value, col_dual, row_value, row_dual);
}
{
const double col_cost[7] =
{ 0.000, 0.000, 0.000, 0.000, 0.000, 0.000, -7.000 };
const double row_lower[1] = { -1000000000000000000000000000000.000 };
const double row_upper[1] = { -106.866 };
const HighsInt a_start[1] = { 0 };
const HighsInt a_index[1] = { 5 };
const double a_value[1] = { 2.000 };
Highs_addRows (highs, 1,
row_lower, row_upper, 1, a_start, a_index, a_value);
Highs_changeColsCostByRange (highs, 0, 6, col_cost);
}
{
Highs_setStringOptionValue (highs, "solver", "simplex");
Highs_changeObjectiveSense (highs, kHighsObjSenseMinimize);
assert (Highs_run (highs) == kHighsStatusOk);
printf ("model_status %d, objective %.4f\n",
Highs_getModelStatus (highs), Highs_getObjectiveValue (highs));
assert (Highs_getModelStatus (highs) == kHighsModelStatusOptimal);
double col_value[7], col_dual[7];
double row_value[7], row_dual[7];
Highs_getSolution (highs, col_value, col_dual, row_value, row_dual);
}
Highs_destroy (highs);
}
return 0;
}
$ gcc -Wall -owarmstart-incorrect warmstart-incorrect.c $(pkg-config --cflags --libs highs)
$ ./warmstart-incorrect
0x1af1150 = Highs_create()
model_status 7, objective -106.8759
model_status 7, objective 280.0174
$ gcc -DPROVOKE_FAILURE -Wall -owarmstart-incorrect warmstart-incorrect.c $(pkg-config --cflags --libs highs)
$ ./warmstart-incorrect
0x104f150 = Highs_create()
model_status 7, objective -848.6980
model_status 7, objective -106.8759
warmstart-incorrect: warmstart-incorrect.c:105: main: Assertion `Highs_run (highs) == kHighsStatusOk' failed.
Aborted
Observed using latest commit 003f8e5ded5ef1064ecf901cc9089f63b05b566c.
The simplex solver is concerned about a risk of cycling, so has not made the final basis change required to get an optimal solution. I'll look at this in more detail in due course - I've no time now.
