Optimization problem with Integer variables and a squared objective

Question

The following code works:

import cvxpy as cp

a = cp.Variable()
b = cp.Variable()
c = cp.Variable()
d = cp.Variable()

objective = cp.Minimize(cp.square(-2*a + 1.5*b + 3*c + 6.5*d - 2000))

constraints = [a >= 0, b>=0, c>=0, d>=0, a+b<=3000, c+d<=2000, a+c == 500, b+d == 2000]

cp.Problem(objective, constraints).solve()

print("optimal var", a.value, b.value,c.value, d.value)

However, if I use integral variables, e.g.,

a = cp.Variable(integer=True)

this basic example will no longer work and results in the error

Either candidate conic solvers (%s) do not support the cvxpy.error.SolverError: Either candidate conic solvers (['SCIPY']) do not support the cones output by the problem (SOC, NonNeg, Zero), or there are not enough constraints in the problem

Does anyone have any ideas as to how to get around this? Or a better Python package to use?

instead of using a squared error, if it is acceptable to use absolute error in your model (assuming it is more complicated than the trivial example above) that can be made into a MILP and avoid the complication of an integer-based NLP — AirSquid
– AirSquid, Commented Jun 9, 2023 at 17:32
@AirSquid, excellent idea, I think that will work... thank you! — Tejay Lovelock
– Tejay Lovelock, Commented Jun 9, 2023 at 17:59
The error itself is due to the nonexistence of open-source solvers (available in cvxpy) for this problem. See docs. If you are in academia, you might obtain some commercial solver supported. Looking at the table again: scip should work (although quite different compared to commercials). It seems you need to take care at install-time such that the scip solver is available: docs. — sascha
– sascha, Commented Jun 9, 2023 at 19:59
Use an MIQP solver. E.g., you can use demo versions of Gurobi or Cplex. Sometimes ECOS_BB can work (but I have not had much luck with this solver). — Erwin Kalvelagen
– Erwin Kalvelagen, Commented Jun 14, 2023 at 15:48

Bhartendu Awasthi · Accepted Answer · 2023-06-16 08:50:39Z

Another option is to express the problem in AMPL, and then use any non-linear solvers such as bonmin, ipopt (both open source) that gets shipped with AMPL. AMPL also has a rich python API as well where you formulate the problem in AMPL and then pass data from python data structures (rather than having a .dat file in native AMPL). https://amplpy.readthedocs.io/en/latest/

AMPL now offers a full fledge community edition license and can be downloaded from https://ampl.com/start-free-now/ If you want to use AMPL with python, then follow the first link to install individual solvers. Its very easy to do that.

Below is the formulation in AMPL. I personally like AMPL for its expressiveness and its succinct syntax.

squared_objective.mod

var a >= 0 integer;
var b >= 0 integer;
var c >= 0 integer;
var d >= 0 integer;

subject to a_b_constraint:
    a + b <= 3000;

subject to c_d_constraint:
    c + d <= 2000;

subject to a_c_constraint:
    a + c = 500;

subject to b_d_constraint:
    b + d = 2000;

minimize obj_fn:
    (-2*a + 1.5*b + 3*c + 6.5*d - 2000) * (-2*a + 1.5*b + 3*c + 6.5*d - 2000);

Now, you can use any non-linear solver such as bonmin, ipopt, even cbc is also able to solve.

using gurobi options solver gurobiasl; results in:

ampl: options solver gurobiasl;
ampl: solve;
Gurobi 10.0.1: optimal solution; objective 0
2 simplex iterations
1 branch-and-cut nodes

ampl: display obj_fn;
obj_fn = 0

ampl: display a; display b; display c; display d;   
a = 500

b = 2000

c = 0

d = 0

Any other non-linear solver pointed above will work just fine

Now, using python API of AMPL:

from amplpy import AMPL

ampl = AMPL()
ampl.set_option("solver", "cbc")
# OR ampl.set_option("solver", "gurobiasl")
# OR ampl.set_option("solver", "ipopt")
# community edition of Gurobi gets shipped with AMPL !

ampl.read("../squared_objective.mod")

ampl.solve()

assert ampl.get_value("solve_result") == "solved"

# objective function value
ampl.getObjective("obj_fn").value()
# optimal value = 0

# decision variable values
ampl.getValue("a") # a = 500
ampl.getValue("b") # b = 2000
ampl.getValue("c") # c = 0
ampl.getValue("d") # d = 0

Use can easily use python data structures such as list, dictionaries and then pass data to your AMPL program

https://amplpy.readthedocs.io/en/latest/quick-start.html#load-the-data-using-pandas-objects https://amplpy.readthedocs.io/en/latest/quick-start.html#load-the-data-using-lists-and-dictionaries

Collectives™ on Stack Overflow

Optimization problem with Integer variables and a squared objective

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related