This is the forty ninth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we solve the task B from Deadline24 2018 edition.

Sewage system
Introduction
Beetlejumpers are known throughout the Universum for their concern for the infrastructure and industrial
facilities of their worlds. The exceptional quality of solutions provided throughout the worlds is
due to the high-quality materials, as much as. . . to the extraordinary skills of Beetle-architects.
To become one of the famous Beetle-architects one has a long way to go. One of the first challenges
on this career path is the work on the less elegant, but no less important projects – such as planning
the sewage system layout.
Competence examination for 2nd degree Beetle-prearchitect includes, among others, the following
problem: Connect entrance connections with exit connections in a given area with the dimensions X * Y .
It is a typical examination problem, so there are numerous conditions simulating the real work:
- there is not much vertical space, so the pipes must not cross,
- due to optimization requirements the whole space must be covered with pipes,
- due to safety standards concerning pressure, each connection must be used only once.
Naturally, the area the examinee is working on is precisely defined, i.e., pipes cannot protrude beyond
the area.
Problem
An area with dimensions X * Y and the number of the necessary connections – N are known. Also
known is the set of start points with their corresponding end points (N pairs of coordinates).
The problem is to generate pipeline descriptions: each description must begin at one of start points
and finish at a corresponding end point. Each field of a given area must be used exactly once and all
pipelines must fit within the borders of the area.
Input data
Test sets are given in flow*.in files.
The first line of the test set includes one integer T denoting the number
of tests. Description of each test contains the definition of the area and connections
belonging to it.
The first line of the test description includes two natural numbers X
and Y that denote the dimensions of the area to be covered with pipes. The second
line includes a natural number N – the number of pipelines (connections)
to be built.
Each of the following N lines contains four natural numbers separated
by spaces – information concerning the pairs of connection points. The first
two numbers in each of those lines (x_s^i, y_s^i ) denote the pipeline start point coordinates.
The following two numbers in each of those lines (x_e^i, y_e^i ) are the endpoint coordinates of the same pipeline.
Each test has at least one correct solution.
1 <= T <= 10
5 <= X; Y <= 100
1 <= N <= 600
1 <= x_s^i, ; x_e^i <= X
1 <= y_s^i ; y_e^i <= Y
1 <= i <= N

Output data
As an answer to each test provide definitions of pipeline routes. Test answers must be provided in
the same sequence as in the input data file.

The first line of the test answer should contain N – the number of pipelines. The following N lines
should include sequences of characters Ck. Each character Ck can take one of the following values (the pair
(i; j) was adopted as current coordinates):
- ’N’ – for the move to j - 1 line (up),
- ’E’ – for the move to i + 1 field in the same line (to the right),
- ’S’ – for the move to j + 1 line (down),
- ’W’ – for the move to i - 1 field in the same line (to the left).
Each sequence corresponds to one pipeline and describes consecutive steps of moving around a given
area, beginning at start point and finishing at its corresponding end point (if a pipeline covers the area
of F fields, its description should consist of F - 1 characters). Pipelines should be presented in the same
sequence as their start and end points were provided in the input data file.
Example
For input data:
2
3 3
2
1 1 3 3
1 2 1 3
4 7
4
1 1 1 7
2 1 2 7
3 1 3 7
4 1 4 7
One of possible solutions is:
2
EESWSE
S
4
SSSSSS
SSSSSS
SSSSSS
SSSSSS

Idea is: for every field of the board we calculate available passes in all directions. Next, we assign height to a field and the pipe number. We make sure that if we pass in a direction then the pipe numbers are equal. Finally, height in end position is equal to one and can differ at most one when we pass through fields. We want to maximize the sum of weights for starting fields.

