Optimal Wedding Seating

Model

import sasoptpy as so
import math


def test(cas_conn, num_guests=20, max_table_size=3, max_tables=None):

    m = so.Model("wedding", session=cas_conn)

    # Check max. tables
    if max_tables is None:
        max_tables = math.ceil(num_guests/max_table_size)

    # Sets
    guests = range(1, num_guests+1)
    tables = range(1, max_tables+1)
    guest_pairs = [[i, j] for i in guests for j in range(i+1, num_guests+1)]

    # Variables
    x = m.add_variables(guests, tables, vartype=so.BIN, name="x")
    unhappy = m.add_variables(tables, name="unhappy", lb=0)

    # Objective
    m.set_objective(unhappy.sum('*'), sense=so.MIN, name="obj")

    # Constraints
    m.add_constraints((x.sum(g, '*') == 1 for g in guests), name="assigncon")
    m.add_constraints((x.sum('*', t) <= max_table_size for t in tables),
                      name="tablesizecon")
    m.add_constraints((unhappy[t] >= abs(g-h)*(x[g, t] + x[h, t] - 1)
                       for t in tables for [g, h] in guest_pairs),
                      name="measurecon")

    # Solve
    res = m.solve(options={
        'with': 'milp', 'decomp': {'method': 'set'}, 'presolver': 'none'})

    if res is not None:

        print(so.get_solution_table(x))

        # Print assignments
        for t in tables:
            print('Table {} : [ '.format(t), end='')
            for g in guests:
                if x[g, t].get_value() == 1:
                    print('{} '.format(g), end='')
            print(']')

    return m.get_objective_value()

Output

In [1]: import os

In [2]: hostname = os.getenv('CASHOST')

In [3]: port = os.getenv('CASPORT')

In [4]: from swat import CAS

In [5]: cas_conn = CAS(hostname, port)

In [6]: import sasoptpy

In [7]: from examples.client_side.sas_optimal_wedding import test

In [8]: test(cas_conn)
NOTE: Initialized model wedding.
NOTE: Added action set 'optimization'.
NOTE: Converting model wedding to DataFrame.
NOTE: Uploading the problem DataFrame to the server.
NOTE: Cloud Analytic Services made the uploaded file available as table TMP7CRMKE11 in caslib CASUSER(casuser).
NOTE: The table TMP7CRMKE11 has been created in caslib CASUSER(casuser) from binary data uploaded to Cloud Analytic Services.
NOTE: The problem wedding has 147 variables (140 binary, 0 integer, 0 free, 0 fixed).
NOTE: The problem has 1357 constraints (7 LE, 20 EQ, 1330 GE, 0 range).
NOTE: The problem has 4270 constraint coefficients.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value NONE is applied.
NOTE: The MILP solver is called.
NOTE: The Decomposition algorithm is used.
NOTE: The Decomposition algorithm is executing in the distributed computing environment in single-machine mode.
NOTE: The DECOMP method value SET is applied.
NOTE: All blocks are identical and the master model is set partitioning.
NOTE: The Decomposition algorithm is using an aggregate formulation and Ryan-Foster branching.
NOTE: The number of block threads has been reduced to 1 threads.
NOTE: The problem has a decomposable structure with 7 blocks. The largest block covers 14.08% of the constraints in the problem.
NOTE: The decomposition subproblems cover 147 (100%) variables and 1337 (98.53%) constraints.
NOTE: The deterministic parallel mode is enabled.
NOTE: The Decomposition algorithm is using up to 8 threads.
         Iter         Best       Master         Best       LP       IP  CPU Real
                     Bound    Objective      Integer      Gap      Gap Time Time
            .       0.0000      13.0000      13.0000 1.30e+01 1.30e+01    0    0
            1       0.0000      13.0000      13.0000 1.30e+01 1.30e+01    0    0
            .       0.0000      13.0000      13.0000 1.30e+01 1.30e+01    1    2
           10       0.0000      13.0000      13.0000 1.30e+01 1.30e+01    1    2
           18       4.2500      13.0000      13.0000  205.88%  205.88%    5    7
           19       6.0000      13.0000      13.0000  116.67%  116.67%    6    7
            .       6.0000      13.0000      13.0000  116.67%  116.67%    6    7
           20       6.0000      13.0000      13.0000  116.67%  116.67%    6    7
           21       9.5000      13.0000      13.0000   36.84%   36.84%    6    8
           23      13.0000      13.0000      13.0000    0.00%    0.00%    7    8
            Node  Active   Sols         Best         Best      Gap    CPU   Real
                                     Integer        Bound            Time   Time
               0       1      3      13.0000      13.0000    0.00%      7      8
