What is the definition of a "maximal feasible solution" in a 0/1 knapsack problem?

85 Views Asked by At

I have the following $0/1$ knapsack problem \begin{aligned} &z=\max \left\{p^T x=12 x_{1}+8 x_{2}+17 x_{3}+11 x_{4}+6 x_{5}+2 x_{6}+2 x_{7}\right\} \\ &\text { s.t. } \quad a^T x=4 x_{1}+3 x_{2}+7 x_{3}+5 x_{4}+3 x_{5}+2 x_{6}+3 x_{7} \leq 9 \\ &\quad x \in\{0,1\}^{7} \end{aligned}

and I was told to give examples of a maximal feasible solution with the maximum cardinality and a maximal feasible solution with the smallest cardinality. I assume the cardinality is about the number of $x_i$ I choose to be equal to $1$, but what does the maximal refer to? Is it about having an optimal value in the objective function? If so, why not just say one of the optimal solutions instead?

1

There are 1 best solutions below

4
On

"Maximal feasible" means that the solution is feasible and if you change any $x_i$ from $0$ to $1$, the solution is no longer feasible.

See section 4.3 of this paper.