[Feature Request] Time limit for Problem

[jk2997]

Hello,

I was wondering if there could be a time limit feature for struct Problem that leads microlp to end the solver before it has found the optimal value of the objective function and produce a Solution after a certain time interval.

[Specy]

For looking at time I'd have to add an OS module which I rather not add as it complicates things.

What about if I add a step limit, with which after that limit is reached I return an error, you can check the time elapsed and in case it's over your predefined amount, you can stop, or in case there is still time you can continue execution?

[jk2997]

Yes, I would very much prefer that idea. Thank you for considering.

[jk2997]

I would also appreciate it if you updated the microlp crate after the changes.

[Specy]

Ok looking at the code it seems to be a bigger task than I expected, Right now the stack that is used to track integer variables is stored in memory and I cannot have it be "resumable", I'd have to find a good way to push it out of memory and place it in the Solver struct (maybe, or some other solution). Plus I'd have to make other tests to track the correctness of the solver with this new resumable functionality.

I don't have much time to work on such an issue lately so if someone else wants to pick it up I'd be glad.
Maybe I'll manage to get some free time to implement it but I don't have an ETA.

[jk2997]

@Specy Even if it requires implementing an OS module, I'll try to figure out using Rust's std::time to implement a time limit for microlp as an optional feature. I will come back to this Issue once I have figured it out.

[Specy]

Even when implement time limit, when the limit is reached it will cause the solver to be in an invalid state since if you call the solver again it might potentially visit already considered variables and cycle back again

[jk2997]

I see. I was planning to develop an application with microlp, but I'll have to modify that project so that the time limit feature doesn't become an issue. Thank you.

[Specy]

I'll keep the issue open to track the feature request as it's an useful addition

[ShelbyJenkins]

I'm having the same issue. Some solves are taking so long, and there is no way to kill them and move on. Ended up doing something cursed.

pub enum SolverWrapper<S> {
    Optimal(S),
    TimeLimit,
    GapLimit,
    Infeasible,
    Unbounded,
    ConcurrencyLimit,
    Other(String),
}

