Model is infeasible when there is too many interval vars

[N L]

Hello!

I am working on a production planner application.
The following are the requirements for the program:

- It must plan a complete value stream, including all of its production lines.

- The user specifies which type numbers they want to produce on the final assembly lines, when and in what quantity.

- A production line can manufacture multiple types of products, and according to the BOM, a single product can be assembled from several variations.
- Changeovers must be minimized and penalized with setup time.
- The production lines include scheduled downtimes.
-  There are supermarket storages between the segments (groups of production lines).
-  A package size is defined for each segment, and products can only enter the supermarket in full packages.

Solution:

I have created a reservoir for each part number, which simulates the supermarket. Production is represented by OptionalFixedSizeIntervalVars (operations), where each interval corresponds to a package size. The interval size is calculated as the product of the cycle time and the number of units in the package. Each operation both deposits into and withdraws from the reservoirs.

The number of interval variables (operations) is determined as follows: 

If 1100 units of product "A" are needed on the final assembly line, then for each preassembly production line I create as many interval variables as I can within the available time, but I produce no more than 1000 units.  If a production line can manufacture three types of products (for example) that are compatible with A, then I create the maximum number of interval variables for all three products. I have attached an example excel file that contains what I generate when I need to produce 1100 pieces on the final assembly line.

Of course the model contains other things, but they are not relevant to my question.

My problem is that if I set a very high target quantity and there are too many intervals, the model tends to get stuck for minutes in an infeasible state and fails to find an optimal solution. When I handled breaks by not using fixed-size intervals, but instead increasing their size if they overlapped with a break, the problem became even worse. I have more than 20 production lines, usually with 1–5 producible part numbers each.  

public Dictionary<string, List<LotProduction>> GetLotProductions()
{
    Dictionary<string, List<LotProduction>> lotProductions = [];
    foreach ((string productionLineId, List<LotProductionInfo> lotProductionInfos) in lotProductionInfosByLineId)
    {
        foreach (LotProductionInfo lotProductionInfo in lotProductionInfos)
        {
            var bomStructure = bomStructures[lotProductionInfo.TypeNumber.Name];
            for (int lotProductionInfoIndex = 0; lotProductionInfoIndex < lotProductionInfo.LotCount; lotProductionInfoIndex++)
            {
                BoolVar isProduced = model.NewBoolVar(nameof(isProduced));
                IntVar lotProductionStart = model.NewIntVar(lotProductionInfo.ProductionStart, lotProductionInfo.ProductionEnd, nameof(lotProductionStart));

                IntervalVar lotProductionTask = model.NewOptionalFixedSizeIntervalVar(
                    lotProductionStart,
                    lotProductionInfo.LotProductionTime,
                    isProduced,
                    nameof(lotProductionTask));

                supermarketsByProduct[lotProductionInfo.TypeNumber.Name]
                    .AddOptionalEvent(lotProductionStart + lotProductionInfo.LotProductionTime, lotProductionInfo.LotSize, isProduced);

                List<List<LotProductionComponent>> lotComponents = [];
                if (lotProductionInfo.TypeNumber.Name != "3394240004")
                {
                    lotComponents = GetLotComponents(bomStructure, isProduced, lotProductionStart, lotProductionInfo.LotSize, lotProductionInfo.ProConId);
                }

                LotProduction lotProduction = new()
                {
                    Product = lotProductionInfo.TypeNumber.Name,
                    LotProductionInfo = lotProductionInfo,
                    ProductionTask = lotProductionTask,
                    LotProductionStart = lotProductionStart,
                    Output = lotProductionInfo.LotSize,
                    IsProduced = isProduced,
                    Components = lotComponents,
                };

                everyLotProductions.Add(lotProduction);
                lotProductions.Push(productionLineId, lotProduction);
            }
        }
    }

    return lotProductions;
}