using CplexMilpManager.Implementation;
using MilpManager.Abstraction;
using MilpManager.Implementation;
using System;
using System.Collections.Generic;
using System.Linq;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            int tests = int.Parse(Console.ReadLine());

            for(int i = 0; i <  tests; ++i)
            {
                Solve();
            }
        }

        public static void Solve()
        {
            int[] nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            int width = nums[0];
            int height = nums[1];

            int pipes = int.Parse(Console.ReadLine());

            List< Tuple< int, int>> starts = new List< Tuple< int, int>>();
            List< Tuple< int, int>> ends = new List< Tuple< int, int>>();

            for (int i = 0; i <  pipes; ++i)
            {
                nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                starts.Add(Tuple.Create(nums[0] - 1, nums[1] - 1));
                ends.Add(Tuple.Create(nums[2] - 1, nums[3] - 1));
            }

            var solver = new CplexMilpSolver(25);

            IVariable inf = solver.FromConstant(1000000);


            IVariable[][] heights = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create("height_{x}_{y}", Domain.PositiveOrZeroInteger)).ToArray()).ToArray();             IVariable[][] ids = Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create("ids_{x}_{y}", Domain.PositiveOrZeroInteger)).ToArray()).ToArray();
            IVariable[][][] passes = Enumerable.Range(0, 4).Select(d => Enumerable.Range(0, width).Select(x => Enumerable.Range(0, height).Select(y => solver.Create($"pass_{d}_{x}_{y}", Domain.BinaryInteger)).ToArray()).ToArray()).ToArray();

            // Assignments
            for (int x = 0; x <  width; ++x)
            {
                for (int y = 0; y <  height; ++y)
                {
                    ids[x][y].Set(ConstraintType.GreaterOrEqual, solver.FromConstant(1)).Set(ConstraintType.LessOrEqual, solver.FromConstant(pipes));
                }
            }

            for(int pipe = 0; pipe <  pipes; ++pipe)
            {
                ids[starts[pipe].Item1][starts[pipe].Item2].Set(ConstraintType.Equal, solver.FromConstant(pipe + 1));
                ids[ends[pipe].Item1][ends[pipe].Item2].Set(ConstraintType.Equal, solver.FromConstant(pipe + 1));
            }

            // Ways out of a field
            for (int x = 0; x <  width; ++x)
            {
                for (int y = 0; y <  height; ++y)
                {
                    bool isStart = Enumerable.Range(0, pipes).Any(p => (starts[p].Item1 == x && starts[p].Item2 == y) || (ends[p].Item1 == x && ends[p].Item2 == y));
                    Enumerable.Range(0, 4).Select(p => passes[p][x][y]).Aggregate(solver.FromConstant(0), (prev, next) => prev.Operation(OperationType.Addition, next)).Set(ConstraintType.Equal, solver.FromConstant(isStart ? 1 : 2));
                }
            }

            // Edges
            for (int x = 0; x <  width; ++x)
            {
                for (int y = 0; y <  height; ++y)
                {
                    if(x == 0){
                        passes[1][x][y].Set(ConstraintType.Equal, solver.FromConstant(0));
                    }
                    if(x == width - 1)
                    {
                        passes[0][x][y].Set(ConstraintType.Equal, solver.FromConstant(0));
                    }
                    if(y == 0)
                    {
                        passes[3][x][y].Set(ConstraintType.Equal, solver.FromConstant(0));
                    }
                    if(y == height- 1)
                    {
                        passes[2][x][y].Set(ConstraintType.Equal, solver.FromConstant(0));
                    }
                }
            }

            // Set height for exit and enter
            for (int pipe = 0; pipe <  pipes; ++pipe)
            {
                heights[ends[pipe].Item1][ends[pipe].Item2].Set(ConstraintType.Equal, solver.FromConstant(1));
            }

            // Difference in heights
            for (int x = 0; x <  width; ++x)
            {
                for (int y = 0; y <  height; ++y)
                {
                    if (x <  width - 1)
                    {
                        var n = passes[0][x][y];
                        heights[x][y].Operation(OperationType.Subtraction, heights[x + 1][y]).Operation(OperationType.AbsoluteValue).Set(ConstraintType.LessOrEqual,
                            n.Operation(OperationType.Addition, n.Operation(OperationType.BinaryNegation).Operation(OperationType.Multiplication, inf))
                        );
                    }
                    if (y <  height - 1)
                    {
                        var n = passes[2][x][y];
                        heights[x][y].Operation(OperationType.Subtraction, heights[x][y + 1]).Operation(OperationType.AbsoluteValue).Set(ConstraintType.LessOrEqual,
                            n.Operation(OperationType.Addition, n.Operation(OperationType.BinaryNegation).Operation(OperationType.Multiplication, inf))
                        );
                    }
                }
            }

            // Consistent passes
            for (int x = 0; x <  width; ++x)
            {
                for (int y = 0; y <  height; ++y)
                {
                    if (x <  width - 1)
                    {
                        passes[0][x][y].Set(ConstraintType.Equal, passes[1][x + 1][y]);
                        passes[0][x][y].Set(ConstraintType.LessOrEqual, ids[x][y].Operation(OperationType.IsEqual, ids[x + 1][y]));
                    }
                    if (y <  height - 1)
                    {
                        passes[2][x][y].Set(ConstraintType.Equal, passes[3][x][y + 1]);
                        passes[2][x][y].Set(ConstraintType.LessOrEqual, ids[x][y].Operation(OperationType.IsEqual, ids[x][y + 1]));
                    }
                }
            }

            // Maximize heights for starts
            var goal = solver.FromConstant(0);
            for (int i = 0; i <  pipes; ++i)
            {
                goal = goal.Operation(OperationType.Addition, heights[starts[i].Item1][starts[i].Item2]);
            }

            solver.AddGoal("GOAL", goal);
            solver.SaveModelToFile("model.mps");

            solver.Solve();

            Console.WriteLine(solver.GetValue(goal));

            for (int y = 0; y <  height; ++y)
            {
                for (int x = 0; x <  width; ++x)
                {
                    Console.Write(solver.GetValue(heights[x][y]));
                    Console.Write("\t");
                }

                Console.WriteLine();
            }
            Console.WriteLine();

            for (int y = 0; y <  height; ++y)
            {
                for (int x = 0; x <  width; ++x)
                {
                    bool end = false;
                    for(int pipe = 0; pipe <  pipes; ++pipe)
                    {
                        if(starts[pipe].Item1 == x && starts[pipe].Item2 == y)
                        {
                            Console.Write(pipe + 1);
                            end = true;
                            break;
                        }
                        if (ends[pipe].Item1 == x && ends[pipe].Item2 == y)
                        {
                            Console.Write(pipe + 1);
                            end = true;
                            break;
                        }
                    }
                    if (end)
                    {
                        Console.Write("\t");
                        continue;
                    }

                    var right = solver.GetValue(passes[0][x][y]) > 0;
                    var left = solver.GetValue(passes[1][x][y]) > 0;
                    var up = solver.GetValue(passes[3][x][y]) > 0;
                    var down = solver.GetValue(passes[2][x][y]) > 0;

                    if (right && left)
                    {
                        Console.Write("—");
                    }
                    else if (right && up)
                    {
                        Console.Write("+");
                    }
                    else if (left && up)
                    {
                        Console.Write("+");
                    }
                    else if (up && down)
                    {
                        Console.Write("|");
                    }else if(right && down){
                        Console.Write("+");
                    }else if(left && down)
                    {
                        Console.Write("+");
                    }
                    else if(right || left)
                    {
                        Console.Write("-");
                    }
                    else
                    {
                        Console.Write("|");
                    }

                    Console.Write("\t");
                }

                Console.WriteLine();
            }
        }
    }
}

It works for small tests, for bigger ones (starting from set 3) even NEOS has problems.