Composite operations

List

Currently there are implemented the following composite operations:

• Unsigned magnitude decomposition
• N-th elements
• Selection sort
• Counting sort
• Loop
• Approximation
• Approximation 2D
• Is lexicographical greater or equal
• Is lexicographical greater than
• Is lexicographical less or equal
• Is lexicographical less than
• Is lexicographical equal
• Is lexicographical not equal
• Decomposition
• Array get
• Array set

---

Unsigned magnitude decomposition

Decomposes non-negative integers into its binary form

Usage

IMilpManager manager;
IVariable a;
...
IEnumerable<IVariable> decomposition = a.CompositeOperation(CompositeOperationType.UnsignedMagnitudeDecomposition);
or
IEnumerable<IVariable> decomposition = manager.CompositeOperation(CompositeOperationType.UnsignedMagnitudeDecomposition, a);

Details

Decomposes non-negative value into bits. For instance: 12 after decomposition is 1100. decomposition.First() is lowest bit (zero in this example). Result.Count() is equal to manager.IntegerWidth. Operation accepts exactly one argument, non-negative integer. It doesn't require additional parameters.

---

N-th elements

Selects N-th from a set

Usage

IMilpManager manager;
IVariable a;
IVariable b;
IVariable c;
IVariable index1;
IVariable index2;
NthElementsParameters parameters = new NthElementsParameters
{
    Indexes = new[] { index1, index2}
};
...
IEnumerable<IVariable> elements = a.CompositeOperation(CompositeOperationType.NthElements, parameters, b, c);
or
IEnumerable<IVariable> elements = manager.CompositeOperation(CompositeOperationType.NthElements, parameters, a, b, c);

Details

Returns elements with specified indexes as they would appear in a sorted set. Elements are numbered 0-base, lower index means lower element. For instance, assume that a = 7, b = 2, c = 4. Selecting index 0 gives variable b=2, since this would be variable with index 0 after sorting. Operation accepts only integers, requires additional parameter with specified indexes. Operation handles duplicated elements.

---

Selection sort

Sorts set using selection sort algorithm

Usage

IMilpManager manager;
IVariable a;
IVariable b;
IVariable c;
...
IEnumerable<IVariable> elements = a.CompositeOperation(CompositeOperationType.SelectionSort, b, c);
or
IEnumerable<IVariable> elements = manager.CompositeOperation(CompositeOperationType.SelectionSort, a, b, c);

Details

Sorts variables using selection sort algorithm. Accepts only integer variables, does not need additional parameters. Handles duplicated values. Elements are sorted in a non-decreasing order. Implemented as

manager.CompositeOperation(CompositeOperationType.NthElements, new NthElementsParameters {    
    Indexes = Enumerable.Range(0, variables.Lenth).ToArray() 
}, variables);

---

Counting sort

Sorts set using counting sort algorithm

Usage

IMilpManager manager;
IVariable a;
IVariable b;
IVariable c;
IVariable integerValueA;
IVariable integerValueB;
IVariable integerValueC;
CountingSortParameters parameters = new CountingSortParameters {Values = new[]{integerValueA, integerValueB, integerValueC}};
...
IEnumerable<IVariable> elements = a.CompositeOperation(CompositeOperationType.CountingSort, parameters, b, c);
or
IEnumerable<IVariable> elements = manager.CompositeOperation(CompositeOperationType.CountingSort, parameters, a, b, c);

Details

Sorts variables using counting sort algorithm. Accepts only integer variables, requires additional parameter specifying values which might occur in a set. Elements are sorted in a non-decreasing order. For instance: imagine that you want to sort variables and you know that all variables are less than ten, however, you do not know exact variables values. You should call the method in the following way:

IMilpManager manager;
IVariable a;
IVariable b;
IVariable c;
CountingSortParameters parameters = new CountingSortParameters {Values = new[]{1, 2, 3, 4, 5, 6, 7, 8, 9}};
...
IEnumerable<IVariable> elements = manager.CompositeOperation(CompositeOperationType.CountingSort, parameters, a, b, c);

This will sort the set assuming that all values are not less than one and not greater than nine.

---

Loop

Executes loop with up-front specified maximum number of iterations.

Usage

IMilpManager manager;
IVariable a;
IVariable b;
IVariable c;
LoopParameters parameters = new LoopParameters
{
    MaxIterations = iterationsCount,
    Body = new Func<IVariable, IVariable, IVariable, IVariable, IVariable[], IVariable>[]
    {
        (variable, counter, isLooping, totalBound, variables) => action
    },
	BeforeBody = new Action<IVariable, IVariable, IVariable, IVariable, IVariable[]>[]
	{
		(variable, counter, isLooping, totalBound, variables) => action
	},
	AfterBody = new Action<IVariable, IVariable, IVariable, IVariable, IVariable[]>[]
	{
		(variable, counter, isLooping, totalBound, variables) => action
	},
	BeforeLoopAction = (variable, variables) => action,
	AfterLoopAction = (variable, variables) => action,
	BeforeIterationAction = (counter, isLooping, totalBound, variables) => action,
	AfterIterationAction = (counter, isLooping, totalBound, variables) => action
};
...
IEnumerable<IVariable> argumentsAndCounter = a.CompositeOperation(CompositeOperationType.Loop, parameters, b, c);
or
IEnumerable<IVariable> argumentsAndCounter = manager.CompositeOperation(CompositeOperationType.CountingSort, parameters, a, b, c);

Details

Executes a loop with maximum specified number of iterations. Accepts any arguments as long as they conform to specified operations. Requires additional parameter with specified number of iterations and loop operations.

Every operation is specified as a Func<IVariable, IVariable, IVariable, IVariable, IVariable[], IVariable>. First argument is a variable representing currently modified variable. Second arguments is a variable current iteration number. Third argument is a variable representing condition whether the loop is still going on. Fourth argument is a variable representing total number of iterations performed by the loop. Fifth argument is an array of current values of parameters. N-th operation acts on N-th variable and needs to return its new value after iteration.

Loop is allowed to run at most specified number of iterations, however, it might run less iterations if it gives better solution.

Result is a collection of arguments and one more variable at the end, representing the loop counter.

You can also specify BeforeBody and AfterBody callbacks which will run before and after performing operation on a variable in each iteration. Every callback is specified as an Action<IVariable, IVariable, IVariable, IVariable, IVariable, IVariable[]>, where arguments are just like for operation callbacks.

You can also specify BeforeIterationAction and AfterIterationAction which will run before and after each iteration. Every callback is specified as an Action<IVariable, IVariable, IVariable, IVariable[]>, where first argument is a variable representing current iteration number. Second argument is a variable representing condition whether the loop is still going on. Third argument is a variable representing total number of iterations performed by the loop. Fourth argument is an array of current values of parameters.

You can also specify BeforeLoopAction and AfterLoopAction which will run before loop and after loop. Every callback is specified as an Action<IVariable, IVariable[]>. First argument is a variable representing total number of iterations performed by the loop. Second argument is an array of current values of parameters.

Example: Finding closes sum of consecutive integers

We want to sum consecutive integer 1+2+...+n and find the sum which is as close to 19 as possible. We allow at most 10 iterations (so the total sum will not exceed 1+2+...+10). The following code represents the solution:

IMilpManager manager;
// At start our sum is equal to zero
IVariable sum = manager.FromConstant(0);

IEnumerable<IVariable> results = manager.CompositeOperation(CompositeOperationType.Loop, new LoopParameters
{
    // We execute at most 10 iterations
    MaxIterations = 10,
    Body = new Func<IVariable, IVariable[], IVariable>[]
    {
        // We have exactly one operation since we pass exactly one variable
        // `counter` represents looping variable, it will have consecutive values (`1, 2, ...`)
        // `vars` represents state of variables, in our example this is exactly one variable representing state of variable `sum` in this iteration
        // We need to return new value of `sum`, we simply add it to `counter`
        (counter, vars) => vars[0].Operation(OperationType.Addition, counter)
    }
}, sum);

// `results` contains two variables: `[sum, counter]`
sum = results.First();

// Now `sum` has a value after the loop
// We calculate the difference
IVariable difference = manager.Operation(OperationType.AbsoluteValue, sum.Operation(OperationType.Subtraction, manager.FromConstant(19)));

// Now let's optimize our program, we want to minimize the difference
manager.AddGoal("goal", difference.Operation(OperationType.Negation));
manager.Solve();

// After solving the problem we should end up with the following values:
// counter = 6
// sum = 21
// difference = 2

You might write this program in C++ as:
int sum = 0;
int difference = 19;
int counter = 0;
while(counter <= 10){
    int newSum = sum + counter + 1;
    if(abs(19 - newSum) < difference ){
        counter++;
        sum = newSum;
        difference = abs(19-sum);
    }else{
        break;
    }
}

Example: Modifying integers as long as they are not equal

We have two variables. First one goes down from 18 with 2*counter in each step, second one goes up from 0 with counter in each step. We want to loop as long as two variables are different.

IMilpManager manager;
// First variable (going down)
IVariable decreasing = manager.FromConstant(18);
// Second variable (going up)
IVariable increasing = manager.FromConstant(0);
// Multiplier in every set
IVariable two = manager.FromConstant(2);

