LinkedIn Games Python Package

The LinkedIn Games is a Python Package designed to solve the LinkedIn mini games by using Linear Optimization models and it will be the library to be used along this book.

Dependencies¶

The Linkedin Games package has the following Python dependencies to model, solve and visualize the optimization problems:

Pyomo: A powerful and flexible optimization modeling language that allows users to define optimization problems in a clear and concise way. Pyomo supports a wide range of optimization problem types, including linear, integer, and nonlinear programming, and can interface with various solvers.
NetworkX: A library for the creation, manipulation, and study of complex networks. It provides tools for working with graphs and networks, which can be useful for modeling and solving optimization problems that involve network structures.
Matplotlib: A plotting library for Python that provides a wide range of tools for creating static, animated, and interactive visualizations. It can be used to visualize optimization results, such as the feasible region, the objective function landscape, or the solution itself.

With this three libraries, it’s able to model, solve and visualize the optimization problems we will encounter in this book. But...

How to install¶

To install the LinkedIn Games package, you can use the traditional pip command:

pip install linkedin-games

Or run the command below if you use uv as your package manager:

uv add linkedin-games

Abstract Base Classes¶

In order to understand how Pyomo work to build and solve the model before displaying the solution with NetworkX, it will be useful to check out the implementation of some Abstract Base Classes, which share methods and attributes with many other classes.

Abstract Base Class

An abstract base class (ABC) is a class that cannot be instantiated and is designed to be subclassed. It can define abstract methods that must be implemented by its subclasses, providing a common interface for a group of related classes. It only makes sense to use an ABC if you have a set of classes that share some common behavior or attributes, and you want to enforce that certain methods are implemented in those subclasses by using the @abstractmethod decorator.

from abc import ABC, abstractmethod


class Quadrilateral(ABC):
    @abstractmethod
    def area(self):
        pass

    @abstractmethod
    def perimeter(self):
        pass


class Rectangle(Quadrilateral):
    def __init__(self, length, width):
        self.length = length
        self.width = width

    def area(self):
        return self.length * self.width

    def perimeter(self):
        return 2 * (self.length + self.width)


class Square(Quadrilateral):
    def __init__(self, side_length):
        self.side_length = side_length

    def area(self):
        return self.side_length ** 2
    
    def perimeter(self):
        return 4 * self.side_length


class Diamond(Quadrilateral):
    def __init__(self, diagonal1, diagonal2):
        self.diagonal1 = diagonal1
        self.diagonal2 = diagonal2

    def area(self):
        return (self.diagonal1 * self.diagonal2) / 2

    def perimeter(self):
        side_length = ((self.diagonal1 / 2) ** 2 + (self.diagonal2 / 2) ** 2) ** 0.5
        return 4 * side_length


class Trapeze(Quadrilateral):
    def __init__(self, base1, base2, height):
        self.base1 = base1
        self.base2 = base2
        self.height = height

    def area(self):
        return (self.base1 + self.base2) * self.height / 2

    def perimeter(self):
        # For a trapeze, we need the lengths of the non-parallel sides.
        # Assuming it's an isosceles trapezoid for simplicity.
        side_length = ((self.base2 - self.base1) / 2) ** 2 + self.height ** 2
        side_length = side_length ** 0.5
        return self.base1 + self.base2 + 2 * side_length

`GameModeler`¶

The GameModeler is a builder pattern that sets the Pyomo ConcreteModel’s components of a game. This base class creates the basic components shared with all games, such as:

Board dimension parameters m and n: The total number of rows and columns on game’s board.
Range sets I and J: The ranges of rows and columns, respectively.
Set S: The set of all squares on game board, which is a cartesian product between ranges I and J.

opt_modeler.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from abc import ABC, abstractmethod

import pyomo.environ as pyo

from ...domain.game_grid import GameGrid


class OptModeler[G: GameGrid](ABC):

    def __init__(self) -> None:
        self.reset()

    def reset(self) -> None:
        self._game: G
        self._model = pyo.ConcreteModel()

    def _set_board_dimensions(self) -> None:
        m, n = self._game.dims
        self._model.m = pyo.Param(initialize=m, domain=pyo.PositiveIntegers)
        self._model.n = pyo.Param(initialize=n, domain=pyo.PositiveIntegers)

    @abstractmethod
    def _set_range_sets(self) -> None:
        self._model.I = pyo.RangeSet(self._model.m) # Rows
        self._model.J = pyo.RangeSet(self._model.n) # Columns

    @abstractmethod
    def _set_composite_sets(self) -> None:
        self._model.S = pyo.Set( # Grid Squares
            initialize=lambda model: [(i,j) for i in model.I for j in model.J]
        )

    @abstractmethod
    def _set_parameters(self) -> None:
        ...

    @abstractmethod
    def _set_decision_variables(self) -> None:
        ...

    def _set_objective_function(self) -> None:
        self._model.obj = pyo.Objective(expr=0) # feasibility problem

    @abstractmethod
    def _set_constraints(self) -> None:
        ...

    def build_model(self, game: G) -> pyo.ConcreteModel:
        self._game = game
        self._set_board_dimensions()
        self._set_range_sets()
        self._set_composite_sets()
        self._set_parameters()
        self._set_decision_variables()
        self._set_objective_function()
        self._set_constraints()
        model = self._model
        self.reset()
        return model

Program 1:The game modeler’s base class

Feasibility Problem

When a optimization problem actually doesn’t have any function to maximize or minimize, it is called a feasibility problem, since the objective is not to find an optimal solution, but a feasible one that satisfies all model’s constraints. To formulate a feasibility problem, the objective function is defined as to maximize (or minimize, it doesn’t matter in this case) an arbitrary constant $C$ (personally, I prefer to set $C=0$ to indicate the objective function is turned off).

\text{Max} \quad C \iff \text{Min} \quad C

As you will see further, all the LinkedIn mini games are formulated as feasibility problems, since the goal is to find a solution that satisfies all the rules of the game, rather than optimizing a specific objective function. This is implemented in the GameModeler class, which sets the objective function to maximize zero.

opt_modeler.py

1
2
    def _set_objective_function(self) -> None:
        self._model.obj = pyo.Objective(expr=0) # feasibility problem

Program 2:The game modeler’s objective function sets the game’s model as a feasibility problem.

`GameRenderer`¶

The GameRenderer is plays the role to display the game’s board by using the NetworkX, to build the graph structure, and Matplotlib, to plot the board as a chart.

renderer.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from abc import ABC, abstractmethod

import networkx as nx

from ...domain.game_grid import GameGrid


class GameRenderer[G: GameGrid](ABC):
    _SCALE_FACTOR = .5

    def __init__(self, game: G) -> None:
        self._game = game
        m, n = game.dims
        self._height = m * self._SCALE_FACTOR
        self._width = n * self._SCALE_FACTOR
        self._set_grid()

    @abstractmethod
    def _set_grid(self) -> None:
        self._grid = nx.grid_2d_graph(*self._game.dims).to_directed()
        nx.set_node_attributes(self._grid, name="value",
            values={(i-1, j-1): k for (i, j), k in self._game.squares.items()}
        )

    @abstractmethod
    def display(self) -> None:
        ...

Program 3:The game renderer’s base class

Dependencies¶

How to install¶

Abstract Base Classes¶

GameModeler¶

GameRenderer¶

`GameModeler`¶

`GameRenderer`¶