can someone please explain to me what is meant by easily converting negative objective function coefficients?
This may seem like a restrictive set of conditions, but many problems are easy to convert to this form. For example, negative objective function coefficients are handled by a change of variables in which xj is replaced by (1-xj’). It is also easy to reorder the variables. Constraint right hand sides can be negative, so ≤ constraints are easily converted to ≥ form by multiplying through by -1.
from: http://www.sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf
is the text saying only positive object coefficients can be used with the algorithm or is the text implying altering negative coefficients to a form where all coefficients are positive is superficial to perform?
the "replaced by (1-xj')" to me implies the latter..?
if indeed the latter than can someone please show the conversion process using the example from later in the paper but now with some negative coefficients:
Minimize $Z = -3x_1+5x_2+6x_3-9x_4+10x_5-10x_6$
$coefficients$: $-3,5,6,-9,10,-10$
Subject to:
(1) $–2x_1+ 6x_2–3x_3+4x_4+x_5–2x_6≥2 $
(2) $–5x_1–3x_2+x_3+3x_4–2x_5+x_6≥–2 $
(3) $5x_1–x_2+4x_3–2x_4+2x_5–x_6≥3 $
and
$ x_j $ binary for $ j=1,2...6$
The text is saying that for this algorithnm to work, the coefficients of the objective function must all be positive. It then goes on to state that this is an easy thing to achieve.
Let's consider your example:
The variables with negative coefficients are $x_1$, $x_4$ and $x_6$.
Let $x'_1=1-x_1$, $x'_4=1-x_4$ and $x'_6=1-x_6$
Substituting these into the objective function gives us:
or
but the constant term can be ignored giving
The first constraint is then changed to:
etc