private List<List<LotProductionComponent>> GetLotComponents(SeparatedBomEntry bomStructure, BoolVar isProduced, IntVar lotProductionStart, int lotSize, int proconId)
{
    List<List<LotProductionComponent>> lotComponents = [];
    foreach (BomEntry nonVariant in bomStructure.NonVariants)
    {
        ComponentType componentType;
        long nonVariantDemand;

        List<List<LotProductionComponent>> dummyComponents = [];
        if (nonVariant.Procurement == BomEntry.PROCUREMENT_F)
        {
            componentType = ComponentType.F;

            nonVariantDemand = GetStockDemand(nonVariant, lotSize);
            IntVar stockDemand = model.NewIntVar(0, nonVariantDemand, nameof(stockDemand));

            model.Add(stockDemand == LinearExpr.Term(isProduced, nonVariantDemand));
            commonStockDemandByProduct.Push(nonVariant.Component, stockDemand);
        }
        else if (supermarketStock.ContainsKey(nonVariant.Component))
        {
            componentType = ComponentType.E;
            nonVariantDemand = (long)(nonVariant.Quantity * lotSize);

            supermarketsByProduct[nonVariant.Component].AddOptionalEvent(lotProductionStart, -nonVariantDemand, isProduced);
        }
        else
        {
            componentType = ComponentType.Dummy;
            nonVariantDemand = (long)(nonVariant.Quantity * lotSize);

            if (bomStructures.TryGetValue(nonVariant.Component, out SeparatedBomEntry? dummyBomStructure))
            {
                dummyComponents = GetLotComponents(dummyBomStructure, isProduced, lotProductionStart, (int)nonVariantDemand, proconId);
            }
        }

        LotProductionComponent component = new()
        {
            BomNode = nonVariant,
            IsActive = isProduced,
            Demand = nonVariantDemand,
            ComponentType = componentType,
            DummyComponents = dummyComponents,
        };

        lotComponents.Add([component]);
        everyLotComponentProductions.Add(component);
    }

    foreach (BomEntryVariantGroup variantGroup in bomStructure.VariantGroups)
    {
        List<LotProductionComponent> variants = [];
        List<BoolVar> isActives = [];

        foreach (BomEntry variant in variantGroup.BomEntries)
        {
            ComponentType componentType;
            long variantDemand;
            bool isSupermarket = false;

            List<List<LotProductionComponent>> dummyComponents = [];

            BoolVar isActive = model.NewBoolVar("isActive");
            isActives.Add(isActive);

            if (variant.Procurement == BomEntry.PROCUREMENT_F)
            {
                componentType = ComponentType.F;

                variantDemand = GetStockDemand(variant, lotSize);
                IntVar stockDemand = model.NewIntVar(0, variantDemand, nameof(stockDemand));

                model.Add(stockDemand == LinearExpr.Term(isActive, variantDemand));
                commonStockDemandByProduct.Push(variant.Component, stockDemand);
            }
            else if (supermarketStock.ContainsKey(variant.Component))
            {
                componentType = ComponentType.E;
                variantDemand = (long)(variant.Quantity * lotSize);

                isSupermarket = true;
                supermarketsByProduct[variant.Component].AddOptionalEvent(lotProductionStart, -variantDemand, isActive);
            }
            else
            {
                componentType = ComponentType.Dummy;
                variantDemand = (int)(variant.Quantity * lotSize);

                if (bomStructures.TryGetValue(variant.Component, out SeparatedBomEntry? dummyBomStructure))
                {
                    dummyComponents = GetLotComponents(dummyBomStructure, isActive, lotProductionStart, (int)variantDemand, proconId);
                }
            }

            LotProductionComponent component = new()
            {
                BomNode = variant,
                IsActive = isActive,
                Demand = variantDemand,
                ComponentType = componentType,
                DummyComponents = dummyComponents
            };

            if (isSupermarket)
            {
                removes.Push(variant.Component, component);
            }

            variants.Add(component);
            everyLotComponentProductions.Add(component);
        }

        model.Add(LinearExpr.Sum(isActives) == isProduced);

        lotComponents.Add(variants);
    }

    return lotComponents;
}

private void LimitActiveLotProductions(List<PlanPeriod> proconProductions)
{
    foreach (var chosenProductionLine in chosenProductionLines)
    {
        SegmentEntity segment = segments.First(s => s.Id == chosenProductionLine.SegmentId);
        SimpleLocation location = locationsByLineId[chosenProductionLine.LineId];

        long productionStart = location.ShiftStart;
        long productionEnd = location.ShiftEnd;
        long productionHorizon = productionEnd - productionStart;

        long occupiedTime = location.Downtimes
           .Aggregate(0L, (occupiedTime, downtime) =>
           {
               long overlapStart = Math.Max(downtime.SectionStart, productionStart);
               long overlapEnd = Math.Min(downtime.SectionEnd, productionEnd);

               return overlapStart < overlapEnd
                   ? occupiedTime + (overlapEnd - overlapStart)
                   : occupiedTime;
           });

        List<LinearExpr> lotProductionTimes = everyLotProductions
            .Where(lp => lp.LotProductionInfo.LineId == chosenProductionLine.LineId)
            .Select(lp => lp.IsProduced * lp.LotProductionInfo.LotProductionTime)
            .ToList();

        model.Add(LinearExpr.Sum(lotProductionTimes) <= productionHorizon - occupiedTime);
    }

    foreach (var segmentProductionLines in chosenProductionLines.GroupBy(p => p.SegmentId))
    {
        List<string> productionLineIds = segmentProductionLines
            .Select(p => p.LineId)
            .ToList();

        List<IGrouping<string, LotProduction>> segmentLotProductions = everyLotProductions
            .Where(lp => productionLineIds.Contains(lp.LotProductionInfo.LineId))
            .GroupBy(lp => lp.LotProductionInfo.JobTypeNumber)
            .ToList();

        foreach (var kvp in segmentLotProductions)
        {
            if (maxLotCountBySegment.TryGetValue((segmentProductionLines.Key, kvp.Key), out int max))
            {
                List<BoolVar> isProduceds = kvp
                    .Select(lp => lp.IsProduced)
                    .ToList();

                model.Add(LinearExpr.Sum(isProduceds) <= max);
            }
        }
    }
}

private void LimitChangeoverLoss()
{
    List<IGrouping<string, LotProduction>> lotProductionsByLineId = everyLotProductions
        .GroupBy(l => l.LotProductionInfo.LineId)
        .ToList();

    foreach (var kvp in lotProductionsByLineId)
    {
        LotProduction[] lotProductions = [.. kvp];
        int typesCount = kvp.GroupBy(p => p.Product).Count();

        if (typesCount == 1)
        {
            continue;
        }

        CircuitConstraint circuit = model.AddCircuit();

        for (int lp1 = 0; lp1 < lotProductions.Length; lp1++)
        {
            BoolVar isFirst = model.NewBoolVar(nameof(isFirst));
            BoolVar isLast = model.NewBoolVar(nameof(isLast));

            circuit.AddArc(0, lp1 + 1, isFirst);
            circuit.AddArc(lp1 + 1, 0, isLast);

            model.AddImplication(lotProductions[lp1].IsProduced.Not(), isFirst.Not());
            model.AddImplication(lotProductions[lp1].IsProduced.Not(), isLast.Not());

            for (int lp2 = 0; lp2 < lotProductions.Length; lp2++)
            {
                if (lp1 == lp2)
                {
                    circuit.AddArc(lp1 + 1, lp1 + 1, lotProductions[lp1].IsProduced.Not());
                    continue;
                }

                BoolVar isNext = model.NewBoolVar(nameof(isNext));
                circuit.AddArc(lp1 + 1, lp2 + 1, isNext);

                model.AddImplication(isNext, lotProductions[lp1].IsProduced);
                model.AddImplication(isNext, lotProductions[lp2].IsProduced);

                LinearExpr nextProductionStart = lotProductions[lp2].ProductionTask.StartExpr();
                LinearExpr currentProductionEnd = lotProductions[lp1].ProductionTask.EndExpr();
                long minDistance = lotProductions[lp1].Product != lotProductions[lp2].Product
                    ? (long)TimeSpan.FromMinutes(5).TotalMilliseconds
                    : 0;

                long changeoverLoss = lotProductions[lp1].Product != lotProductions[lp2].Product
                    ? -1
                    : 0;

                model.Add(nextProductionStart >= currentProductionEnd + minDistance).OnlyEnforceIf(isNext);

                changeoverLossesByLineId.Push(kvp.Key, changeoverLoss * isNext);
            }
        }
    }
}

[Laurent Perron]

what do you mean by infeasible ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/c3ad3a3d-0549-43f1-bdba-ba15e30d9deen%40googlegroups.com.

[N L]

Sorry, I meant to say it stops in the FEASIBLE state. It starts searching and gets very close to the optimal solution based on log, but then stops and only one thing helps, if I add a max searching time. If I create an easily solvable model (much less interval than the maximum production time of the production line) then it works properly, but in reality, they (the users of the program) usually want to produce as much as they can on a production line.

[Laurent Perron]

so, you are creating a large NP-Hard problem, and you expect the solver to always produce an optimal solution in a reasonable time frame? 

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/10a388cf-1069-4f4b-9dbe-5588a03b791dn%40googlegroups.com.

[N L]

Should I not expect it? I'm totally fine if the solution isn't perfect—I just thought I made a mistake somewhere, and that's why it behaves like this.
What do you think, can I optimize my target (or my model) somehow to simplify the goal for the model? I am a beginner, this is the first program what I made with an optimization tool, I just want to know where is the limits or what can I expect from it.