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(](https://blog.adamfurmanek.pl/wp-content/ql-cache/quicklatex.com-acdadcffe5d3c8e1535cea5fa1fe3cd7_l3.png "Rendered by QuickLaTeX.com")
"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.