NOTE: The Decomposition algorithm used 8 threads.
NOTE: The Decomposition algorithm time is 8.82 seconds.
NOTE: Optimal.
NOTE: Objective = 13.
           x
(1, 1)   1.0
(1, 2)   0.0
(1, 3)   0.0
(1, 4)   0.0
(1, 5)   0.0
(1, 6)   0.0
(1, 7)   0.0
(2, 1)   1.0
(2, 2)   0.0
(2, 3)   0.0
(2, 4)   0.0
(2, 5)   0.0
(2, 6)   0.0
(2, 7)   0.0
(3, 1)   1.0
(3, 2)   0.0
(3, 3)   0.0
(3, 4)   0.0
(3, 5)   0.0
(3, 6)   0.0
(3, 7)   0.0
(4, 1)   0.0
(4, 2)   1.0
(4, 3)   0.0
(4, 4)   0.0
(4, 5)   0.0
(4, 6)   0.0
(4, 7)   0.0
(5, 1)   0.0
(5, 2)   1.0
(5, 3)   0.0
(5, 4)   0.0
(5, 5)   0.0
(5, 6)   0.0
(5, 7)   0.0
(6, 1)   0.0
(6, 2)   1.0
(6, 3)   0.0
(6, 4)   0.0
(6, 5)   0.0
(6, 6)   0.0
(6, 7)   0.0
(7, 1)   0.0
(7, 2)   0.0
(7, 3)   1.0
(7, 4)   0.0
(7, 5)   0.0
(7, 6)   0.0
(7, 7)   0.0
(8, 1)   0.0
(8, 2)   0.0
(8, 3)   1.0
(8, 4)   0.0
(8, 5)   0.0
(8, 6)   0.0
(8, 7)   0.0
(9, 1)   0.0
(9, 2)   0.0
(9, 3)   1.0
(9, 4)   0.0
(9, 5)   0.0
(9, 6)   0.0
(9, 7)   0.0
(10, 1)  0.0
(10, 2)  0.0
(10, 3)  0.0
(10, 4)  1.0
(10, 5)  0.0
(10, 6)  0.0
(10, 7)  0.0
(11, 1)  0.0
(11, 2)  0.0
(11, 3)  0.0
(11, 4)  1.0
(11, 5)  0.0
(11, 6)  0.0
(11, 7)  0.0
(12, 1)  0.0
(12, 2)  0.0
(12, 3)  0.0
(12, 4)  1.0
(12, 5)  0.0
(12, 6)  0.0
(12, 7)  0.0
(13, 1)  0.0
(13, 2)  0.0
(13, 3)  0.0
(13, 4)  0.0
(13, 5)  1.0
(13, 6)  0.0
(13, 7)  0.0
(14, 1)  0.0
(14, 2)  0.0
(14, 3)  0.0
(14, 4)  0.0
(14, 5)  1.0
(14, 6)  0.0
(14, 7)  0.0
(15, 1)  0.0
(15, 2)  0.0
(15, 3)  0.0
(15, 4)  0.0
(15, 5)  1.0
(15, 6)  0.0
(15, 7)  0.0
(16, 1)  0.0
(16, 2)  0.0
(16, 3)  0.0
(16, 4)  0.0
(16, 5)  0.0
(16, 6)  1.0
(16, 7)  0.0
(17, 1)  0.0
(17, 2)  0.0
(17, 3)  0.0
(17, 4)  0.0
(17, 5)  0.0
(17, 6)  1.0
(17, 7)  0.0
(18, 1)  0.0
(18, 2)  0.0
(18, 3)  0.0
(18, 4)  0.0
(18, 5)  0.0
(18, 6)  1.0
(18, 7)  0.0
(19, 1)  0.0
(19, 2)  0.0
(19, 3)  0.0
(19, 4)  0.0
(19, 5)  0.0
(19, 6)  0.0
(19, 7)  1.0
(20, 1)  0.0
(20, 2)  0.0
(20, 3)  0.0
(20, 4)  0.0
(20, 5)  0.0
(20, 6)  0.0
(20, 7)  1.0
Table 1 : [ 1 2 3 ]
Table 2 : [ 4 5 6 ]
Table 3 : [ 7 8 9 ]
Table 4 : [ 10 11 12 ]
Table 5 : [ 13 14 15 ]
Table 6 : [ 16 17 18 ]
Table 7 : [ 19 20 ]
Out[8]: 13.0