If you are going to the conference or if you are based in Abu Dhabi and would like to discuss MOSEK, don’t hesitate to reach out to sales@mosek.com.
See you in Abu Dhabi!
When an optimization problem is infeasible it is common to ask for the reason for infeasibility. It is very typical that the model is infeasible because it contains a set of mutually contradicting constraints which is relatively small compared to the total size of the problem. Locating and analyzing such a subset is usually helpful in understanding the reasons for infeasibility.
Such considerations have led the OR community to come up with the notion of Irreducible Infeasible Set (IIS) - a subset of constraints which is infeasible but cannot be reduced to a smaller infeasible set (all its proper subsets are already feasible). Every infeasible problem has an IIS - possibly many, possibly of different sizes. For example the problem bgdbg1 (see below) has a few hundred bounds but its infeasibility is caused already by the small segment
X104_JY >= 0.0
X104_JH >= 36.0
X104_JY + X104_JH <= 6.0
consisting of 3 bounds, which is an IIS. In fact the same model has also another IIS
X199_CM1 >= 96.0
X199_CM1 <= 86.0
with just 2 bounds (it doesn't get any better - a single linear bound is always feasible on its own).
An IIS can be found by a simple iterative algorithm which tries to remove one bound at a time and checks if the problem remains infeasible. We have implemented it for linear and mixed-integer linear problems in a recently published python notebook, where you can also read more details of the algorithm and its implementation. You can also download the python code directly.
Below are the results produced by our sample code on the infeasible problems from NETLIB. We report the number of bounds in the problem, the size of the (Farkas) infeasibility certificate (these are the bounds that will appear in the infeasibility report or in the task.getinfeasiblesubproblem() function) and finally the size of the smallest IIS out of 5 runs of the algorithm (the IIS found depends on an ordering of the bounds, which we randomize).
bgdbg1.gz: OK, all bounds = 926, Farkas size = 2, IIS size = 2
bgetam.gz: OK, all bounds = 1577, Farkas size = 31, IIS size = 25
bgindy.gz: OK, all bounds = 14694, Farkas size = 196, IIS size = 154
bgprtr.gz: OK, all bounds = 68, Farkas size = 12, IIS size = 10
box1.gz: OK, all bounds = 723, Farkas size = 10, IIS size = 9
ceria3d.gz: OK, all bounds = 3576, Farkas size = 117, IIS size = 198
chemcom.gz: OK, all bounds = 1416, Farkas size = 86, IIS size = 37
cplex2.gz: numerical issues, all bounds = 733, Farkas size = 177, IIS size = 715
ex72a.gz: OK, all bounds = 609, Farkas size = 61, IIS size = 60
ex73a.gz: OK, all bounds = 597, Farkas size = 28, IIS size = 25
forest6.gz: OK, all bounds = 196, Farkas size = 96, IIS size = 92
galenet.gz: OK, all bounds = 26, Farkas size = 5, IIS size = 5
gosh.gz: OK, all bounds = 15353, Farkas size = 9, IIS size = 9
gran.gz: OK, all bounds = 8386, Farkas size = 2, IIS size = 2
grbeai.gz: OK, all bounds = 10402, Farkas size = 93, IIS size = 54
itest2.gz: OK, all bounds = 13, Farkas size = 3, IIS size = 3
itest6.gz: OK, all bounds = 21, Farkas size = 3, IIS size = 3
klein1.gz: OK, all bounds = 108, Farkas size = 55, IIS size = 54
klein2.gz: OK, all bounds = 531, Farkas size = 57, IIS size = 55
klein3.gz: numerical issues, all bounds = 1082, Farkas size = 97, IIS size = 192
mondou2.gz: OK, all bounds = 1832, Farkas size = 24, IIS size = 23
pang.gz: OK, all bounds = 942, Farkas size = 34, IIS size = 32
pilot4i.gz: OK, all bounds = 1886, Farkas size = 43, IIS size = 47
qual.gz: OK, all bounds = 1360, Farkas size = 217, IIS size = 370
reactor.gz: OK, all bounds = 1652, Farkas size = 15, IIS size = 9
refinery.gz: OK, all bounds = 1360, Farkas size = 206, IIS size = 120
vol1.gz: OK, all bounds = 1360, Farkas size = 275, IIS size = 196
woodinfe.gz: OK, all bounds = 173, Farkas size = 2, IIS size = 2
The work reported here and in the notebook was carried out by Adam Bosák during his student internship at MOSEK. Thanks!
Next week Informs annual meeting will take place in Phoenix and MOSEK will of course be there. If you are going to Informs annual meeting and would like to discuss MOSEK, don’t hesitate to reach out to sales@mosek.com.
See you
in Phoenix!
The summer has been long here in Copenhagen, but now it feels like the fall is here to stay. For MOSEK the arrival of autumn means the arrival of thousands of new persons allegeable to use MOSEK for free.
This is because MOSEK, through our academic initiative, grants free licenses for research or educational purposes at degree-granting academic institutions.
Whether you are a new student or a seasoned academic why not use this opportunity to try MOSEK!
The MATLAB R2023b is the first stable release with native support for the Apple Silicon M1/M2 platform.
The MOSEK Optimization Toolbox for MATLAB is available natively for Apple Silicon from MOSEK 10.1. It means that from version 10.1 there are two ways to use MOSEK in MATLAB on the M1/M2 platform:
In a previous blogpost we talked about
additions made to MOSEK with the release of version 10.1. However, as usual
with new releases improvements in the existing functionality have also been
made.
One area where we have improved a lot with
our latest release is with our mixed integer solver. On our internal
benchmarking set we have seen an improvement of over 30 per cent on the geometric
mean of the solution time compared to MOSEK 10.0.
Does this mean you will see a 30 per cent improvement on your mixed integer problems? No, or yes or maybe… It depends!
Mixed integer problems are hard,
NP-complete in fact, and in the design of the solver algorithms there are tradeoffs
to be made. These tradeoffs will make the solver good for certain problems and
less so for others. Tuning the solver will determine which problems it will perform
well on and on which it will not.
At MOSEK we tune our solvers based on our
internal benchmarking sets. These sets are mainly based on problems we have received
from customers, and we feel they are representative of the problems being
solved for practical applications.
So, does this mean you will see a 30 per
cent improvement on your mixed integer problems? No, not for certain. But it might
be worthwhile to upgrade to 10.1 and test and see!
Together with the recently released MOSEK 10.1 we introduced OptServerLight - a light version of a remote optimization server. Let us take this opportunity to write a few words about remote optimization in MOSEK and introduce the two variants of the OptServer.
In a typical scenario the user sets up an optimization problem in MOSEK (through an API, or by reading a file), solves it, and retrieves the solution. All steps are executed in one process, on the same machine. Under remote optimization the user still sets up the problem locally (in the client), but the optimization itself (the call to MSK_optimize(), optimize(), solve() or similar) is being executed on a remote machine (server), before the user can again retrieve the solution in the local process on the client. In practice the client submits the problem data to the server via HTTP/HTTPS, the server calls its own instance of MOSEK to solve the problem, and transmits the solution back to the client in response.
From the client's point of view the process is completely transparent. All it takes is to instruct MOSEK to contact the remote server instead of optimizing locally. Everything else - setting up the problem, retrieving the solution, printing log output - remain unchanged. Here is an illustration in Python Fusion:
