固定成本弧的最小成本流修改？

Question

我有一个最小成本流网络，其中一些弧有固定费用，也就是说，如果弧有非零流量，那么成本是c\u k，与流量无关。0的流产生0的成本。这些圆弧没有容量限制。

我知道如何将其建模为一个混合整数程序（MIP）：添加一个0/1变量，成本为c\k。将arc上的容量设置为M*y\U k，其中M大于所有电源的总和。因此，当且仅当弧有流时，才会产生固定成本。

是否可以使用最小成本流公式来解决此问题，该公式比一般MIP实现更有效？或工具（或任何其他包）是否扩展到最小成本流以适应这一点？

交叉发布到谷歌或工具列表。

谢了赫谢尔

Answer 1

我不确定我是否理解你（很可能是因为我的无知）你可能会从OR论坛得到比这里更好的回应。

但是，我认为可能有一种方法可以通过AddCircuit（）作为电路来完成您的要求

基本上，我相信可以最大化（或最小化）那些标记为有成本的弧。

这是一个使用AddCircuit约束的示例，其中每个节点的一个传出电弧具有固定成本。

from ortools.sat.python import cp_model

class DiGraphSolver:

    def __init__(self, desc):
        self.model  = cp_model.CpModel()
        self.status = cp_model.UNKNOWN
        self.timing = None

        # AddCircuit needs a numeric index for each node.
        # Here's two lazy key->index / index->key lookups.
        self.keys = {k: i for i, k in enumerate(desc.nodes.keys()) }
        self.revs = {i: k for k, i in self.keys.items() }

        # Determine the start and stop nodes
        self.start = self.keys[desc.start]
        self.stop = self.keys[desc.stop]

        # Store the nodes dict in it's indexed form.
        self.nodes = {self.keys[head]: [self.keys[t] for t in tails] for head,tails in desc.nodes.items()}
        self.heavies = [(self.keys[head],self.keys[tail])  for head,tail in desc.heavies.items()]

        self.arcs = []
        self.vars = []
        self.result = []
        self.heavy_arcs = []
        self.weight = 0

    def setup(self):
        self.arcs = [
            (head,tail, self.model.NewBoolVar(f'{head}:{tail}')) for head, tails in self.nodes.items() for tail in tails
        ]
        self.heavy_arcs = [arc[2] for arc in self.arcs if arc[:-1] in self.heavies]

        # vars is a list of all the arcs defined in the problem.
        self.vars = [arc[2] for arc in self.arcs]

        # Add self loops for all *optional* nodes (because AddCircuit requires a Hamiltonian Circuit)
        # for this example, that's everywhere except for 'start' and 'stop'
        # We just use the keys of self.revs (the index values).
        loops = [(n, n, self.model.NewBoolVar(f'{n}:{n}')) for n in self.revs if n not in [self.start, self.stop]]
        self.arcs += loops

        # connect the stop variable to the start variable as a dummy arc to complete the hamiltonian circuit.
        # Because start and stop are not self-closing (non-optional), we don't need to set truth values.
        loop = (self.stop, self.start, self.model.NewBoolVar(f'loop'))
        self.arcs.append(loop)

        # Now add the circuit as a constraint.
        self.model.AddCircuit(self.arcs)

        # Now reduce weighted nodes.
        self.model.Minimize(sum(self.heavy_arcs))   # look for the shortest network with the lightest weight.

    def solve(self) -> bool:
        cp_solver = cp_model.CpSolver()
        cp_solver.parameters.max_time_in_seconds = 1
        cp_solver.parameters.num_search_workers = 12
        self.status = cp_solver.Solve(self.model)
        return self.summarise(cp_solver)

    def summarise(self, cp_solver) -> bool:
        if self.status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
            self.store(cp_solver)
            return True
        else:
            if self.status == cp_model.INFEASIBLE:
                print(f"Challenge for {self.step_count} arc{'s ' if self.step_count > 1 else ' '}is infeasible after {cp_solver.WallTime()}s.")
            else:
                print(f"Solver ran out of time.")
            return False

    def store(self, cp_solver):
        self.timing = cp_solver.WallTime()
        used = [arc for arc in self.arcs if cp_solver.Value(arc[2])]
        arc = None, self.start
        while True:
            arc = next((link for link in used if link[0] == arc[1]), None)
            self.result.append(self.revs[arc[0]])
            if arc[1] == self.start:
                break
        self.weight = cp_solver.ObjectiveValue()
        self.step_count = len(self.result) - 1

    def show(self):
        print(f"{'-'.join(self.result)}")
        print(f'Cost: {self.weight}')

class RandomDigraph:
    """
        define a problem.
        26 nodes, labelled 'a' ... 'z'
        start at 'a', stop at 'z'
        Each node other than 'z' has a 4 outgoing arcs (random but not going to 'a')
    """
    def __init__(self):
        from random import sample,randint  #
        names = 'abcdefghijklmnopqrstuvwxyz'
        arcs = 4
        self.steps = 1
        self.start = 'a'
        self.stop = 'z'
        but_first = set(names) ^ set(self.start)
        self.nodes = {v: sample(but_first - set(v), arcs) for v in names}
        self.heavies = {v: self.nodes[v][randint(0, arcs - 1)] for v in names if v != self.stop}
        self.nodes[self.stop] = []

    def print_nodes(self):
        for key, value in self.nodes.items():
            vs = [f" {v} " if v != self.heavies[key] else f"*{v}*" for v in value]
            print(f'{key}: {"".join(vs)}')

def solve_with_steps(problem) -> int:
    solver = DiGraphSolver(problem)
    solver.setup()
    if solver.solve():
        solver.show()
    return solver.step_count

def solve_az_paths_of_a_random_digraph():
    problem = RandomDigraph()
    problem.print_nodes()
    print()
    solve_with_steps(problem)

if __name__ == '__main__':
    solve_az_paths_of_a_random_digraph()

示例运行（求解a..z）给出

# network: (heavy arcs are marked by the tail in **.)
# eg.  a->p is a heavy arc.
a: *p* d  i  l 
b: *t* u  e  y 
c:  r  v *m* q 
d:  q  t *f* l 
e:  k *o* y  i 
f:  i  p  z *u*
g:  s  h  i *x*
h: *g* l  j  d 
i:  x  f  e *k*
j: *g* r  e  p 
k:  d *c* g  q 
l:  r  f  j *h*
m: *i* b  d  r 
n:  t  v  y *b*
o:  s  x  q *w*
p:  w  g *h* n 
q:  o  r *f* p 
r:  f *c* i  m 
s:  y  c  w *p*
t: *y* d  v  i 
u: *h* z  w  n 
v: *d* x  f  t 
w:  l  c *s* r 
x: *j* r  g  m 
y:  b  j *u* c 
z: 

Solution:
a-i-e-k-g-h-j-p-w-c-q-o-s-y-b-u-n-t-v-x-r-m-d-l-f-z

Cost: 0.0