1
$\begingroup$

I have a model as below.

enter image description here

I have constructed the matrix of its constraints as below. I need to show the total unimodularity of its constraints matrix. However, the determinant of the below submatrix (specified by red line) is not equal to -1, 0, or 1. This means that the matrix of constraints is not totally unimodular. Can you please let me know whether I am making any mistakes?

enter image description here

Improve this question
$\endgroup$
5
  • $\begingroup$ It would help if you could confirm what's a variable and what's a constant and what the domain of those variables/ constants would be. I assume $x_{ij}$ are binary variables, $w_j$ are continuous variables and $g_j$ are constants? $\endgroup$
    – Walter Sebastian Gisler
    Commented May 29, 2021 at 7:18
  • $\begingroup$ It sounds like you have a business problem and want to come up with a mathematical optimization formulation that has a totally unimodular constraint matrix. What is the business problem? If it is what I think, you can model it as a shortest path problem in a directed acyclic network, and the corresponding constraint matrix will be TU. $\endgroup$
    – RobPratt
    Commented May 29, 2021 at 13:31
  • $\begingroup$ @RobPratt, could you please introduce me to a paper that proves the total unimodularity of a shortest path problem in a directed acyclic network? $\endgroup$
    – mdslt
    Commented Jun 12, 2021 at 23:50
  • $\begingroup$ See Theorem 11.12 in Ahuja, Magnanti, Orlin, Network Flows (1993). $\endgroup$
    – RobPratt
    Commented Jun 13, 2021 at 0:02
  • $\begingroup$ @RobPratt, thanks! $\endgroup$
    – mdslt
    Commented Jun 13, 2021 at 1:45

2 Answers 2

Reset to default
2
$\begingroup$

Your matrix seems to represent the given model. If you multiply any of the variables with $M$, $M$ will definitely be part of the matrix. Like RobPratt pointed out, that alone is sufficient to say that the matrix isn't totally unimodular.

However, assuming that $w_j$ are continuous variables and $g_j$ are constants (confirm please), I believe it is possible to set $M$ to 1 in this case. $M$ has to be a sufficiently large constant relative to the expected size of your $w_j$ and $g_j$. Assuming $w_j$ and $g_j$ would be quantities in kg, you could always change the constants such that $w_j$ and $g_j$ will be in tonnes or even larger units of weight.

With $M = 1$, you should be able to check whether the resulting matrix is unimodular or not.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is amazing. I would like to confirm that w_j are continuous variables, g_j are constants. To make sure that I have understood your point, you meant that I can tentatively give relatively smaller values to my parameters (like g_j) such that I can set M = 1. Under this condition, I would be able to check the total unimodality. Is my understanding correct? $\endgroup$
    – mdslt
    Commented May 29, 2021 at 19:18
  • $\begingroup$ I would like to emphasize that M can certainly get values greater than 1 for many instances (where at least one g_j is greater than 1). However, you are telling me to assume that M=1 only for the sake of evaluating the total unimodality. Is that right? Many thanks. $\endgroup$
    – mdslt
    Commented May 29, 2021 at 19:26
  • $\begingroup$ Yes, that was my thought. Scale the inputs, such that you can solve the problem with M = 1. Nevertheless, this doesn't automatically mean that the matrix is totally unimodular, but at least you have a matrix consisting of only {-1,0,1} elements which is a prerequisite. $\endgroup$
    – Walter Sebastian Gisler
    Commented May 30, 2021 at 5:58
  • $\begingroup$ It is possible to show that if the matrix is totally unimodular, and all constants are integer values, the problem has integer basic solutions. Note the second part: all constants have integer values. It seems like that might not be the case when you scale the $g_j$ values, so even if it turns out that the matrix is totally unimodular, this might not help you for what you want to achieve. As RobPratt says in his comment, you might want to post what your problem is. There might be a more efficient formulation. $\endgroup$
    – Walter Sebastian Gisler
    Commented May 30, 2021 at 6:09
5
$\begingroup$

It is not totally unimodular. A necessary condition is that even the $1\times 1$ submatrices have determinant in $\{-1,0,1\}$. That is, individual entries must be in $\{-1,0,1\}$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ So, I should reformulate my question! Does the matrix I have constructed represent the constraints matrix of the given model? Many many thanks for your help. $\endgroup$
    – mdslt
    Commented May 28, 2021 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.