IVariable[] results = manager.CompositeOperation(CompositeOperationType.Loop, new LoopParameters
{
    // We have at most 10 iterations
    MaxIterations = 10,
    Body = new Func<IVariable, IVariable[], IVariable>[]
    {
        // We have two operations since we pass two arguments
        // First operation subtracts `2*counter` from the first variable
        (counter, vars) => vars[0].Operation(OperationType.Subtraction, counter.Operation(OperationType.Multiplication, two)),
        // Second operation adds `counter` to the second variable
        (counter, vars) => vars[1].Operation(OperationType.Addition, counter)
    }
}, decreasing, increasing).ToArray();

// After the loop `results` is `[decreasing, increasing, counter]`
// We extract our variables
decreasing = results[0];
increasing = results[1];

// Now we want to make sure that they meet somewhere in between
IVariable areEqual = decreasing.Operation(OperationType.IsEqual, increasing).Set(ConstraintType.Equal, manager.FromConstant(1));

// If you would try to solve the problem, the loop would take as many steps as it is required (but no more than 10) to make `increasing == decreasing`
// In our example it would be:
// counter = 3
// increasing = 6 (1 + 2 + 3)
// decreasing = 6 (18 - 2 - 4 - 6)

C++ code:
int decreasing = 18;
int increasing = 0;
for(int i=0;i<=10;++i){
    decreasing -= 2*i;
    increasing += i;
    if(decreasing == increasing){
        break;
    }
}

---

Approximation

Approximates function using linear functions in the given points

Usage

IMilpManager manager;
IVariable x;
...
IEnumerable<IVariable> y = a.CompositeOperation(CompositeOperationType.Approximation, new ApproximateParameters{
	Function = argument => 2 - argument*argument,
	FunctionDescription = "2-x^2",
	Arguments = new []{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}
});
or
IEnumerable<IVariable> y = manager.CompositeOperation(CompositeOperationType.Approximation, new ApproximateParameters{
	Function = argument => 2 - argument*argument,
	FunctionDescription = "2-x^2",
	Arguments = new []{0.0, 0.3, 0.6, 1.0}
}, x);

Details

First, for every given argument a function value is calculated. Next, for every consecutive pair of arguments a linear function is calculated and constraints are added so the given variable will have value matching on of these segments. Finally, variable representing function value is returned. Example: snippet above approximates function f(x)=2-x^2 in the range [0; 1] using four points: 0.0, 0.3, 0.6, 1.0. First, values in these points are calculated:

• f(0.0) = 2 - 0^2 = 2
• f(0.3) = 2 - 0.3^2 = 1.991
• f(0.6) = 2 - 0.6^2 = 1.64
• f(1.0) = 2 - 1^2 = 1 Next, linear functions are calculated. First segment's ends are (0.0; 0.0) and (0.3; 1.991). Second segment's ends are (0.3; 1.991) and (0.6; 1.64). Third segment's ends are (0.6; 1.64) and (1.0; 1.0). Finally, constraints are added so variable x passed to calculator will be in range [0.0; 1.0]. Returned variable will take value approximating 2-x^2 for variable x from one of three segments.

Accepts optional flag to restrict argument to obtain one of passed argument values.

---

Approximation 2D

Approximates two-dimensional function using linear functions in the given points

Usage

IMilpManager manager;
IVariable x;
IVariable y;
...
IEnumerable<IVariable> z = a.CompositeOperation(CompositeOperationType.Approximation2D, new Approximate2DParameters{
	Function = (x, y) => 2 - x*x - y*y,
	FunctionDescription = "2-x^2-y^2",
	ArgumentsX = new []{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0},
	ArgumentsY = new []{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}
}, y);
or
IEnumerable<IVariable> y = manager.CompositeOperation(CompositeOperation2DType.Approximation, new Approximate2DParameters{
	Function = (x, y) => 2 - x*x - y*y,
	FunctionDescription = "2-x^2-y^2",
	ArgumentsX = new []{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0},
	ArgumentsY = new []{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}
}, x, y);

Details

Works like Approximation but for two-dimensional functions. Accepts optional flag to restrict argument to obtain one of passed argument values.

---

Is lexicographical greater or equal

Answers whether one Sequence of variables is lexicographical greater or equal to the other one.

Usage

IMilpManager manager;
IVariable x0, x1, x2;
IVariable y0, y1, y2;
...
IVariable[] result = solver.CompositeOperation(
	CompositeOperationType.IsLexicographicalGreaterOrEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x0, x1, x2 }
);
or
IVariable[] result = x0.CompositeOperation(
	CompositeOperationType.IsLexicographicalGreaterOrEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x1, x2 }
);

Details

Performs lexicographical comparison. Sequence is lexicographical greater or equal to the other one if they are equal or there exists j for which for all i < j element x_i is equal to y_i, and x_j > y_j;

---

Is lexicographical greater than

Answers whether one Sequence of variables is lexicographical greater than the other one.

Usage

