COCOMA/mipsolving.py at master · eusip/COCOMA · GitHub

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
# -*- coding: utf-8 -*-
"""
Created on Tue Jul 12 23:25:48 2016

@author: nicolas
"""

import pulp
import math
import numpy as np
from problem import Problem

#TODO: introduce parameter to specify whether the allocation must be modified

###############################################################################
# The Assignment LP
###############################################################################


def assignmentLP(p,verbose=False):

    agents = list(range(1,p.n)) # agent 0 is the auctioneer
    resources = list(range(0,p.m))


    # building the pulp model

    assignLP = pulp.LpProblem("Assignment LP",pulp.LpMaximize)

    # creating the variables

    x = pulp.LpVariable.dicts("assignement", (agents, resources),cat = pulp.LpBinary)
    k = pulp.LpVariable("bound", lowBound = 0)


    # objective function: maximize k

    assignLP += k

    # each resource assigned to one agent
    for j in resources:
        assignLP += sum([x[i][j] for i in agents])==1

    # utility of each agent must be higher than k
    for i in agents:
        assignLP += sum([p.agent[i].u["r"+str(j)]*x[i][j] for j in resources])>=k


    # solving and printing

    assignLP.solve()
    if verbose:
        for i in agents:
            for j in resources:
                if (x[i][j].varValue == 1):
                    print ("agent ", i, " gets resource r"+str(j))

    return k.varValue


###############################################################################
# The Envy-Minimizing LP
###############################################################################

def envyminimizingLP(p,verbose=False):

    agents = list(range(1,p.n)) # agent 0 is the auctioneer
    resources = list(range(0,p.m))


    envyLP = pulp.LpProblem("Envy Minimizing LP",pulp.LpMinimize)

    # creating the variables

    x = pulp.LpVariable.dicts("x", (agents, resources),cat = pulp.LpBinary)
    e = pulp.LpVariable("envy bound", lowBound = 0) # upBound = 100

    # objective function: minimize e

    envyLP += e, "e: bound on envy"

    # each resource assigned to one agent
    for j in resources:
        envyLP += sum([x[i][j] for i in agents])==1

    # envy of each agent must be smaller than e
    for i in agents:
        for j in agents:
            if i != j:
                envyLP += sum([p.agent[i].u["r"+str(k)]*x[j][k] for k in resources]) - sum([p.agent[i].u["r"+str(k)]*x[i][k] for k in resources]) <=e

    # solving and printing

    envyLP.solve() # by default COIN-OR
    #envyLP.solve(pulp.GUROBI())

    if verbose:
        print("Status:", pulp.LpStatus[envyLP.status])
        print(envyLP.objective)
        print(pulp.value(envyLP.objective))
        envyLP.writeLP("envyLP.lp",mip=True)
        for i in agents:
            for j in resources:
                if (x[i][j].varValue == 1):
                    print ("agent ", i, " gets resource r"+str(j))

    return e.varValue

###############################################################################
# The Nash-meximizing IP
###############################################################################

def nashproductMIP(p,verbose=False):

    agents = list(range(1,p.n)) # agent 0 is the auctioneer
    resources = list(range(0,p.m))


    nashMIP = pulp.LpProblem("Nash Maximizing MIP",pulp.LpMaximize)

    # creating the variables

    x = pulp.LpVariable.dicts("x", (agents, resources),cat = pulp.LpBinary)

    # objective function: maximize nprod

    nprod = sum([math.log(p.agent[i].u["r"+str(k)])*x[i][k] for k in resources for i in agents]), "log trick"

    nashMIP += nprod

    # each resource assigned to one agent
    for j in resources:
        nashMIP += sum([x[i][j] for i in agents])==1


    # solving and printing

    nashMIP.solve() # by default COIN-OR
    #nashMIP.solve(pulp.GUROBI())

    sol = np.product([sum([p.agent[i].u["r"+str(k)]*x[i][k].varValue for k in resources]) for i in agents])


    if verbose:
        # The status of the solution is printed to the screen
        print("Status:", pulp.LpStatus[nashMIP.status])
        print(nashMIP.objective)
        print(pulp.value(nashMIP.objective))
        nashMIP.writeLP("nashMIP.lp",mip=True)
        for i in agents:
            for j in resources:
                if (x[i][j].varValue == 1):
                    print ("agent ", i, " gets resource r"+str(j))

    return sol