// (c) 2023-2025 Fair Isaac Corporation
using System;
using Optimizer;
using Optimizer.Objects;
using static Optimizer.Objects.Utils;
namespace XpressExamples
{
/// <summary>Economic lot sizing, ELS, problem</summary>
/// <remarks>
/// Solved by adding (l,S)-inequalities in several rounds looping over
/// the root node.
///
/// ELS considers production planning over a horizon
/// of T periods. In period t, t=1,...,T, there is a
/// given demand DEMAND[t] that must be satisfied by
/// production prod[t] in period t and by inventory
/// carried over from previous periods. There is a
/// set-up up cost SETUPCOST[t] associated with
/// production in period t. The unit production cost
/// in period t is PRODCOST[t]. There is no inventory
/// or stock-holding cost.
/// </remarks>
class ELS
{
private static readonly double EPS = 1e-6;
private static readonly int T = 6; /* Number of time periods */
/* Data */
private static readonly double[] DEMAND = { 1, 3, 5, 3, 4, 2 }; /* Demand per period */
private static readonly double[] SETUPCOST = { 17, 16, 11, 6, 9, 6 }; /* Setup cost / period */
private static readonly double[] PRODCOST = { 5, 3, 2, 1, 3, 1 }; /* Prod. cost / period */
private static double[,] D; /* Total demand in periods t1 - t2 */
/* Variables and constraints */
private static Variable[] prod; /* Production in period t */
private static Variable[] setup; /* Setup in period t */
/***********************************************************************/
private static void ModEls(XpressProblem p)
{
D = new double[T, T];
for (int s = 0; s < T; s++)
for (int t = 0; t < T; t++)
for (int k = s; k <= t; k++)
D[s, t] += DEMAND[k];
// Variables
prod = p.AddVariables(T)
.WithType(ColumnType.Continuous)
.WithName(t => $"prod{t + 1}")
.ToArray();
setup = p.AddVariables(T)
.WithType(ColumnType.Binary)
.WithName(t => $"setup{t + 1}")
.ToArray();
// Objective: Minimize total cost
p.SetObjective(
Sum(
ScalarProduct(setup, SETUPCOST),
ScalarProduct(prod, PRODCOST)
),
Optimizer.ObjSense.Minimize
);
// Constraints
// Production in period t must not exceed the total demand for the
// remaining periods; if there is production during t then there
// is a setup in t
// for all t in [0,T[
// prod[t] <= setup[t] * D[t][T-1]
p.AddConstraints(T,
t => prod[t].Leq(setup[t] * D[t, T - 1]).SetName($"Production_{t}")
);
// Production in periods 0 to t must satisfy the total demand
// during this period of time
// for all t in [0,T[
// sum(s in [0,t+1[) prod[s] >= D[0][t]
p.AddConstraints(T,
t => Sum(t + 1, t => prod[t]).Geq(D[0, t]).SetName($"Demand_{t}")
);
p.WriteProb("ELS.lp", "l");
}
/**************************************************************************/
/* Cut generation loop at the top node: */
/* solve the LP and save the basis */
/* get the solution values */
/* identify and set up violated constraints */
/* load the modified problem and load the saved basis */
/**************************************************************************/
private static void SolveEls(XpressProblem p)
{
// Output all messages.
p.callbacks.AddMessageCallback(DefaultMessageListener.Console);
/* Disable automatic cuts - we use our own */
p.CutStrategy = (int)Optimizer.CutStrategy.None;
/* Switch presolve off */
p.Presolve = (int)Optimizer.Presolve.None;
int ncut = 0, npass = 0, npcut = 0;
long starttime = Environment.TickCount64;
double[] sol;
do
{
p.WriteProb("model" + npass + ".lp", "l");
npass++;
npcut = 0;
// Solve the LP-problem
p.LpOptimize();
if (p.SolStatus != Optimizer.SolStatus.Optimal)
throw new Exception("failed to optimize with status " + p.SolStatus);
// Get the solution values:
sol = p.GetSolution();
// Search for violated constraints:
for (int l = 0; l < T; l++)
{
double ds = 0.0;
for (int t = 0; t <= l; t++)
{
if (prod[t].GetValue(sol) < D[t, l] * setup[t].GetValue(sol) + EPS)
{
ds += prod[t].GetValue(sol);
}
else
{
ds += D[t, l] * setup[t].GetValue(sol);
}
}
/* Add the violated inequality: the minimum of the actual production
prod[t] and the maximum potential production D[t][l]*setup[t]
in periods 0 to l must at least equal the total demand in periods
0 to l.
sum(t=1:l) min(prod[t], D[t][l]*setup[t]) >= D[0][l] */
if (ds < D[0, l] - EPS)
{
LinExpression cut = new LinTermMap(0);
for (int t = 0; t <= l; t++)
{
if (prod[t].GetValue(sol) < D[t, l] * setup[t].GetValue(sol) + EPS)
cut.AddTerm(prod[t]);
else
cut.AddTerm(setup[t] * D[t, l]);
}
p.AddConstraint((cut >= D[0, l]).SetName($"cut_{ncut + 1}"));
ncut++;
npcut++;
}
}
Console.WriteLine("Iteration {0:d}, {1:f2} sec, objective value: {2:f}, cuts added: {3:d} (total {4:d})",
npass,
(Environment.TickCount64 - starttime) / 1000.0,
p.ObjVal,
npcut,
ncut
);
if (npcut == 0)
Console.WriteLine("Optimal integer solution found:");
} while (npcut > 0);
// Print out the solution:
for (int t = 0; t < T; t++)
{
Console.WriteLine(
"Period {0:d}: prod {1:f1} (demand: {2:f0}, cost: {3:f0}), setup {4:f0} (cost {5:f0})",
t + 1,
prod[t].GetValue(sol),
DEMAND[t],
PRODCOST[t],
setup[t].GetValue(sol),
SETUPCOST[t]
);
}
}
public static void Main(string[] args)
{
using (XpressProblem prob = new XpressProblem())
{
ModEls(prob); // Model the problem
SolveEls(prob); // Solve the problem
}
}
}
}
|
// (c) 2023-2025 Fair Isaac Corporation
using System;
using Optimizer.Objects;
using Optimizer;
using static Optimizer.Objects.Utils;
namespace XpressExamples
{
/// <summary>Economic lot sizing, ELS, problem</summary>
/// <remarks>
/// Solved by adding (l,S)-inequalities in a branch-and-cut heuristic
/// (using the cut manager).
///
/// ELS considers production planning over a horizon
/// of T periods. In period t, t=1,...,T, there is a
/// given demand DEMAND[t] that must be satisfied by
/// production prod[t] in period t and by inventory
/// carried over from previous periods. There is a
/// set-up up cost SETUPCOST[t] associated with
/// production in period t. The unit production cost
/// in period t is PRODCOST[t]. There is no inventory
/// or stock-holding cost.
///
/// <b>This model cannot be run with a Community Licence</b>
/// </remarks>
class ELSCut
{
private static readonly double EPS = 1e-6;
private static readonly int T = 6; /* Number of time periods */
/* Data */
private static readonly double[] DEMAND = { 1, 3, 5, 3, 4, 2 }; /* Demand per period */
private static readonly double[] SETUPCOST = { 17, 16, 11, 6, 9, 6 }; /* Setup cost / period */
private static readonly double[] PRODCOST = { 5, 3, 2, 1, 3, 1 }; /* Prod. cost / period */
private static readonly double[,] D = new double[T, T]; /* Total demand in periods t1 - t2 */
/* Variables and constraints */
private static Variable[] prod; /* Production in period t */
private static Variable[] setup; /* Setup in period t */
private static void PrintProblemStatus(XpressProblem prob)
{
Console.WriteLine("Problem status:");
Console.WriteLine($"\tSolve status: {prob.SolveStatus}");
Console.WriteLine($"\tLP status: {prob.LPStatus}");
Console.WriteLine($"\tMIP status: {prob.MIPStatus}");
Console.WriteLine($"\tSol status: {prob.SolStatus}");
}
/// <summary>Cut generation algorithm (implemented as optnode callback).</summary>
/// <remarks>
/// - get the solution values
/// - identify and set up violated constraints
/// - add cuts to the problem
/// </remarks>
private static int OptNode(XpressProblem p)
{
double[] sol, slack, duals, djs;
int ncut = 0;
// Add cut only to optimal relaxations
if (p.LPStatus != Optimizer.LPStatus.Optimal)
{
return 0;
}
sol = p.GetCallbackSolution();
slack = p.GetCallbackSlacks();
duals = p.GetCallbackDuals();
djs = p.GetCallbackRedCosts();
// Search for violated constraints:
for (int l = 0; l < T; l++)
{
double ds = 0.0;
for (int t = 0; t <= l; t++)
{
if (prod[t].GetValue(sol) < D[t, l] * setup[t].GetValue(sol) + EPS)
{
ds += prod[t].GetValue(sol);
}
else
{
ds += D[t, l] * setup[t].GetValue(sol);
}
}
// Add the violated inequality: the minimum of the actual production
// prod[t] and the maximum potential production D[t][l]*setup[t]
// in periods 0 to l must at least equal the total demand in periods
// 0 to l.
// sum(t=1:l) min(prod[t], D[t][l]*setup[t]) >= D[0][l] */
if (ds < D[0, l] - EPS)
{
LinExpression cut = new LinTermMap(0);
for (int t = 0; t <= l; t++)
{
if (prod[t].GetValue(sol) < D[t, l] * setup[t].GetValue(sol) + EPS)
{
cut.AddTerm(prod[t]);
}
else
{
cut.AddTerm(setup[t] * D[t, l]);
}
}
p.AddCut(0, cut >= D[0, 1]);
ncut++;
}
}
if (ncut > 0)
{
Console.WriteLine($"Cuts added: {ncut} (depth {p.NodeDepth}, node {p.Nodes})");
}
return 0;
}
/***********************************************************************/
private static void ModEls(XpressProblem p)
{
for (int s = 0; s < T; s++)
for (int t = 0; t < T; t++)
for (int k = s; k <= t; k++)
D[s, t] += DEMAND[k];
// Variables
prod = p.AddVariables(T)
.WithType(ColumnType.Continuous)
.WithName(t => $"prod{t + 1}")
.ToArray();
setup = p.AddVariables(T)
.WithType(ColumnType.Binary)
.WithName(t => $"setup{t + 1}")
.ToArray();
// Objective: Minimize total cost
p.SetObjective(
Sum(
ScalarProduct(setup, SETUPCOST),
ScalarProduct(prod, PRODCOST)
),
Optimizer.ObjSense.Minimize
);
// Constraints
// Production in period t must not exceed the total demand for the
// remaining periods; if there is production during t then there
// is a setup in t
// for all t in [0,T[
// prod[t] <= setup[t] * D[t][T-1]
p.AddConstraints(T,
t => prod[t].Leq(setup[t] * D[t, T - 1]).SetName($"Production_{t}")
);
// Production in periods 0 to t must satisfy the total demand
// during this period of time
// for all t in [0,T[
// sum(s in [0,t+1[) prod[s] >= D[0][t]
p.AddConstraints(T,
t => Sum(t + 1, t => prod[t]).Geq(D[0, t]).SetName($"Demand_{t}")
);
p.WriteProb("ELSCut.lp", "l");
}
/// <summary>Solve the model.</summary>
/// <remarks>
/// Cuts are added dynamically with the optnode callback.
/// </remarks>
/// <param name='p'>The problem to solve.</param>
private static void SolveEls(XpressProblem p)
{
// Output all messages.
p.callbacks.AddMessageCallback(DefaultMessageListener.Console);
p.LPLog = 0;
p.MIPLog = 3;
// Disable automatic cuts - we use our own
p.CutStrategy = (int)Optimizer.CutStrategy.None;
// Switch presolve off
p.Presolve = (int)Optimizer.Presolve.None;
p.MIPPresolve = 0;
p.callbacks.AddOptnodeCallback(OptNode);
/* Solve the MIP */
p.MipOptimize();
if (p.SolStatus != Optimizer.SolStatus.Optimal)
throw new Exception("optimization failed with status " + p.SolStatus);
/* Get the solution values: */
double[] sol = p.GetSolution();
/* Print out the solution: */
for (int t = 0; t < T; t++)
{
Console.WriteLine(
"Period {0:%d}: prod {1:f1} (demand: {2:f0}, cost: {3:f0}), setup {4:f0} (cost {5:f0})",
t + 1,
prod[t].GetValue(sol),
DEMAND[t],
PRODCOST[t],
setup[t].GetValue(sol),
SETUPCOST[t]
);
}
PrintProblemStatus(p);
}
public static void Main(string[] args)
{
using (XpressProblem prob = new XpressProblem())
{
ModEls(prob); // Model the problem
SolveEls(prob); // Solve the problem
}
}
}
}
|
// (c) 2025-2025 Fair Isaac Corporation
using System;
using Optimizer;
using Optimizer.Objects;
using static Optimizer.Objects.Utils;
namespace XpressExamples
{
/// <summary>Demonstrates how to implement cutting planes as part of a MIP branch-and-bound search using the cutround callback.</summary>
/// <remarks>
/// Cuts are added as user cuts using XpressProblem.AddManagedCut().
///
/// Economic lot sizing problem. Solved by adding (l,S)-inequalities
/// in a branch-and-cut heuristic (using the cutround callback).
///
/// ELS considers production planning over a horizon of T periods. In period t,
/// t=1,...,T, there is a given demand DEMAND[p,t] that must be satisfied by
/// production produce[p,t] in period t and by inventory carried over
/// from previous periods.
/// There is a set-up cost SETUPCOST[t] associated with production in
/// period t and the total production capacity per period is limited. The unit
/// production cost in period t is PRODCOST[p,t]. There is no
/// inventory or stock-holding cost.
///
/// A well-known class of valid inequalities for ELS are the
/// (l,S)-inequalities. Let D(p,q) denote the demand in periods p
/// to q and y(t) be a binary variable indicating whether there is any
/// production in period t. For each period l and each subset of periods S
/// of 1 to l, the (l,S)-inequality is
/// <pre>
/// sum (t=1:l | t in S) x(t) + sum (t=1:l | t not in S) D(t,l)/// y(t)
/// >= D(1,l)
/// </pre>
///
/// It says that actual production x(t) in periods included S plus maximum
/// potential production D(t,l)*y(t) in the remaining periods (those not in
/// S) must at least equal total demand in periods 1 to l. Note that in
/// period t at most D(t,l) production is required to meet demand up to
/// period l.
///
/// Based on the observation that
/// <pre>
/// sum (t=1:l | t in S) x(t) + sum (t=1:l | t not in S) D(t,l)/// y(t)
/// >= sum (t=1:l) min(x(t), D(t,l)/// y(t))
/// >= D(1,l)
/// </pre>
/// it is easy to develop a separation algorithm and thus a cutting plane
/// algorithm based on these (l,S)-inequalities.
/// </remarks>
class ELSManagedCuts
{
/** Tolerance for satisfiability. */
private const double EPS = 1e-6;
/** Number of time periods. */
private const int DIM_TIMES = 15;
/** Number of products to produce. */
private const int DIM_PRODUCTS = 4;
/** Demand per product (first dim) and time period (second dim). */
private static readonly int[,] DEMAND = new int[,]{
{ 2, 3, 5, 3, 4, 2, 5, 4, 1, 3, 4, 2, 3, 5, 2},
{3, 1, 2, 3, 5, 3, 1, 2, 3, 3, 4, 5, 1, 4, 1},
{3, 5, 2, 1, 2, 1, 3, 3, 5, 2, 2, 1, 3, 2, 3},
{2, 2, 1, 3, 2, 1, 2, 2, 3, 3, 2, 2, 3, 1, 2}
};
/** Setup cost. */
private static readonly double[] SETUPCOST = new double[]{
17, 14, 11, 6, 9, 6, 15, 10, 8, 7, 12, 9, 10, 8, 12
};
/** Production cost per product (first dim) and time period (second dim). */
private static readonly double[,] PRODCOST = new double[,]{
{5, 3, 2, 1, 3, 1, 4, 3, 2, 2, 3, 1, 2, 3, 2},
{1, 4, 2, 3, 1, 3, 1, 2, 3, 3, 3, 4, 4, 2, 2},
{3, 3, 3, 4, 4, 3, 3, 3, 2, 2, 1, 1, 3, 3, 3},
{2, 2, 2, 3, 3, 3, 4, 4, 4, 3, 3, 2, 2, 2, 3}
};
/** Capacity. */
private static int[] CAP = new int[]{
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12
};
/** Cut round callback for separating our cutting planes. */
class Callback
{
private Variable[,] produce;
private Variable[,] setup;
private double[,,] sumDemand;
public Callback(Variable[,] produce, Variable[,] setup, double[,,] sumDemand)
{
this.produce = produce;
this.setup = setup;
this.sumDemand = sumDemand;
}
public void CutRound(XpressProblem prob, int ifxpresscuts, ref int action)
{
// Apply only one round of cutting on each node.
// Because the CutRound callback is fired *before* a round of
// cutting, the CUTROUNDS attribute will start from 0 on the first
// invocation of the callback.
if (prob.CutRounds >= 1)
return;
// Get the solution vector.
// Xpress will only fire the CutRound callback when a solution is
// available, so there is no need to check whether a solution is
// available.
double[] sol = prob.GetCallbackSolution();
// Search for violated constraints : the minimum of the actual
// production produce[p,t] and the maximum potential production
// D[p,t,l]*setup[p,t] in periods 0 to l must at least equal
// the total demand in periods 0 to l.
// sum(t=1:l) min(prod[p,t], D[p,t,l]*setup[p,t]) >= D[p,0,l]
int nCutsAdded = 0;
for (int p = 0; p < DIM_PRODUCTS; p++)
{
for (int l = 0; l < DIM_TIMES; l++)
{
double sum = 0.0;
for (int t = 0; t <= l; t++)
{
if (produce[p, t].GetValue(sol) < sumDemand[p, t, l] * setup[p, t].GetValue(sol) + EPS)
{
sum += produce[p, t].GetValue(sol);
}
else
{
sum += sumDemand[p, t, l] * setup[p, t].GetValue(sol);
}
}
if (sum < sumDemand[p, 0, l] - EPS)
{
// Create the violated cut.
LinExpression cut = LinExpression.Create();
for (int t = 0; t <= l; t++)
{
if (produce[p, t].GetValue(sol) < sumDemand[p, t, l] * setup[p, t].GetValue(sol))
{
cut.AddTerm(1.0, produce[p, t]);
}
else
{
cut.AddTerm(sumDemand[p, t, l], setup[p, t]);
}
}
// Give the cut to Xpress to manage.
// It will automatically be presolved.
prob.AddManagedCut(true, cut >= sumDemand[p, 0, l]);
++nCutsAdded;
// If we modified the problem in the callback, Xpress
// will automatically trigger another roound of cuts,
// so there is no need to set the action return
// argument.
}
}
}
if (nCutsAdded > 0)
{
Console.WriteLine("Cuts added: {0}", nCutsAdded);
}
}
}
public static void Main(string[] args)
{
using (XpressProblem prob = new XpressProblem())
{
prob.callbacks.AddMessageCallback(DefaultMessageListener.Console);
// Create an economic lot sizing problem.
// Calculate demand D(p, s, t) as the demand for product p from
// time s to time t(inclusive).
double[,,] sumDemand = new double[DIM_PRODUCTS, DIM_TIMES, DIM_TIMES];
for (int p = 0; p < DIM_PRODUCTS; p++)
{
for (int s = 0; s < DIM_TIMES; s++)
{
double thisSumDemand = 0.0;
for (int t = s; t < DIM_TIMES; t++)
{
thisSumDemand += DEMAND[p, t];
sumDemand[p, s, t] = thisSumDemand;
}
}
}
Variable[,] produce = prob.AddVariables(DIM_PRODUCTS, DIM_TIMES)
.WithName((p, t) => "produce(" + p + "," + t + ")")
.ToArray();
Variable[,] setup = prob.AddVariables(DIM_PRODUCTS, DIM_TIMES)
.WithType(ColumnType.Binary)
.WithName((p, t) => "setup(" + p + "," + t + ")")
.ToArray();
// Add the objective function :
// MinCost:= sum(t in TIMES) (SETUPCOST(t) * sum(p in PRODUCTS) setup(p,t) +
// sum(p in PRODUCTS) PRODCOST(p, t) *produce(p, t) )
prob.SetObjective(Sum(DIM_TIMES, DIM_PRODUCTS,
(t, p) => SETUPCOST[t] * setup[p, t] + PRODCOST[p, t] * produce[p, t]));
// Add constraints.
// Production in periods 0 to t must satisfy the total demand
// during this period of time, for all t in [0,T[
// forall(p in PRODUCTS, t in TIMES)
// Dem(t) : = sum(s in 1..t) produce(p,s) >= sum(s in 1..t) DEMAND(s)
prob.AddConstraints(DIM_PRODUCTS, DIM_TIMES,
(p, t) => Sum(t + 1, s => produce[p, s]) >= sumDemand[p, 0, t]);
// If there is production during t then there is a setup in t :
// forall(p in PRODUCTS, t in TIMES)
// ProdSetup(t) : = produce(t) <= D(t,TIMES) * setup(t)
for (int p = 0; p < DIM_PRODUCTS; ++p)
{
for (int t = DIM_TIMES - 1; t >= 0; --t)
{
prob.AddConstraint(produce[p, t] <= sumDemand[p, t, DIM_TIMES - 1] * setup[p, t]);
}
}
// Capacity limits :
// forall(t in TIMES) Capacity(t) : = sum(p in PRODUCTS) produce(p, t) <= CAP(t)
prob.AddConstraints(DIM_TIMES,
t => Sum(DIM_PRODUCTS, p => produce[p, t]) <= CAP[t]);
// Add a CutRound callback for separating our cuts.
prob.callbacks.AddCutRoundCallback(new Callback(produce, setup, sumDemand).CutRound);
prob.WriteProb("elsmanagedcuts.lp");
prob.Optimize();
if (prob.SolveStatus == SolveStatus.Completed && prob.SolStatus == SolStatus.Optimal)
{
Console.WriteLine("Solved problem to optimality.");
}
else
{
Console.WriteLine("Failed to solve problem with solvestatus {0} and solstatus {1}",
prob.SolveStatus,
prob.SolStatus);
}
}
}
}
}
|
