Add gap synchronization check to stop concurrent solvers

[zengbin5966]

…cess of the SYNCSTORE among concurrent solvers. It checks if the latest gap in the SYNCSTORE meets the predefined limit_gap. If the condition is satisfied, the commit stops updating the shared cache and terminates all ongoing concurrent solver processes.

The changes include:

A new function in syncstore.c that compares the current concurrent gap with the limit_gap and sets the syncstore's stopped flag accordingly. Integration of this check within the synchronization logic to ensure timely termination of solvers when the gap criterion is met. This improvement aims to optimize resource utilization by preventing unnecessary computations once the desired gap threshold is achieved.

[ambros-gleixner]

Thanks! Do you still want to move the call to execConcsolver() or not? See https://github.com/scipopt/scip/pull/107#discussion_r1746813930 .

[ambros-gleixner]

I will rebase this to our internal git where our complete CI runs, get approval, and merge it there. This may take a few days. Afterwards, it will be mirrored on github.

[ambros-gleixner]

I just noted that you used a very long commit line. I will have to rebase this, which will lose your authorship. If this is important to you, then please install https://github.com/scipopt/localhooks and make sure your commit passes these checks.

[zengbin5966]

I just noted that you used a very long commit line. I will have to rebase this, which will lose your authorship. If this is important to you, then please install https://github.com/scipopt/localhooks and make sure your commit passes these checks.

Based on the requirements, I have shortened the content of the commit. Thank you for the reminder.

[svigerske]

@zengbin5966 Would the following changes work for you?

diff --git a/src/scip/struct_syncstore.h b/src/scip/struct_syncstore.h
index d80b267f96..1a89988e31 100644
--- a/src/scip/struct_syncstore.h
+++ b/src/scip/struct_syncstore.h
@@ -57,6 +57,8 @@ struct SCIP_SyncStore
                                               *   by all threads */

    SCIP*                 mainscip;           /**< the SCIP instance that was used for initializing the syncstore */
+   SCIP_Real             limit_gap;          /**< relative gap limit in main SCIP */
+   SCIP_Real             limit_absgap;       /**< absolute gap limit in main SCIP */
    SCIP_Bool             stopped;            /**< flag to indicate if the solving is stopped */
    SCIP_LOCK*            lock;               /**< lock to protect the syncstore data structure from data races */

diff --git a/src/scip/syncstore.c b/src/scip/syncstore.c
index 1130b35252..446a5a476c 100644
--- a/src/scip/syncstore.c
+++ b/src/scip/syncstore.c
@@ -148,6 +148,8 @@ SCIP_RETCODE SCIPsyncstoreInit(
    syncstore = SCIPgetSyncstore(scip);
    assert(syncstore != NULL);
    syncstore->mainscip = scip;
+   SCIP_CALL( SCIPgetRealParam(scip, "limits/gap", &syncstore->limit_gap) );
+   SCIP_CALL( SCIPgetRealParam(scip, "limits/absgap", &syncstore->limit_absgap) );
    syncstore->lastsync = NULL;
    syncstore->nsolvers = SCIPgetNConcurrentSolvers(scip);

@@ -492,7 +494,9 @@ SCIP_RETCODE SCIPsyncstoreFinishSync(

    if( (*syncdata)->syncedcount == syncstore->nsolvers )
    {
-      if( (*syncdata)->status != SCIP_STATUS_UNKNOWN )
+      if( (*syncdata)->status != SCIP_STATUS_UNKNOWN ||
+         (SCIPgetConcurrentGap(syncstore->mainscip) <= syncstore->limit_gap) ||
+         (SCIPgetConcurrentPrimalbound(syncstore->mainscip) - SCIPgetConcurrentDualbound(syncstore->mainscip) <= syncstore->limit_absgap) )
          SCIPsyncstoreSetSolveIsStopped(syncstore, TRUE);

       syncstore->lastsync = *syncdata;

That is, adding the gap check to SCIPsyncstoreFinishSync.

[zengbin5966]

@zengbin5966 Would the following changes work for you?

diff --git a/src/scip/struct_syncstore.h b/src/scip/struct_syncstore.h
index d80b267f96..1a89988e31 100644
--- a/src/scip/struct_syncstore.h
+++ b/src/scip/struct_syncstore.h
@@ -57,6 +57,8 @@ struct SCIP_SyncStore
                                               *   by all threads */

    SCIP*                 mainscip;           /**< the SCIP instance that was used for initializing the syncstore */
+   SCIP_Real             limit_gap;          /**< relative gap limit in main SCIP */
+   SCIP_Real             limit_absgap;       /**< absolute gap limit in main SCIP */
    SCIP_Bool             stopped;            /**< flag to indicate if the solving is stopped */
    SCIP_LOCK*            lock;               /**< lock to protect the syncstore data structure from data races */

diff --git a/src/scip/syncstore.c b/src/scip/syncstore.c
index 1130b35252..446a5a476c 100644
--- a/src/scip/syncstore.c
+++ b/src/scip/syncstore.c
@@ -148,6 +148,8 @@ SCIP_RETCODE SCIPsyncstoreInit(
    syncstore = SCIPgetSyncstore(scip);
    assert(syncstore != NULL);
    syncstore->mainscip = scip;
+   SCIP_CALL( SCIPgetRealParam(scip, "limits/gap", &syncstore->limit_gap) );
+   SCIP_CALL( SCIPgetRealParam(scip, "limits/absgap", &syncstore->limit_absgap) );
    syncstore->lastsync = NULL;
    syncstore->nsolvers = SCIPgetNConcurrentSolvers(scip);

@@ -492,7 +494,9 @@ SCIP_RETCODE SCIPsyncstoreFinishSync(

    if( (*syncdata)->syncedcount == syncstore->nsolvers )
    {
-      if( (*syncdata)->status != SCIP_STATUS_UNKNOWN )
+      if( (*syncdata)->status != SCIP_STATUS_UNKNOWN ||
+         (SCIPgetConcurrentGap(syncstore->mainscip) <= syncstore->limit_gap) ||
+         (SCIPgetConcurrentPrimalbound(syncstore->mainscip) - SCIPgetConcurrentDualbound(syncstore->mainscip) <= syncstore->limit_absgap) )
          SCIPsyncstoreSetSolveIsStopped(syncstore, TRUE);

       syncstore->lastsync = *syncdata;

That is, adding the gap check to SCIPsyncstoreFinishSync.

oh wow! I think your changes should be better. :-)

[svigerske]

The changes are now or soon on branches master and v9-minor.