4
votes
Accepted
Bellman Equation for nonlinear model
Let $f(n,b)$ be the maximum objective value for the problem with variables $x_1,\dots,x_n$ and constraint right-hand side $b$. You want to compute $f(3,7)$.
Let $a_i$ be the constraint coefficient of $...
- 30.5k
4
votes
Cover cuts for knapsack constraint with integer variables
Consider the integer knapsack set as:
$$ K_{I} = \{ x \in Z^{N}_{+} : ax \leq b, x \leq u\} $$
Let $C \subseteq N$ be a cover if $\lambda = \sum_{i \in C} u_ia_i − b \gt 0$ and consider the ...
- 8,450
3
votes
Separating violated cover inequalities
A partial answer to part (ii) of your question (this was too long for a comment so I'm including it as an answer). Note that the following assumes a minimal cover.
The sequence independent lifting ...
- 131
3
votes
Accepted
Separating violated cover inequalities
As a heuristic for finding a minimal violated cover inequality, you can solve your min-knapsack problem to find a cover $C$. Then, you may note that all objective function coefficients of the ...
- 6,352
2
votes
Bellman Equation for nonlinear model
Assuming there are n stages, S symbolized by say $s$ define $x$ as $x_{1,s},x_{2,s}, x_{3,s}$: decision vector $X_s$ and $Z(X_s)$ as optimal value for every stage $s$ subject to same constraint
Using ...
- 3,343
2
votes
A sum with a product-penalty
You might consider using dynamic programming, as in the usual binary knapsack problem. Let $f(n,k,C)$ be the optimal objective value for the original problem. Conditioning on the value of $x_n\in\{0,1\...
- 30.5k
2
votes
A sum with a product-penalty
One way is to replace the product part with its log. So if $z=\prod_i (1-x_i(1-b_i))$, this can be substituted with $\sum_i \log(1-x_i(1-b_i))$ or simply $\sum_i x_i \cdot \log b_i$.
This 2nd ...
- 3,343
2
votes
Accepted
Optimal to-do list scheduling in Python using Pyomo
In addition to the below code
for m in model.Tasks:
model.column_constraint.add(sum( model.x[n,m] * 0.25 for n in model.Intervals ) <= durations[m])
If you ...
- 3,343
2
votes
Cover cuts for knapsack constraint with integer variables
Sure. Another way of doing this is by extending the number of items. Suffices to create $\lfloor \frac{b}{a_i} \rfloor$ dummy items to each item $i \in N$. Thus, we would have the new items set $N^{'} ...
- 1,208
2
votes
Accepted
Knapsack Constraint
If you complement the variables $y_i=1−z_i$, substitute, and rearrange terms, you get a classic knapsack constraint. And yes, solvers generally separate cuts from all available structures.
A simple ...
- 6,352
2
votes
Need help with integer programming exercise
As the problem only contains four variables let's define $f$ as the feasible solution space of the problem. Then $f$ contains $12$ feasible solutions: $\{(1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,...
- 8,450
1
vote
Need help with integer programming exercise
Given the system you presented
$X = \{ x \in \{0, 1\}^4 : 97 x_1 + 32 x_2 + 25 x_3 + 20 x_4 \leqslant 139 \}$ (1)
We have that, if $x_1 = 1$, then $x_2 + x_3 + x_4 \leqslant 1$, since any solution ...
- 1,208
1
vote
Knapsack Problem with Multiple Properties
First, let $x_i=1$ if the $i$th example is picked, where $i \in \{1, 2, …, N\}$, and $x_i=0$ otherwise.
If you want to maximize the sum of ALL the elements, simply a knapsack problem with non-varying ...
- 495
1
vote
Accepted
How to Set Up an Optimization Problem Like the 0/1 Knapsack
You can certainly model this as a binary integer program. The constraints are very straightforward, and either filling the maximum number of fields or (equivalently) maximizing the number of words ...
- 37.9k
Only top scored, non community-wiki answers of a minimum length are eligible