%the Fischer function which is not everywhere Fdifferentiable so I built eval_jacobian for building the jacobian
function [val] = fischer(a, b)
val = zeros(size(a))
for i = 1:size(a)
val(i) = sqrt(a(i)^2+b(i)^2)(a(i)+b(i))
end
end
% use iterative solver for newton eq
while ~all(fischer(x, A*x+b) == 0) & its < max_it
% compute the Jacobian
J = eval_jacobian(A, b, x);
% compute the value of the Fischer function
p = fischer(x, A*x + b);
% the natural merit function for convergence measure
residual(its) = .5*(p'*p);
% the newton eq, solve J*h = p
%WHAT WOULD YOU SUGGEST?
% update the solution vector
x = x + h;
% increment the iteration counter
its = its + 1;
end
The direct solution is the exact solver  GaussSeidel where h = p/J. Please let me know if you have any suggestions.
Thank you.
First of all you should decide how you'll model the problem  as an ordinary MILP or somehow else. If former, you could use any modeling language (including Python, MATLAB) + any MILP solver.
scipy has neither MILP solver nor other tools for graph modeling and solving.
BTW, there are some people in our optimization dept with strong graph probs experience, although they haven't deal with neither Python nor MATLAB.
]]>I am searching for something similar...
I am looking for a userfriendly platform which would allow me to model a production scheduling problem with changeover times. Since it's an NPHard problem, I am getting convinced that a CP formulation would be most appropriate. Later on, a GUI should be designed to allow a user to interact with the model.
OPL CPLEX CP optimizer is too expensive for me. Most of the OpenSourceSW I found is too cumbersome to use: either the setup procedure is not transparent, or the modeling itself is not intuitive (deep understanding of programming is required). I found that AIMMS is incredibly userfriendly but does not support CP at this moment (they are working on it). I have made good experience with MatLab, but its optimization/ORmodeling capabilities are limited...
So my "ideal" environment would be similar to AIMMS (intuitive modelling/programming + GUI capabilities), and would help solve CP (and production scheduling) efficiently.
I would appreciate any leads on this! Thanks
Kind Regards, Andrei
]]>Thanks to pythoncvxopt maintainer Soeren Sonnenburg for quick fix.
]]>regards
]]>I need to write a program in Python that has a stdin and stdout. The stdin posted below:
stdin = "7 8 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 1 1"
Programming Notes:
1. Datacenter Cooling
We have some rooms in our datacenter, and we need to connect them all with a single cooling duct.
Here is what we need:
• The datacenter is represented by a 2D grid.
• Rooms we own are represented by a 0.
• Rooms we do not own are represented by a 1.
• The duct has to start at the air intake valve, which is represented by a 2.
• The duct has to end at the air conditioner, which is represented by a 3.
• The duct cannot go in multiple directions out of the intake or the AC  they must be the two endpoints of the duct.
• The duct must pass through each room exactly once.
• The duct cannot pass through rooms we do not own.
• The duct can connect between rooms horizontally or vertically but not diagonally.
Here is an example datacenter:
2 0 0 0
0 0 0 0
0 0 3 1
There are two possible ways to run the duct here:
2000

0000

003 1
or
2 000
  
0 0 00
  
00 3 1
Write a program to compute the number of possible ways to run the duct. For the above example, the correct answer is 2.
Input format:
The program should read from stdin. The input will be a series of integers separated by whitespace.
The first two integers will be W and H, with width and height of the datacenter. These will be followed by W*H more integers, specifying the 2D grid representing the datacenter.
Output format:
The program should write a single integer out to stdout: the number of possible ways to run the duct.
See how fast you can make it compute the stdout.
Our best solution (written in C) can solve the following test case in under 5 seconds on a 2.4GHz Pentium 4, but it's pretty good if you can get to within 12 orders of magnitude of that.
7 8
2 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 0 0 1 1
Again, I'm not asking anyone to write this solution for me, I am just asking for help with what Python Function or API could be used to compute this solution...
]]>Thanks
]]>model timeIndexScheduling
uses "mmxprs"; !gain access to the XpressOptimizer solver
declarations
W=20
N=1..10 !number of activities
T:integer !time period
u:array(N) of integer !constraints for each activity
p:array(N) of integer !processing times for each activity
arc:array(N,N) of integer ! precedence order
e:real
enddeclarations
initializations from 'project.dat'
p u arc
endinitializations
writeln("Begin running model\n")
T:=sum(i in N)p(i) !T is the sum of all processing times
declarations
x:array(N,1..T) of mpvar
y:array(N,1..T) of mpvar
enddeclarations
!Constraint 1
forall(j in N)sum(t in 1..T)x(j,t)= 1
!Constraint 2
forall(i in N)sum(j in 1..T)y(i,j) = p(i)
!Specifying range for variables
forall(i in N,j in 1..T) do
x(i,j) is_binary
y(i,j) is_binary
enddo
!Precedences
forall(i in N, j in Narc(i,j)= 1) do
forall(t in 1..T)sum(s in 1..(tp(i)))x(i,s)>=sum(s in 1..t)x(j,s)
enddo
!minmax approach
forall(j in N,t in 1..T)e>=(t+p(j))*x(j,t)
!Constraint equation
forall(t in 1..T) sum(j in N)u(j)*y(j,t)<=W
minimize(e)
writeln("Objective: ",getobjval)
!forall(i in N,t in 1..T)writeln(x(i,t).sol)
writeln("\nEnd running model")
endmodel
]]>