The problem below aims to find the minimum cost for the network architecture:

We want to build a network where client terminals are connected to servers by cabling which is very expensive. The network architecture should be designed to minimize the total cost of the cabling used.

It is assumed that $T=\{T_1,\ldots,T_n\}$ is the set of terminals. Cabling costs are known.

Show that it is possible to model this problem with a graph theory tool.

Can someone please help to initialize and how to process to solve this problem?

  • 3
    $\begingroup$ Hint: is it ever optimal for the network to contain a cycle? $\endgroup$
    – RobPratt
    Jun 29 '20 at 18:35
  • 1
    $\begingroup$ Welcome to OR.SE! This question feels like a homework problem. If so, that's fine, but please see Can I ask a homework question on OR.SE?. In particular, please make sure you explain what you have tried so far, and where you get stuck. $\endgroup$
    – LarrySnyder610
    Jun 29 '20 at 20:07
  • 1
    $\begingroup$ A more descriptive title might help, too. $\endgroup$
    – LarrySnyder610
    Jun 29 '20 at 20:09

Your problem description is quiet vague. So i picked the simplest solution to his problem i can think off in modeling language JuMP.

If you are more detailed about the reality you are working with a better model can be chosen.

clients = 24
servers = 3

using JuMP
using GLPK

class = Model(with_optimizer(GLPK.Optimizer))

cost = rand(clients, servers) # cost to connect client i, to server j as cost[i,j]
# write an array 
@variable(class, connection[1:clients,1:servers], Bin) # a connection exist or it doesn't

for i in 1:clients
    @constraint(class, sum(connection[i,:]) >= 1 )
    # every client is connected to at least one server directly 
    # and can only connect to servers
    # a server can receive an unlimited amount of connections.

@objective(class, Min, sum(cost.*connection)) # minimize cost of connections

@time optimize!(class)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.