ILP Part 49 — Deadline24 2018 – Flow

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

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:

3 3

1 1 3 3

1 2 1 3

4 7

1 1 1 7

2 1 2 7

3 1 3 7

4 1 4 7

One of possible solutions is:

EESWSE

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();
            }
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

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.

ILP Part 49 — Deadline24 2018 – Flow

Recent Posts

Categories

Archive

Posts