2
$\begingroup$

I try to solve this 0-1 integer linear program (maximize, thus the minus) with LinearOptimization:

LinearOptimization[
 -(15 x + 6 y + 0 a),
 {
  275 a >= 0,
  a <= x,
  a <= y,
  a >= -1 + x + y,
  
  a >= 0,
  a <= 1,
  
  x >= 0,
  x <= 1,
  
  y >= 0,
  y <= 1
  }, {x, y, a}, Integers
 ]

This should yield the solution x = y = a = 1. However, I get the following error:

LinearOptimization::misupp: The CLP method does not support mixed integer optimization.

I introduced a to linearize the constraint 275 x y >= 0. Also, I used matrix/vector notation in LinearOptimization

LinearOptimization[-{15, 6, 0}, {
  -{{0, 0, -275},
    {-1, 0, 1},
    {0, -1, 1},
    {1, 1, -1},
    {-1, 0, 0},
    {1, 0, 0},
    {0, -1, 0},
    {0, 1, 0},
    {0, 0, -1},
    {0, 0, 1}},
  {0, 0, 0, 1, 0, 1, 0, 1, 0, 1}}]

This works and returns {1,1,1}.

The bottom approach shows that my constraints are linear, so why does Mathematica think my program is mixed-linear?

$\endgroup$
1
  • $\begingroup$ LinearOptimization[-(15 x + 6 y + 0 a), {275 a >= 0, a <= x, a <= y, a >= -1 + x + y, a >= 0, a <= 1, x >= 0, x <= 1, y >= 0, y <= 1, {x, y, a} ∈ Integers}, {x, y, a}] $\endgroup$
    – cvgmt
    Dec 3, 2022 at 10:21

1 Answer 1

2
$\begingroup$

Domain for every element in the LinearOptimization should be defined explicitly, therefore code is given by

LinearOptimization[-(15 x + 6 y + 0 a), {275 a >= 0, a <= x, 
  a <= y, a >= -1 + x + y, a >= 0, a <= 1, x >= 0, x <= 1, y >= 0, 
  y <= 1}, {Element[x, Integers], Element[y, Integers], 
  Element[a, Integers]}]

Out[]= {x -> 1, y -> 1, a -> 1} 
$\endgroup$
2
  • $\begingroup$ It seems that Mathematica still thinks it's an MLP but implicitly uses a method that can solve it because LinearOptimization[-(15 x + 6 y + 0 a), {275 a >= 0, a <= x, a <= y, a >= -1 + x + y, a >= 0, a <= 1, x >= 0, x <= 1, y >= 0, y <= 1}, {Element[x, Integers], Element[y, Integers], Element[a, Integers]}, Method -> "Simplex"] (or CLP, InteriorPoint) returns the same error. LinearOptimization::misupp: The InteriorPoint method does not support mixed integer optimization. I'd like to compare the speed of solving with different methods. $\endgroup$
    – rndm_me
    Dec 3, 2022 at 11:55
  • 1
    $\begingroup$ @rndm_me Please, note, CLP and InteriorPoint are methods that only work with machine precision. $\endgroup$ Dec 3, 2022 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.