[Dip] Solving master problems using interior point method
Jonas Christoffer Villumsen
jcvi at man.dtu.dk
Mon Jan 10 03:21:45 EST 2011
Shahin,
Yes, you are right. Using
CPXsetdblparam(env, CPX_PARAM_BAROBJRNG, 1e72);
Gets me through the first couple of MP solves. Then, however, it terminates with
24 z(t3, a4<1,3>) 1.000
25 x(t0, a0<0,1>) 15.000
29 x(t0, a4<1,3>) 15.000
46 theta(t0, n1 -15.000
47 theta(t0, n2 -15.000
isIPFeasible = 1
D-ALGO : 75.3 [CPU: 75.27 ] --- isIPFeasible() ----------> funcT = 1.2
Solution is app-feasible, nSolutions=0
New Global UB = 151
MASTER PRIM[ 3-> y2(a3<2,3>)] = 1.0000000000
MASTER PRIM[ 5-> z(t0, a0<0,1>)] = 1.0000000000
MASTER PRIM[ 6-> z(t0, a1<0,2>)] = 1.0000000000
MASTER PRIM[ 7-> z(t0, a2<1,2>)] = 1.0000000000
MASTER PRIM[ 9-> z(t0, a4<1,3>)] = 1.0000000000
MASTER PRIM[ 10-> z(t1, a0<0,1>)] = 1.0000000000
MASTER PRIM[ 11-> z(t1, a1<0,2>)] = 1.0000000000
MASTER PRIM[ 12-> z(t1, a2<1,2>)] = 1.0000000000
MASTER PRIM[ 13-> z(t1, a3<2,3>)] = 1.0000000000
MASTER PRIM[ 14-> z(t1, a4<1,3>)] = 1.0000000000
MASTER PRIM[ 15-> z(t2, a0<0,1>)] = 1.0000000000
MASTER PRIM[ 16-> z(t2, a1<0,2>)] = 1.0000000000
MASTER PRIM[ 17-> z(t2, a2<1,2>)] = 1.0000000000
MASTER PRIM[ 18-> z(t2, a3<2,3>)] = 1.0000000000
MASTER PRIM[ 19-> z(t2, a4<1,3>)] = 1.0000000000
MASTER PRIM[ 20-> z(t3, a0<0,1>)] = 1.0000000000
MASTER PRIM[ 21-> z(t3, a1<0,2>)] = 1.0000000000
MASTER PRIM[ 22-> z(t3, a2<1,2>)] = 1.0000000000
MASTER PRIM[ 23-> z(t3, a3<2,3>)] = 1.0000000000
MASTER PRIM[ 24-> z(t3, a4<1,3>)] = 1.0000000000
MASTER PRIM[ 25-> x(t0, a0<0,1>)] = 15.0000000000
MASTER PRIM[ 29-> x(t0, a4<1,3>)] = 15.0000000000
MASTER PRIM[ 46-> theta(t0, n1] = -15.0000000000
MASTER PRIM[ 47-> theta(t0, n2] = -15.0000000000
D-ALGOPC : 75.3 [CPU: 75.33 ] --- solutionUpdateAsIp() ----> funcT = 3.95
************ resolve using barrier
CPLEX Error 1017: Not available for mixed-integer programs.
CPX0000 CPLEX Error 1017: Not available for mixed-integer programs.
CPLEX Error 1217: No solution exists.
CPX0000 CPLEX Error 1217: No solution exists.
CPLEX Error 1217: No solution exists.
CPX0000 CPLEX Error 1217: No solution exists.
Solution update n_cols:106 n_rows: 79 n_iter: 0 time: 3.99
CPLEX Error 1217: No solution exists.
CPX0000 CPLEX Error 1217: No solution exists.
CPLEX Error 1217: No solution exists.
CPX0000 CPLEX Error 1217: No solution exists.
CPLEX Error 1217: No solution exists.
CPX0000 CPLEX Error 1217: No solution exists.
Iteration Count : 0
isAbandoned() : 1
isProvenOptimal() : 0
isProvenPrimalInfeasible() : 0
isProvenDualInfeasible() : 0
isPrimalObjectiveLimitReached : 0
isDualObjectiveLimitReached : 0
isIterationLimitReached : 0
CPLEX Error 1217: No solution exists.
CPX0000 CPLEX Error 1217: No solution exists.
Assertion failed: 0, file ..\..\..\..\src\DecompAlgo.cpp, line 2448
I suppose, it is trying to resolve the master as an MIP, so solving using interior point methods should be conditional.
Thanks,
Jonas
From: dip-bounces at list.coin-or.org [mailto:dip-bounces at list.coin-or.org] On Behalf Of Shahin Gelareh
Sent: 8. januar 2011 10:21
To: dip at list.coin-or.org
Subject: Re: [Dip] Dip Digest, Vol 9, Issue 3
Hi Jonas,
if I am not wrong:
I think, you have go to set CPX_PARAM_BAROBJRNG to some thing larger than 1e20.
Also, be sure that your primal or dual are not actually unbounded.
regards,
On Sat, Jan 8, 2011 at 2:35 AM, <dip-request at list.coin-or.org<mailto:dip-request at list.coin-or.org>> wrote:
Send Dip mailing list submissions to
dip at list.coin-or.org<mailto:dip at list.coin-or.org>
To subscribe or unsubscribe via the World Wide Web, visit
http://list.coin-or.org/mailman/listinfo/dip
or, via email, send a message with subject or body 'help' to
dip-request at list.coin-or.org<mailto:dip-request at list.coin-or.org>
You can reach the person managing the list at
dip-owner at list.coin-or.org<mailto:dip-owner at list.coin-or.org>
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Dip digest..."
Today's Topics:
1. Re: Dip Digest, Vol 8, Issue 9 (Jonas Christoffer Villumsen)
2. Solving master problems using interior point method
(Jonas Christoffer Villumsen)
----------------------------------------------------------------------
Message: 1
Date: Fri, 31 Dec 2010 00:41:37 +0100
From: Jonas Christoffer Villumsen <jcvi at man.dtu.dk<mailto:jcvi at man.dtu.dk>>
Subject: Re: [Dip] Dip Digest, Vol 8, Issue 9
To: Matthew Galati <matthew.galati at gmail.com<mailto:matthew.galati at gmail.com>>
Cc: "dip at list.coin-or.org<mailto:dip at list.coin-or.org>" <dip at list.coin-or.org<mailto:dip at list.coin-or.org>>, Shahin Gelareh
<shahin.gelareh at gmail.com<mailto:shahin.gelareh at gmail.com>>
Message-ID:
<D1098F5B0816804F870334AA52B65F510132B5BCAE71 at WINEXCHANGE1.win.dtu.dk<mailto:D1098F5B0816804F870334AA52B65F510132B5BCAE71 at WINEXCHANGE1.win.dtu.dk>>
Content-Type: text/plain; charset="us-ascii"
Logs for for first and second run attached. Thank you for your assistance.
firstrun.txt 1) has
__DECOMP_LP_CPX__
__DECOMP_IP_CPX__
secondrun.txt 2) has
__DECOMP_LP_CLP__
__DECOMP_IP_CPX__
From: Matthew Galati [mailto:matthew.galati at gmail.com<mailto:matthew.galati at gmail.com>]
Sent: 30. december 2010 03:33
To: Jonas Christoffer Villumsen
Cc: Shahin Gelareh; dip at list.coin-or.org<mailto:dip at list.coin-or.org>
Subject: Re: [Dip] Dip Digest, Vol 8, Issue 9
I have tried different settings
1)
__DECOMP_LP_CPX__
__DECOMP_IP_CPX__
Gives a range constraint error.
Can you post the error log?
COIN Exception [ Range constraints are not yet supported. Please break up your range constraints into two constraints. ] at ..\..\..\..\src\DecompAlgo.cpp:L1170 in DecompAlgo:
:masterMatrixAddArtCols
2)
__DECOMP_LP_CLP__
__DECOMP_IP_CPX__
No error.
In either case, however, It doesn't seem to be using CPLEX.
Turn up the log levels and post the log (or just send it to me directly).
In the parameter file, use
[DECOMP]
LogLpLevel = 1
LogDebugLevel = 3
LogLevel = 3
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/dip/attachments/20101231/066d846b/attachment.html
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: firstrun.txt
Url: http://list.coin-or.org/pipermail/dip/attachments/20101231/066d846b/attachment.txt
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: secondrun.txt
Url: http://list.coin-or.org/pipermail/dip/attachments/20101231/066d846b/attachment-0001.txt
------------------------------
Message: 2
Date: Wed, 5 Jan 2011 10:12:02 +0100
From: Jonas Christoffer Villumsen <jcvi at man.dtu.dk<mailto:jcvi at man.dtu.dk>>
Subject: [Dip] Solving master problems using interior point method
To: Matthew Galati <matthew.galati at gmail.com<mailto:matthew.galati at gmail.com>>
Cc: "dip at list.coin-or.org<mailto:dip at list.coin-or.org>" <dip at list.coin-or.org<mailto:dip at list.coin-or.org>>
Message-ID:
<D1098F5B0816804F870334AA52B65F510132B5DF0E4D at WINEXCHANGE1.win.dtu.dk<mailto:D1098F5B0816804F870334AA52B65F510132B5DF0E4D at WINEXCHANGE1.win.dtu.dk>>
Content-Type: text/plain; charset="us-ascii"
Hi all,
Does anyone have experience solving master problems with an interior point method?
There is a parameter SolveMasterUpdateAlgo that can be set to 2 (barrier), but this doesn't seem to have an effect.
In DecompAlgo.cpp I tried to set DO_INTERIOR. I managed to get it to run, but it terminates with an assertion failure - saying that Barrier limit on dual objective exceeded.
I have pasted some of the log below (full log attached). I guess the barrier algorithm doesn't find a feasible solution (within the set limit), and the infeasible state is not set properly (as stated in the comments of the code). Is this the case? And if so any ideas how to come by that?
Thanks,
Jonas
D-ALGO : 4.35 [CPU: 4.37 ] <--- solutionUpdate() --------
Tried aggregator 1 time.
CPX0000 Tried aggregator 1 time.
LP Presolve eliminated 43 rows and 53 columns.
CPX0000 LP Presolve eliminated 43 rows and 53 columns.
Reduced LP has 36 rows, 44 columns, and 76 nonzeros.
CPX0000 Reduced LP has 36 rows, 44 columns, and 76 nonzeros.
Presolve time = 0.02 sec.
CPX0000 Presolve time = 0.02 sec.
Parallel mode: using up to 2 threads for barrier.
CPX0000 Parallel mode: using up to 2 threads for barrier.
Number of nonzeros in lower triangle of A*A'CPX0000 Number of nonzeros in
lower triangle of
= 144
CPX0000 Number of nonzeros in lower triangle oCPX0000 A*A'
Using Approximate Minimum Degree ordering
CPX0000 Using Approximate Minimum Degree ordering
Total time for automaticCPX0000 Total time for
ordering = 0.00 sec.
CPX0000 Total time foCPX0000 automatic
Summary statistics for Cholesky factor:
CPX0000 Summary statistics for Cholesky factor:
Threads = 2
CPX0000 Threads = 2
Rows in Factor = 36
CPX0000 Rows in Factor = 36
Integer space required = 36
CPX0000 Integer space required = 36
Total non-zeros in factor = 180
CPX0000 Total non-zeros in factor = 180
Total FP ops to factor = 1140
CPX0000 Total FP ops to factor = 1140
Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf
CPX0000 Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf
0 1.2727273e+021 4.0000000e+000 1.75e+021 0.00e+000 1.12e+002
CPX0000 0 1.2727273e+021 4.0000000e+000 1.75e+021 0.00e+000 1.12e+002
1 5.9609448e+020 5.6913266e+020 3.93e+005 0.00e+000 1.99e+001
CPX0000 1 5.9609448e+020 5.6913266e+020 3.93e+005 0.00e+000 1.99e+001
Barrier limit on dual objective exceeded.
CPX0000 Barrier limit on dual objective exceeded.
Infeasible barrier solution (dependent on objective limit).
CPX0000 Infeasible barrier solution (dependent on objective limit).
Total real time on 2 threads = 0.09 sec.
CPX0000
CPX0000 Total real time on 2 threads = 0.09 sec.
Solution update n_cols:97 n_rows: 79 n_iter: 0 time:
0.109
Iteration Count : 0
isAbandoned() : 0
isProvenOptimal() : 0
isProvenPrimalInfeasible() : 0
isProvenDualInfeasible() : 0
isPrimalObjectiveLimitReached : 0
isDualObjectiveLimitReached : 0
isIterationLimitReached : 0
Assertion failed: 0, file ..\..\..\..\src\DecompAlgo.cpp, line 2434
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/dip/attachments/20110105/37855752/attachment.html
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: log.txt
Url: http://list.coin-or.org/pipermail/dip/attachments/20110105/37855752/attachment.txt
------------------------------
_______________________________________________
Dip mailing list
Dip at list.coin-or.org<mailto:Dip at list.coin-or.org>
http://list.coin-or.org/mailman/listinfo/dip
End of Dip Digest, Vol 9, Issue 3
*********************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/dip/attachments/20110110/cea8c9df/attachment.html
More information about the Dip
mailing list