Skip to main content
Operations Research

Return to Answer

typo
Source Link
TheSimpliFire ♦
TheSimpliFire ♦
  • 5.5k
  • 5
  • 23
  • 56

Here is how I would do this: you essentially have a facility location problem, every data point is a potential facility and you decide whether you open it or not (i.e., whether it is the leader of its group). Same goes for the other points, will they be served by the opened facility or not (i.e., will they belong to its group).

Standard MILP models don't scale well and I would formulate this as a set covering model, one variable for each (!) potential cluster, and solve that one by branch-and-price. I would use the left hand side of the non-linear constraint as objective function in the pricing problem and use some tailored algorithm to find the minimum reduced cost clusters. In the master problem I would minimize derthe maximum of the selected clusters' costs.

Solving the master problem (a linear program) can be done in CPLEX, also the tailored pricing problem can be done in your Java code, however you would not be able to have a tailored branching which you might need to solve the model to integer optimality.

Here is how I would do this: you essentially have a facility location problem, every data point is a potential facility and you decide whether you open it or not (i.e., whether it is the leader of its group). Same goes for the other points, will they be served by the opened facility or not (i.e., will they belong to its group).

Standard MILP models don't scale well and I would formulate this as a set covering model, one variable for each (!) potential cluster, and solve that one by branch-and-price. I would use the left hand side of the non-linear constraint as objective function in the pricing problem and use some tailored algorithm to find the minimum reduced cost clusters. In the master problem I would minimize der maximum of the selected clusters' costs.

Solving the master problem (a linear program) can be done in CPLEX, also the tailored pricing problem can be done in your Java code, however you would not be able to have a tailored branching which you might need to solve the model to integer optimality.

Here is how I would do this: you essentially have a facility location problem, every data point is a potential facility and you decide whether you open it or not (i.e., whether it is the leader of its group). Same goes for the other points, will they be served by the opened facility or not (i.e., will they belong to its group).

Standard MILP models don't scale well and I would formulate this as a set covering model, one variable for each (!) potential cluster, and solve that one by branch-and-price. I would use the left hand side of the non-linear constraint as objective function in the pricing problem and use some tailored algorithm to find the minimum reduced cost clusters. In the master problem I would minimize the maximum of the selected clusters' costs.

Solving the master problem (a linear program) can be done in CPLEX, also the tailored pricing problem can be done in your Java code, however you would not be able to have a tailored branching which you might need to solve the model to integer optimality.

Source Link
Marco Lübbecke
Marco Lübbecke
  • 5.9k
  • 23
  • 64

Here is how I would do this: you essentially have a facility location problem, every data point is a potential facility and you decide whether you open it or not (i.e., whether it is the leader of its group). Same goes for the other points, will they be served by the opened facility or not (i.e., will they belong to its group).

Standard MILP models don't scale well and I would formulate this as a set covering model, one variable for each (!) potential cluster, and solve that one by branch-and-price. I would use the left hand side of the non-linear constraint as objective function in the pricing problem and use some tailored algorithm to find the minimum reduced cost clusters. In the master problem I would minimize der maximum of the selected clusters' costs.

Solving the master problem (a linear program) can be done in CPLEX, also the tailored pricing problem can be done in your Java code, however you would not be able to have a tailored branching which you might need to solve the model to integer optimality.