Skip to main content
MathOverflow

Return to Question

edited body
Source Link
Greg
Greg
  • 1
  • 1

Good evening everyone, I will try to be as succint as possible, pardon my wording as I am not well-versed in combinatorial optimization.

I have defined a problem where I want to minimize the total cost $C$ of a system $S$ composed of discrete unique elements, to give a simple example, let's say $A$ and $B$. $S$ must contain $A$ and $B$. Each of these elements has a cost that is a function of other variables of the system. Now, these elements may have alternatives I want to choose from, such that with altenrativealternative elements $B_1$, $B_2$ and $B_3$ for $B$, if I were to brute-force the cost calculations, I would need to evaluate $C_{S_1} = C_{A} + C_{B_1}$, $C_{S_2} = C_{A} + C_{B_2}$ and $C_{S_3} = C_{A} + C_{B_3}$.

How can I go about solving this problem ? This looks like a variation of the knapsack problem where I would want to minimize the knapsack's weight given a fixed set of included items, some of them without alternatives. Thank you in advance for your help.

Good evening everyone, I will try to be as succint as possible, pardon my wording as I am not well-versed in combinatorial optimization.

I have defined a problem where I want to minimize the total cost $C$ of a system $S$ composed of discrete unique elements, to give a simple example, let's say $A$ and $B$. $S$ must contain $A$ and $B$. Each of these elements has a cost that is a function of other variables of the system. Now, these elements may have alternatives I want to choose from, such that with altenrative elements $B_1$, $B_2$ and $B_3$ for $B$, if I were to brute-force the cost calculations, I would need to evaluate $C_{S_1} = C_{A} + C_{B_1}$, $C_{S_2} = C_{A} + C_{B_2}$ and $C_{S_3} = C_{A} + C_{B_3}$.

How can I go about solving this problem ? This looks like a variation of the knapsack problem where I would want to minimize the knapsack's weight given a fixed set of included items, some of them without alternatives. Thank you in advance for your help.

Good evening everyone, I will try to be as succint as possible, pardon my wording as I am not well-versed in combinatorial optimization.

I have defined a problem where I want to minimize the total cost $C$ of a system $S$ composed of discrete unique elements, to give a simple example, let's say $A$ and $B$. $S$ must contain $A$ and $B$. Each of these elements has a cost that is a function of other variables of the system. Now, these elements may have alternatives I want to choose from, such that with alternative elements $B_1$, $B_2$ and $B_3$ for $B$, if I were to brute-force the cost calculations, I would need to evaluate $C_{S_1} = C_{A} + C_{B_1}$, $C_{S_2} = C_{A} + C_{B_2}$ and $C_{S_3} = C_{A} + C_{B_3}$.

How can I go about solving this problem ? This looks like a variation of the knapsack problem where I would want to minimize the knapsack's weight given a fixed set of included items, some of them without alternatives. Thank you in advance for your help.

Source Link
Greg
Greg
  • 1
  • 1

Combinatorial optimization problem and solving strategy

Good evening everyone, I will try to be as succint as possible, pardon my wording as I am not well-versed in combinatorial optimization.

I have defined a problem where I want to minimize the total cost $C$ of a system $S$ composed of discrete unique elements, to give a simple example, let's say $A$ and $B$. $S$ must contain $A$ and $B$. Each of these elements has a cost that is a function of other variables of the system. Now, these elements may have alternatives I want to choose from, such that with altenrative elements $B_1$, $B_2$ and $B_3$ for $B$, if I were to brute-force the cost calculations, I would need to evaluate $C_{S_1} = C_{A} + C_{B_1}$, $C_{S_2} = C_{A} + C_{B_2}$ and $C_{S_3} = C_{A} + C_{B_3}$.

How can I go about solving this problem ? This looks like a variation of the knapsack problem where I would want to minimize the knapsack's weight given a fixed set of included items, some of them without alternatives. Thank you in advance for your help.