15
votes
Modeling the Choose function
I am going to assume that $x \in \mathbb{N}$ and $y \in \mathbb{N}$ are variables, and that $C \in \mathbb{N}$ is a constant. In this case, you can benefit from the fact that your equality constraint ...
- 6,033
9
votes
Specific algorithms to compute the LP-relaxation of the Set-Cover problem
Not sure about solving the LP relaxation, but you can get a closed-form lower bound from LP duality, without calling any solver. Let $y_j$ be the dual variable for constraint $j\in U$. The dual LP ...
- 29.8k
5
votes
Accepted
Minimum vertex cover and linear programming
I am pretty sure the answer is NO!
Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and two additional nodes $r_1, r_2$ that have an edge to each of the nodes in the $...
- 701
5
votes
Use GA for Assignment Problem?
I agree with @RobPratt that a GA is not the ideal way to solve an assignment problem. The Wikipedia entry for assignment problems lists a few alternatives, and as Rob points out an LP solver should ...
- 37.4k
3
votes
Accepted
Combinatorial Optimisation, Allocation problem
Given what appears to be a nonlinear constraint (the 5% deviation constraint) and a nonlinear (and apparently arbitrarily complex) objective function, I would not be optimistic about finding a ...
- 37.4k
3
votes
Accepted
How to solve assignment problem with additional constraints?
You can create additional "group agents" that represent combinations of actual agents (for instance, $P_{17}$ might be the pairing of $P_1$ and $P_2$) and/or additional "combo tasks&...
- 37.4k
2
votes
How to solve assignment problem with additional constraints?
This sounds like a special case of the parallel assignment problem in which the preemption (this is a standard notation in the scheduling theory) would be allowed. I am not aware of how this problem ...
- 8,185
2
votes
Accepted
Minimum vertex cover and linear programming 2
I am pretty sure the answer is again NO. And it can be seen with the same graph as in the previous question here.
Consider the graph consisting of a $K_5$ (the fully connected graph with 5 nodes) and ...
- 701
1
vote
Modeling the Choose function
AFAIK, some optimization software such as GAMS has some nice functions to deal with this. For example, function likes factorial (fact(x)).
Indeed, some estimations for the factorial function using the ...
- 8,185
Only top scored, non community-wiki answers of a minimum length are eligible