IMilpManager manager;
IVariable x0, x1, x2;
IVariable y0, y1, y2;
...
IVariable[] result = solver.CompositeOperation(
	CompositeOperationType.IsLexicographicalGreaterThan, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x0, x1, x2 }
);
or
IVariable[] result = x0.CompositeOperation(
	CompositeOperationType.IsLexicographicalGreaterThan, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x1, x2 }
);

Details

Performs lexicographical comparison. Sequence is lexicographical greater than the other one if there exists j for which for all i < j element x_i is equal to y_i, and x_j > y_j;

---

Is lexicographical less than

Answers whether one Sequence of variables is lexicographical less than the other one.

Usage

IMilpManager manager;
IVariable x0, x1, x2;
IVariable y0, y1, y2;
...
IVariable[] result = solver.CompositeOperation(
	CompositeOperationType.IsLexicographicalLessThan, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x0, x1, x2 }
);
or
IVariable[] result = x0.CompositeOperation(
	CompositeOperationType.IsLexicographicalLessThan, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x1, x2 }
);

Details

Performs lexicographical comparison. Sequence is lexicographical less than the other one if there exists j for which for all i < j element x_i is equal to y_i, and x_j < y_j;

---

Is lexicographical less or equal

Answers whether one Sequence of variables is lexicographical less or equal to the other one.

Usage

IMilpManager manager;
IVariable x0, x1, x2;
IVariable y0, y1, y2;
...
IVariable[] result = solver.CompositeOperation(
	CompositeOperationType.IsLexicographicalLessOrEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x0, x1, x2 }
);
or
IVariable[] result = x0.CompositeOperation(
	CompositeOperationType.IsLexicographicalLessOrEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x1, x2 }
);

Details

Performs lexicographical comparison. Sequence is lexicographical less or equal to the other one if they are equal or there exists j for which for all i < j element x_i is equal to y_i, and x_j < y_j;

---

Is lexicographical equal

Answers whether one Sequence of variables is lexicographical equal to the other one.

Usage

IMilpManager manager;
IVariable x0, x1, x2;
IVariable y0, y1, y2;
...
IVariable[] result = solver.CompositeOperation(
	CompositeOperationType.IsLexicographicalEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x0, x1, x2 }
);
or
IVariable[] result = x0.CompositeOperation(
	CompositeOperationType.IsLexicographicalEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x1, x2 }
);

Details

Performs lexicographical comparison. Sequence is lexicographical equal to the other one if they are equal.

---

Is lexicographical not equal

Answers whether one Sequence of variables is lexicographical not equal to the other one.

Usage

IMilpManager manager;
IVariable x0, x1, x2;
IVariable y0, y1, y2;
...
IVariable[] result = solver.CompositeOperation(
	CompositeOperationType.IsLexicographicalNotEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x0, x1, x2 }
);
or
IVariable[] result = x0.CompositeOperation(
	CompositeOperationType.IsLexicographicalNotEqual, 
	new LexicographicalCompareParameters
	{
		Pattern = new[] { y0, y1, y2 }
	}, 
	new[] { x1, x2 }
);

Details

Performs lexicographical comparison. Sequence is lexicographical not equal to theother one if they are not equal.

---

Decomposition

Decomposes non-negative integers into its form in specified base

Usage

IMilpManager manager;
IVariable a;
...
IEnumerable<IVariable> decomposition = a.CompositeOperation(CompositeOperationType.Decomposition, new DecompositionParameters { Base = 3});
or
IEnumerable<IVariable> decomposition = manager.CompositeOperation(CompositeOperationType.Decomposition, new DecompositionParameters { Base = 3}, a);

Details

Decomposes non-negative value into digits in specified base. decomposition.First() is lowest digit. Operation accepts exactly one argument, non-negative integer. It requires additional parameter with specified base.

---

Array get

Gets element from an array

Usage

IMilpManager manager;
IVariable index;
IVariable element1;
IVariable element2;
IVariable element3;
...
IEnumerable<IVariable> element = element1.CompositeOperation(CompositeOperationType.ArrayGet, new ArrayGetParameters
            {
                Index = index
            }, element2, element3)
or
IEnumerable<IVariable> decomposition = manager.CompositeOperation(CompositeOperationType.ArrayGet, new ArrayGetParameters
            {
                Index = index
            }, element1, element2, element3)

Details

Returns exactly one element, and element from an array from specified index.

---

Array set

Sets element in an array

Usage

IMilpManager manager;
IVariable index;
IVariable value;
IVariable element1;
IVariable element2;
IVariable element3;
...
IEnumerable<IVariable> element = element1.CompositeOperation(CompositeOperationType.ArraySet, new ArraySetParameters
            {
                Index = index,
                Value = value
            }, element2, element3)
or
IEnumerable<IVariable> decomposition = manager.CompositeOperation(CompositeOperationType.ArraySet, new ArraySetParameters
            {
                Index = index,
                Value = value
            }, element1, element2, element3)

Details

Sets element in an array at specified index. Returns new array.

---