Decision Optimization

 View Only
  • 1.  Conflict Refiner: removing infeasible jobs

    Posted Sun February 28, 2021 11:06 AM

    Suppose we are dealing with a large scale CSP problem with 100 machines and 1000 jobs with lots of precedency constraints so the goal is to generate a feasible solution. Due to heavily interwoven constraints, a problem instance often has infeasible jobs, which cannot be checked in advance. In this case, what I hope to accomplish is to automatically remove the minimum number of jobs by using Conflict Refiner.

    In the following code, I would like to screen out jobs 5, 7 and 9. Surely, we can turn the interval into "Optional" and maximize the present job count. But, I would like to see if we can utilize Conflict Refiner to remove the minimum number of jobs, for my large-scale CSP problem. 

    using CP;
    tuple t_Job {
    key int j;
    int sz;
    int grp;
    int loc;
    } {t_Job} Jobs = {
    <1, 1, 100, 80>,
    <2, 2, 100, 40>,
    <3, 3, 100, 80>,
    <4, 4, 200, 40>,
    <5, 5, 200, 40>,
    <6, 6, 200, 80>,
    <7, 7, 200, 40>,
    <8, 8, 300, 80>,
    <9, 9, 300, 40>,
    <10,10,300, 80>};

    dvar interval itvj[j in Jobs] size j.sz;
    dvar sequence Mch in all(j in Jobs) itvj[j];

    minimize max(j in Jobs)endOf(itvj[j]);
    subject to {
    forall(j in Jobs)
    if(j.sz >=5 && j.loc==40) presenceOf(itvj[j])==0;
    noOverlap(Mch);
    }


    #DecisionOptimization


  • 2.  RE: Conflict Refiner: removing infeasible jobs

    Posted Mon March 01, 2021 03:26 AM
    If the infeasibility is due to the interactions between jobs and not to the constraints inside the jobs themselves, then I think the conflict refiner will be of little help here, except for identifying some reason why the problem is globally infeasible. Indeed, if the infeasibility is global (for instance because the problem is over constrained and there is no enough resource capacity to execute all jobs), then there will be a compromise to be done for deciding which jobs to abandon (for instance it could be jobs 5&7&9 or maybe 3&7&9) and some combination may be better than others. So I think the best here is as you suggest to have all (or at least some) jobs optional and minimize the number (or a weighted sum if jobs have priorities) of abandoned jobs.

    If the infeasibility is local to the jobs (for instance some deadlines that are clearly too tight given the temporal constraints between the operations on the job), then you could solve 1 small subproblem per job (with only the interval variables of the job) with SolutionLimit=1 (stop at first feasible solution) to check that the job is (locally) feasible. If it is infeasible, in this case you can use the conflict refiner to find why.

    ------------------------------
    Philippe Laborie
    ------------------------------



  • 3.  RE: Conflict Refiner: removing infeasible jobs

    Posted Mon March 01, 2021 04:45 PM
    Edited by System Fri January 20, 2023 04:44 PM

    I believe the infeasibility is global in my problem. However, "1 small subproblem per job with SolutionLimit=1" is very interesting, something to explore further. Thanks!


    #DecisionOptimization