The ILP Manager class

ILP Formulation

This class models Euler’s 185th riddle with the following Integer Linear Problem:

Let be binary variables indicating the color of the digits in , that is: .

Since each vertex in has only one color, we get the constraints:

And from the input of correct vertices we get the constraints:

Since we are guarantied that only one solution exists, we can put a dummy objective function of our choice, and solve the ILP to get the unique solution.

Class API

class src.ilp_manager.ILPManager(m)

Model the 185th problem in Project Euler as an ILP (Integer Linear Program)

To instantiate this module, please specify the length on sequences.

build_ilp_solver(sequences_list, n_correct_vertices_list)

Given input sequences, and number or correct vertices in each of them, build an ILP representation of the problem.

Parameters:

• sequences_list – List of sequences, each of length self.m, of integers between 0 and 9.
• n_correct_vertices_list – Number of correct vertices in each sequence in sequences_list. A vertex is correct if its color is equal to the color of the corresponding vertex in the solution s_star.

Returns:

tuple, containing:

• ilp_solver: Pulp instance, holding all the information needed for the solution.
• s_star_to_color_edges: The edges (variables) in the ilp_solver.

solve_ilp(ilp_solver, s_star_to_color_edges)

Given a solver with the needed information, solve the ILP and extract the solution to problem 185.

Parameters:

• ilp_solver – Pulp instance, holding all the information needed for the solution.
• s_star_to_color_edges – The edges (variables) in the ilp_solver.

Returns:

s_star: List of integers that is the solution to problem 185.

This page was generated using this .rst code:

The ILP Manager class
=====================
|
|


ILP Formulation
***************
|

This class models Euler's 185th riddle with the following Integer Linear Problem:

 Let :math:`\left\{ x_{i,c}\right\} _{i\in[m],c\in[10]}` be binary variables indicating \
 the color of the digits in :math:`s^{*}`, that is: \
 :math:`x_{j,c}=1\thinspace\thinspace\iff\thinspace\thinspace v_{j}^{*}=c`.

 Since each vertex in :math:`s^{*}` has only one color, we get the constraints: \
 :math:`\left\{ \sum_{c=0}^{9}x_{j,c}=1\right\} _{j\in[m]}`

 And from the input of correct vertices we get the constraints: \
 :math:`\left\{ \sum_{j\in[m]}x_{j,v_{j}^{\left(i\right)}}=d^{\left(i\right)}\right\} _{i\in[n]}`

 Since we are guarantied that only one solution exists, we can put a dummy objective function of our choice, \
 and solve the ILP to get the unique solution.

|

Class API
#########

.. Notice the markers line is longer than the headline.
.. It is allowed. but markers lines shorter than headlines are not allowed.
..
   Notice further: each time you change the type of heading marker
   (here we started with =, then * then #)
   The heading level drops (heading 1 => heading 2 => etc.)

|

.. autoclass:: src.ilp_manager.ILPManager

|
|

This page was generated using this .rst code:
*********************************************

|

.. literalinclude:: ilp_manager.rst

|
|

:ref:`Return Home <mastertoc>`

Return Home