impl<S> SolverWrapper<S>
where
    S: Solution + Send + 'static,
{
    pub fn is_feasible<M>(
        model: M,
        module: &'static str,
        function: &'static str,
        context: &'static str,
        timeout: Option<std::time::Duration>,
    ) -> Result<bool, SolverError>
    where
        M: SolverModel<Error = ResolutionError, Solution = S> + Send + 'static,
        S: Send + 'static,
    {
        match Self::run(model, timeout) {
            SolverWrapper::Optimal(_) => Ok(true),
            SolverWrapper::Infeasible => Ok(false),
            SolverWrapper::Unbounded => Err(SolverError::Unbounded {
                module,
                function,
                context,
            }),
            SolverWrapper::TimeLimit => Err(SolverError::TimeLimit {
                module,
                function,
                context,
            }),
            SolverWrapper::GapLimit => Err(SolverError::GapLimit {
                module,
                function,
                context,
            }),
            SolverWrapper::ConcurrencyLimit => Err(SolverError::ConcurrencyLimit {
                module,
                function,
                context,
                max: MAX_CONCURRENT_SOLVERS,
            }),
            SolverWrapper::Other(error) => Err(SolverError::Other {
                module,
                function,
                context,
                error,
            }),
        }
    }

    pub fn solution<M>(
        model: M,
        module: &'static str,
        function: &'static str,
        context: &'static str,
        timeout: Option<std::time::Duration>,
    ) -> Result<S, SolverError>
    where
        M: SolverModel<Error = ResolutionError, Solution = S> + Send + 'static,
        S: Send + 'static,
    {
        match Self::run(model, timeout) {
            SolverWrapper::Optimal(s) => Ok(s),
            SolverWrapper::Infeasible => Err(SolverError::Infeasible {
                module,
                function,
                context,
            }),
            SolverWrapper::Unbounded => Err(SolverError::Unbounded {
                module,
                function,
                context,
            }),
            SolverWrapper::TimeLimit => Err(SolverError::TimeLimit {
                module,
                function,
                context,
            }),
            SolverWrapper::GapLimit => Err(SolverError::GapLimit {
                module,
                function,
                context,
            }),
            SolverWrapper::ConcurrencyLimit => Err(SolverError::ConcurrencyLimit {
                module,
                function,
                context,
                max: MAX_CONCURRENT_SOLVERS,
            }),
            SolverWrapper::Other(error) => Err(SolverError::Other {
                module,
                function,
                context,
                error,
            }),
        }
    }

    fn run<M>(model: M, timeout: Option<Duration>) -> Self
    where
        M: SolverModel<Error = ResolutionError, Solution = S> + Send + 'static,
        S: Send + 'static,
    {
        if let Some(duration) = timeout {
            // 1. Try to acquire semaphore
            let permit = match SolverPermit::try_acquire() {
                Some(p) => p,
                None => return SolverWrapper::ConcurrencyLimit,
            };

            let (tx, rx) = mpsc::channel();

            // 2. Spawn thread
            // We move `permit` INTO the thread. It will drop (and decrement counter)
            // only when the *thread* finishes, ensuring zombie threads count against the limit.
            thread::spawn(move || {
                let _keep_permit_alive = permit;
                let result = model.solve();
                let _ = tx.send(result);
            });

            // 3. Wait with timeout
            match rx.recv_timeout(duration) {
                Ok(solve_result) => Self::process_result(solve_result),
                Err(mpsc::RecvTimeoutError::Timeout) => SolverWrapper::TimeLimit,
                Err(mpsc::RecvTimeoutError::Disconnected) => {
                    SolverWrapper::Other("Solver thread disconnected unexpectedly".to_string())
                }
            }
        } else {
            // Run synchronously on current thread (existing behavior)
            // No semaphore needed here as it blocks the caller anyway.
            Self::process_result(model.solve())
        }
    }

    fn process_result(result: Result<S, ResolutionError>) -> Self {
        match result {
            Ok(s) => match s.status() {
                SolutionStatus::Optimal => SolverWrapper::Optimal(s),
                SolutionStatus::TimeLimit => SolverWrapper::TimeLimit,
                SolutionStatus::GapLimit => SolverWrapper::GapLimit,
            },
            Err(e) => match e {
                ResolutionError::Infeasible => SolverWrapper::Infeasible,
                ResolutionError::Unbounded => SolverWrapper::Unbounded,
                ResolutionError::Other(msg) => SolverWrapper::Other(msg.to_string()),
                ResolutionError::Str(msg) => SolverWrapper::Other(msg),
            },
        }
    }
}

// If microlp ever adds timeout functionality, we can remove this concurrency limit.
const MAX_CONCURRENT_SOLVERS: usize = 8;
static ACTIVE_SOLVER_THREADS: AtomicUsize = AtomicUsize::new(0);

struct SolverPermit;

impl SolverPermit {
    /// Tries to acquire a slot. Returns None if MAX_CONCURRENT_SOLVERS is reached.
    fn try_acquire() -> Option<Self> {
        ACTIVE_SOLVER_THREADS
            .fetch_update(Ordering::SeqCst, Ordering::SeqCst, |count| {
                if count < MAX_CONCURRENT_SOLVERS {
                    Some(count + 1)
                } else {
                    None
                }
            })
            .ok()
            .map(|_| SolverPermit)
    }

    /// Returns the current count of active/zombie threads.
    #[allow(dead_code)]
    fn count() -> usize {
        ACTIVE_SOLVER_THREADS.load(Ordering::SeqCst)
    }
}

impl Drop for SolverPermit {
    fn drop(&mut self) {
        ACTIVE_SOLVER_THREADS.fetch_sub(1, Ordering::SeqCst);
    }
}