Constrained integer optimization in Python

Question

I'd like to minimize a function, which takes a 3x8 matrix of non-negative integers as input. Each row specifies a variable, whereas each column specifies a certain time point in the system. See the input in CSV format below.

   ,Time0,Time1,Time2
U_i,0,0,0
U_o,0,0,0
C_i,0,0,0
C_o,0,0,0
T_i,0,0,0
T_o,0,0,0
D_i,0,0,0
D_o,0,0,0

The constraints for each column is:

C_i + T_i >= U_i
C_o + T_o >= U_o
D_i <= 15
D_o <= 15
D_i = 0 if C_i == 0
D_o = 0 if C_o == 0

And the overall constraint across rows is C_i + C_o + T_i + T_o = 5. I've looked at scipy.optimize, but cannot find a proper method that handles integers. Could someone give me a hint or a MWE on how to do this?

You should know that most integer programming problems are NP-hard. Also, the form of the function to be minimized matters: if it's linear, it does make the problem easier. — cfh
– cfh, Commented May 28, 2015 at 10:51
The form of the function is nonlinear, although I don't know that much about it. Do you think it would be difficult to get a good approximate solution for this problem? To me it seems like a quite low number of parameters/constraints. — pir
– pir, Commented May 28, 2015 at 11:50
I don't know. Your best bet is probably to get an evaluation license of Gurobi or CPLEX and simply see if it will work. Number of parameters alone is not the most important determining factor of difficulty of these problems. — cfh
– cfh, Commented May 28, 2015 at 11:54

Christoph FG · Accepted Answer · 2015-06-29 18:56:31Z

For smaller problems the AMPL website has a free tool: http://www.ampl.com/TRYAMPL/startup.html. The model file (*.mod) to upload would would be:

set T;

var U_i {T} >= 0 integer;
var U_o {T} >= 0 integer;
var C_i {T} >= 0 integer;
var C_o {T} >= 0 integer;
var T_i {T} >= 0 integer;
var T_o {T} >= 0 integer;
var D_i {T} >= 0 integer;
var D_o {T} >= 0 integer;

minimize obj: sum {t in T} (U_i[t] + U_o[t] + C_i[t] + C_o[t] + T_i[t] + T_o[t] + D_i[t] + D_o[t]);
subject to C1 {t in T}: C_i[t] + T_i[t] >= U_i[t];
subject to C2 {t in T}: C_o[t] + T_o[t] >= U_o[t];
subject to C3 {t in T}: D_i[t] <= 15;
subject to C4 {t in T}: D_o[t] <= 15;
subject to C5 {t in T}: D_i[t] <= C_i[t] / 1000;
subject to C6 {t in T}: D_o[t] <= C_o[t] / 1000;
subject to C7 {t in T}: C_i[t] + C_o[t] + T_i[t] + T_o[t] = 5;

The data file (*.dat):

set T := 1 2 3;

Since you didn't specify an objective function I put in a linear dummy. After uploading both files you can select a solver; I think none of them is an integer solver unfortunately, but some are non-linear. This way you could probably find a lower bound, feasible integer solutions you can get from there by some rounding heuristic (not necessary integer optimal).

Alternatively: Excel solver?

Collectives™ on Stack Overflow

Constrained integer optimization in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related