How does one define SOS in PuLP?

[vjktm]

Hi,
is it possible to define SOS in PulP?
I did not see it in any of the examples but the source does have some
sos related lines.
Thanks.

[ukyo yagamura]

Hi,

Is SOS make the problem to be non linear ?

If it's true, I think that pulp cannot do that because it can solve only linear optimization or linear programming.
 As the slogan says "puLP: An LP modeler in Python".

Regards,

Ukyo

[Christophe-Marie Duquesne]

2010/3/18 ukyo yagamura <ukyo.y...@gmail.com>:

SOS are special types of linear constraints. Basically, it describes
constraints where at most one variable can be non zero (type 1) or two
(type 2). Most solvers will use more efficient branching rules if you
specify your constraints are SOS. Indeed, it would be cool if there
was a way to specify these kind of rules (there is one in OSI C++
library).

--
Christophe-Marie Duquesne
06 84 14 26 82 - mobile
04 76 57 48 06 - g-scop
04 97 04 27 33 - amadeus

[Stuart Mitchell]

Ah good point I don't use SOS constraints so I haven't really looked at
their implementation in pulp.

However, J.S. Roy (the original author) did write code that will output
SOS constraints in the LP format.

Therefore, the command line solver CPLEX_CMD will solve it as cbc does
not seem to understand the format.

There is no infrastucture to add these constraints to the problem though :-(

so if you want to use them you need to directly add to
prob.sos1
and prob.sos2

I played around with it and got this example working but I'm not to sure
about it note that you can't seem to give a name to the sos constraint

>>> prob = LpProblem('sos_test')
>>> x1 = LpVariable('x1', cat = LpInteger)
>>> x2 = LpVariable('x2', cat = LpInteger)
>>> prob += -x1 - x2
>>> prob += x1 + x2 <= 5
>>> prob.sos1['sos'] = x1 + 2*x2
>>> prob.writeLP('testsos.lp')

gives an lp file like so
\* sos_test *\
Minimize
OBJ: - x1 - x2
Subject To
_C1: x1 + x2 <= 5
Bounds
x2 free
x1 free
Generals
x2
x1
SOS
S1::
x1: 1
x2: 2
End

And is solved by CPLEX_CMD
>>> prob.solve(CPLEX_CMD())
ILOG CPLEX 11.010, licensed to "universityauckland-newzealand", options:
e m b q use=10

Welcome to CPLEX Interactive Optimizer 11.0.1
with Simplex, Mixed Integer & Barrier Optimizers
Copyright (c) ILOG 1997-2008
CPLEX is a registered trademark of ILOG

Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.

CPLEX> Problem '/tmp/7262-pulp.lp' read.
Read time = 0.00 sec.
CPLEX> Tried aggregator 1 time.
Presolve time = 0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node
ItCnt Gap

* 0 0 integral 0 -5.0000 -5.0000
0 0.00%

Solution pool: 1 solution saved.

MIP - Integer optimal solution: Objective = -5.0000000000e+00
Solution time = 0.00 sec. Iterations = 0 Nodes = 0

CPLEX> MILP problem relaxed to LP with fixed integer variables using
incumbent solution.
CPLEX> Tried aggregator 1 time.
LP Presolve eliminated 1 rows and 2 columns.
All rows and columns eliminated.
Presolve time = 0.00 sec.

Dual simplex - Optimal: Objective = -5.0000000000e+00
Solution time = 0.00 sec. Iterations = 0 (0)

CPLEX> Solution written to file '/tmp/7262-pulp.sol'.
CPLEX> 1
>>>

However, I do not like this way at all and am open to suggestions
should there be a
LpProblem.addSOS()
function and some hook into the solvers?
What should pulp do if a solver does not support SOS?

Vinaka
Stu

Christophe-Marie Duquesne wrote:
> 2010/3/18 ukyo yagamura <ukyo.y...@gmail.com>:
>
>> Hi,
>>
>> Is SOS make the problem to be non linear ?
>>
>> If it's true, I think that pulp cannot do that because it can solve only
>> linear optimization or linear programming.
>> As the slogan says "puLP: An LP modeler in Python".
>>
>> Regards,
>>
>> Ukyo
>>

[vjktm]

Hi all,
thank you for all responses. This group is so responsive. It
motivates me to continue learning and using PuLP.

Stu,
thanks for the workaround solution of directly adding to pulp.sos.
I think SOS support would be quite useful. I vote yes to it's
inclusion through LpProblem.addSOS() or something similar. I think
the modeling language should support it.

If the chosen solver does not support SOS then calls to pulp.solve
could initially decline running it or better still (possible in the
future) create equivalent constraints that would honor the SOS
restrictions (even if not as efficient). E.g., for a SOS1 with N
members yi, one could define binary vector xi such that

lpSum(xi) == 1

and lpDot(x, y) would be used wherever one of the yi's is needed in
the LP formulation.

So far I have manually edited the lp file written by PuLP to add SOS
and modify for use with lpsolve.

If we have enough support I am volunteering to help code this.

> > 2010/3/18 ukyo yagamura <ukyo.yagam...@gmail.com>:

>
> >> Hi,
>
> >> Is SOS make the problem to be non linear ?
>
> >> If it's true, I think that pulp cannot do that because it can solve only
> >> linear optimization or linear programming.
> >>  As the slogan says "puLP: An LP modeler in Python".
>
> >> Regards,
>
> >> Ukyo
>