This repository has been archived by the owner on Jul 7, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
linear_program.py
86 lines (69 loc) · 2.14 KB
/
linear_program.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
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
"""
Contains the linear program for the correlation robust influence problem.
We use `Pyomo <https://pyomo.org/>`_ to model our problem.
"""
# Python Standard library
from collections.abc import Hashable
from typing import Sequence
# packages
from igraph import Graph
from pyomo.environ import (
AbstractModel,
Constraint,
Objective,
Set,
SolverFactory,
Var,
minimize,
value,
)
SOLVER = SolverFactory("gurobi") # modify this to use alternative solvers
# An alternative is CBC, which uses the string "cbc"
def inf_abs_mod(input_graph: Graph) -> AbstractModel:
"""
Create the abstract model which is shared among all concrete models.
"""
# RESERVED SEED NAMES
# if 's' in input_graph or 't' in input_graph:
# raise ValueError
# Abstract Model to be shared throughout greedy algorithm
mod = AbstractModel()
# Common sets
mod.V = Set(initialize=[n.index for n in input_graph.vs()])
mod.E = Set(initialize=[e.tuple for e in input_graph.es()], dimen=2)
# Common variables
mod.pi = Var(mod.V, bounds=(0, 1))
return mod
def inf_conc_mod_solve(
seed_set: Sequence[Hashable],
abs_mod: AbstractModel,
input_graph: Graph,
) -> float:
"""
Instantiate and solve a concrete instance of the model.
Default solver is `CBC <https://github.com/coin-or/Cbc>`_.
"""
inst = abs_mod.create_instance()
# Sets
inst.S = Set(initialize=seed_set)
inst.VmS = inst.V - inst.S # type: ignore
# Objective Function
o_expr = sum(inst.pi[i] for i in inst.VmS) # type: ignore
inst.obj = Objective(expr=o_expr, sense=minimize)
# Constraints
inst.flow_profit = Constraint(
inst.E,
rule=(
lambda model, i, j: (
model.pi[i] - model.pi[j]
<= input_graph.es[input_graph.get_eid(i, j)]["q"]
)
),
)
inst.seed = Constraint(inst.S, rule=lambda model, i: model.pi[i] == 1)
SOLVER.solve(inst)
val = value(inst.obj)
if isinstance(val, float):
return val + len(seed_set)
else:
raise ValueError("Unexpected outcome of `pyomo.environ.value`")