Here is an example where the PuLP modeling tool goes bezerk. In standard linear programming, only \(\ge\), \(=\) and \(\le\) constraints are supported. Some tools also allow \(\ne\), which for MIP models needs to be reformulated into a disjunctive constraint. Here is an attempt to do this in PuLP [1]. PuLP does not support this operator in its constraints, so we would expect a meaningful error message. #------------------------------------------- # funny behavior when using a != constraint # in a PuLP model #------------------------------------------- import pulp model = pulp.LpPro ..read more

In [1], the question was asked: how can I round to two decimal places inside an optimization model? I.e., \[\color{darkred}y_{i,j} = \mathbf{round}(\color{darkred}x_{i,j},2)\] To get this off my chest first: I have never encountered a situation like this. Rounding to two decimal places is more for reporting than something we want inside model equations. Given that, let me look into this modeling problem a bit more as an exercise.  Of course, the first thing we can do is to drop the indices (as mathematicians would say: WLOG, Without Loss Of Generality). So we have as our problem: &n ..read more

Lots of statistical procedures are based on an underlying optimization problem. Least squares regression and maximum likelihood estimation are two obvious examples. In a few cases, linear programming is used. Some examples are: Least absolute deviation (LAD) regression [1] Chebyshev regression [2] Quantile regression [3] Here is another regression example that uses linear programming. We want to estimate a sparse vector \(\color{darkred}\beta\) from the linear model \(\color{darblue}y=\color{darkblue}X\color{darkred}\beta+\color{darkred}e\) where the number of observations \(n\) (rows in ..read more

In [1], a small model is proposed: High-Level Model \[\begin{align} \min\> & \sum_i | \color{darkblue}a_i\cdot \color{darkred}x_i| \\ & \max_i |\color{darkred}x_i| = 1 \\ & \color{darkred}x_i \in \{-1,0,1\} \end{align}\] Can we formulate this as a straight MIP?  The objective is not very complicated. We can handle this with standard formulations, similar to what is used in LAD (Least Absolute Deviation) regression [2]. The constraint is more problematic. It can be interpreted as "at least one of the \(\color{darkred}x_i\) should be nonzero". This type of counti ..read more

 A programmer writes about this blog ..read more

 In [1], the following Pyomo model (Python fragment) is presented: model.x = Var(name="Number of batches", domain=NonNegativeIntegers, initialize=10) model.a = Var(name="Batch Size", domain=NonNegativeIntegers, bounds=(5,20)) # Objective function def total_production(model): return model.x * model.a model.total_production = Objective(rule=total_production, sense=minimize) # Constraints # Minimum production of the two output products def first_material_constraint_rule(model): return sum(0.2 * model.a * i for i in range(1, value(model.x)+1)) >= 70 model.f ..read more

In [1] the following question is posed: I have free variables \(\color{darkred}x_i\). How can I impose the constraint that at least one of the variables is nonzero: \(\color{darkred}x_i\ne 0\). Observations \(\color{darkred}x_i\ne 0\) is somewhat difficult. We need to write this as \[\begin{align}&\color{darkred}x_i\le -\color{darkblue}\epsilon \\ & \textbf{or} \\ &  \color{darkred}x_i\ge \color{darkblue}\epsilon\end{align}\] Here \(\color{darkblue}\epsilon\gt 0\) is a small constant. This "or"-type of constraint needs a binary variable (or something similar). I ..read more

Newer versions of GAMS allow UTF-8 encoded strings as labels. That is very welcome, as these labels may come from data sources that just use Unicode characters. However, when printing to the listing file, we miss proper Unicode support. At first, I thought, "OK, just a few misaligned tables. No big deal." Here is a constructed example showing this may be a bit more problematic. $onText The chars ? in the labels below are Unicode characters (U+1D6FD). The name is "Mathematical Italic Small Beta" In UTF-8 encoding they occupy 4 bytes: 0xF0 0x9D 0x9B 0xBD $offText set j /col1*col2/; paramet ..read more

  In [1], a greyscale picture is approximated by strings (lines) between points around the image. Here, I will try something similar with a formal optimization model. A greyscale image can be represented by an \(m\times n\) matrix of floating point values between zero and one. A value of zero indicates a black pixel, and a value of one a white pixel. In the discussion below, when I use the term color, this means the greyscale value. Here is a \(160\times 120\) image. The pixels have values between 0 and 0.97. Let's call this matrix \(\color{darkblue}{\mathit{GreyScale}}_{i,j} \in ..read more

In [1], a simple problem is described: We have \(n\) items (or orders) with a certain width.  We need to combine these items in groups (called patterns) with rather tight limits on the total width. The total length of a pattern (the sum of the lengths of the items assigned to this pattern) must be between 335 and 340. As a result, we may not be able to assign all items. The remaining items cannot be formed into valid patterns. The objective is to try to place as many items as possible into patterns. An indication of the size of the problem: \(n \approx 500\).   Data Instea ..read more