18 votes

Can the (famous) "Problem of Apollonius" be Considered as a "Constraint Optimization" Problem?

You have the inputs and outputs confused. The three black circles are given, and the purple circle is a desired output. But, yes, any system of equations can be thought of as an optimization problem ...
user avatar
  • 21.7k
14 votes
Accepted

No "not equals" constraint in Gurobi

If you want $x_1\neq x_2$, you can linearize $|x_1-x_2|\ge \varepsilon$, where $\varepsilon$ is your tolerance. You can do this by introducing a boolean variable $y=1$ if and only if $x_1-x_2\ge \...
user avatar
  • 10.1k
11 votes

Gurobi: how to add a constraint to make there be only one non-integer value

Let $x_{p,\ell}$ be the continuous variables in your table. Introduce integer variables $y_{p,\ell}$ and binary variables $z_{p,\ell}$, and impose linear constraints \begin{align} -z_{p,\ell} \le x_{...
user avatar
  • 21.7k
10 votes
Accepted

How to model: If $X\ge\epsilon$ then $X\ge Y$

Introduce binary variable $Z$ and linear constraints \begin{align} X - \epsilon &\le (\bar{X} - \epsilon) Z \tag1 \\ Y - X &\le (\bar{Y} - 0) (1-Z) \tag2 \\ \end{align} Constraint $(1)$ ...
user avatar
  • 21.7k
9 votes
Accepted

Two equivalent soft constraint implementations

Using the max operator, your objective function has directional derivatives but is not smoothly differentiable. For instance, if $x$ is scalar and $g(x) = x-2$, then at $x=2$ the max term has ...
user avatar
  • 28.8k
8 votes

How to make following constraint a convex one?

The constraint is not convex, and is not transformable to a convex constraint without substantively changing it. The additive linear term $dx$ is irrelevant to convexity. So let's ignore it and look ...
user avatar
8 votes
Accepted

Complicated constraint with logical operators in PuLP

Suppose your two arrays are indexed by $I$ and $J$, and let $x_i$ be the binary variable. zero or one elements may be selected from first array: $$\sum_{i\in I} x_i \le 1 \tag1$$ zero, one, or many ...
user avatar
  • 21.7k
8 votes
Accepted

How to transform a (thermal) range constraint into the objective function

Introduce nonnegative variables $Z^+(t)$ and $Z^-(t)$, impose linear constraints $$T_\min \le T(t)-Z^+(t)+Z^-(t) \le T_\max,$$ and minimize $$\sum_t (Z^+(t)+Z^-(t)).$$ Notice that this approach easily ...
user avatar
  • 21.7k
7 votes
Accepted

if $x = 0$ then $y \ne b$

Introduce binary variables $z_1$, $z_2$, and $z_3$, and impose linear constraints \begin{align} z_1+z_2 +z_3&= 1 \tag1\\ 1z_1+bz_2+(b+1)z_3 \le y &\le (b-1)z_1+bz_2+Uz_3 \tag2\\ z_2&\le x\...
user avatar
  • 21.7k
7 votes
Accepted

How to model a non-overlap constraint between 2 groups of tasks?

within CPLEX you could try CPOptimizer and use intervals. In OPL (One of CPLEX API) you could write ...
user avatar
7 votes

How to model a non-overlap constraint between 2 groups of tasks?

One simple approach is to impose the classical non-overlap constraints for each pair of tasks for which one task is in $T_1$ and one task is in $T_2$, as shown here.
user avatar
  • 21.7k
7 votes
Accepted

The importance of evaluating the number of constraints

In academic publications (where the point is to present a model and possibly computational scheme to solve an actual problem) I typically do not bother to count the constraints. First, the reader can ...
user avatar
  • 28.8k
7 votes
Accepted

If-then condition formulation to avoid variable multiplication

Something like: $$\begin{align} & c_i \le x_i + M(1-y_i)\\ & c_i \le My_i \end{align}$$ $M$ can be interpreted as an upperbound on $c_i$. If you don't like the big-$M$'s, consider using ...
user avatar
7 votes

Quadratically constrained convex optimization

For all things convex, Mosek's modeling cookbook and conic modeling cheatsheet have you covered. In your case, see the section on convex quadratic sets.
user avatar
  • 3,253
6 votes

Operator error in operating cost model constraint

Integer programming models solved by CPLEX (or most other solvers) require linear or, in certain very limited cases, quadratic constraints. Your constraint 9 involves dividing a parameter (...
user avatar
  • 28.8k
6 votes
Accepted

Constraintlist with two Options Pyomo

A variable that can assume values of zero or between some lower and upper bound is called a semi-continuous variable. Most high-end solvers have direct support for this type of variable. If not ...
user avatar
6 votes
Accepted

How do constraints become redundant in a Big-M conjunction?

If $y^s_{fg}=1$, then $y^s_{gf}=0=x^s_{fg}$. So the right-hand sides of (ii), (iii) and (iv) become $-M$ (think $-\infty$ here), which means any values of the left-hand side variables will satisfy ...
user avatar
  • 28.8k
6 votes
Accepted

Model generation for large-sized instances

I suggest three major changes: Omit the $y$ variables. Replace the $a_{p,j,t,i}$ variables with $a_{p,j,t,i,n}$. Instead of pairs of jobs, consider much larger subsets of jobs. The resulting ...
user avatar
  • 21.7k
6 votes

How to put this restriction using Gurobi in python

Firstly, your constraint should rather look this this: $$\sum_{j=0}^{i}X_j \leq H_i \quad \forall i \in I$$ $$\sum_{j=0}^{i}X_j \geq L_i \quad \forall i \in I$$ In your code this should translate to: <...
user avatar
  • 564
6 votes

Modeling an either-or-constraint

Based on the clarification about regions, it seems that all you have to do is add the constraints $$x_{ij}=0\quad\forall i\in I,j\notin J.$$ How to handle the "treat it differently" part may ...
user avatar
  • 28.8k
5 votes

Linearise $\max\{ y_{t-1} + a_t - z_t ,0\}$

If you are maximizing $y_t$ (or any increasing function of $y_t$) and using "standard" inequalities, you need something to preclude the solver from setting $y_t$ to $+\infty$. You can use ...
user avatar
  • 10.1k
5 votes

Show the total unimodularity of constraints matrix

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\}$.
user avatar
  • 21.7k
5 votes
Accepted

Constrain Mixed-Integer problem such that a graph is fully connected

If you are looking for a way to ensure (in a MILP model) that a graph with $p$ nodes is connected, a common approach is to treat each edge as a pair of directed edges (adding flow variables $x_{ij}$ ...
user avatar
  • 28.8k
5 votes

Regularization in Machine Learning : Constraint Optimization in Disguise?

Yes it is incorrect to refer to a unconstrained optimization problem as a constrained optimization problem. The idea of putting constraints into the objective is a often used technique. Example one ...
user avatar
5 votes

Can the (famous) "Problem of Apollonius" be Considered as a "Constraint Optimization" Problem?

Since I can't comment due to lack of reputation, here's an a note in response to your comment on RobPratt's answer: The difficulty is not so much in managing to draw something close to the desired ...
user avatar
5 votes
Accepted

Robust way to implement $(x=0) \Rightarrow (y=0)$, with $x$ nonnegative and $y$ binary

Equivalently, you want to enforce the contrapositive $y = 1 \implies x > 0$. The standard approach is to introduce a small constant tolerance $\epsilon > 0$ and enforce $y = 1 \implies x \ge \...
user avatar
  • 21.7k
5 votes
Accepted

Modeling an either-or-constraint

You can introduce an additional binary variable $y$ that takes value $1$ if and only if at least one node from $I$ is matched with another one from $J$: \begin{align*} x_{ij} &\le y \quad \forall ...
user avatar
  • 10.1k
4 votes
Accepted

How to specify an objective function that prohibits trading in both directions linearly

Yes, you can drop the big-M constraints and the binary variables, if there are no other constraints involving $\sf varWaterIn$ and $\sf varWaterOut$. Note that if you take any optimal solution and ...
user avatar
  • 28.8k
4 votes
Accepted

Lot-sizing problem variant

You could try and get rid of variables $Y_{p,t,j,c}$: remove constraints $(6)-(7)$; constraints $(6)$ simply link $x$ and $Y$ variables, so removing them should not have any impact on the feasibility ...
user avatar
  • 10.1k
4 votes

How to model a non-overlap constraint between 2 groups of tasks?

I assume for you have a binary matrix $S_{i,t}$ (tasks)$\times$(time steps) which tells you whether some task $i$ is active at time $t$. This approach introduces additional variables unless you have ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible