Questions tagged [optimization]
For questions involving mathematical problems that aim to minimize or maximize some objective function, possibly subject to one or more constraints.
428
questions
4
votes
1answer
100 views
maximum number of BoolVar 's before or-tools is no longer feasible to use
The standard nurse scheduling problem which is used as an example for OR-Tools (see for example https://developers.google.com/optimization/scheduling/employee_scheduling) attempts to assign boolean ...
4
votes
1answer
90 views
Clustering a large ride-matching problem
Background: We are solving a large scale vehicle to person ride-matching problem. The problem is essentially simple (match every person with a vehicle, if possible), yet the problem size is quite ...
4
votes
1answer
70 views
the set of optimal solutions of a linear programming (LP) problem as a mapping of right-hand side
Consider a linear programming (LP) problem
\begin{align}
M(b) \in \arg\min_x \{ c^\top x : Ax=b, x \ge 0 \}.
\end{align}
Suppose the LP is feasible and bounded for all values of $b$. We know that $M(...
4
votes
1answer
152 views
Combinatorial Optimisation, Allocation problem
I am trying to solve a problem (in pyspark/ python) where I need to find two distinct values to allocate, and how to allocate them in a network of stores.
The two distinct values can only be integer ...
4
votes
1answer
231 views
Creating an Optimisation Problem to Optimise Water Flow
A water tank needs to be refilled with an electric pump when the water level gets below a certain level. The pump can operate at variable flow rates. Further, there is a time-variant electric billing ...
4
votes
1answer
47 views
Greedy algorithms for assignment problems — prediction doesn't match simulation
I'm considering the following basic assignment problem: a group of $n$ people is to be assigned, in one-to-one fashion, a set of $n$ jobs. Write $C_{ij}$ for the cost incurred when person $i$ gets ...
4
votes
1answer
92 views
how to apply Big M to model the logic constraint （if-then-else）
I was hoping to get some help in modelling the following logic as an MIP Constraint
c_{m,l}^{RC} is binary decision variable.
Simplify it：
4
votes
2answers
70 views
How to decide between a inaccurate system and a accurate system with capacity constraints to do a stream of jobs
Let's say you have a list of at most N Jobs to be done which are coming in a stream. There are two kinds of systems that can do the job:
System 1: A very fast system, which however, only does the job ...
4
votes
1answer
87 views
How to convert non-normal probabilistic constraints to deterministic ones for mathematical modelling?
I am working on a chance-constrained optimisation model that takes into account uncertainty. I am aware of how to convert constraints that are of a probabilistic nature into the equivalent ...
4
votes
1answer
64 views
Optimize probability parameter in an optimal control problem
We have a game with infinite but countable rounds. We have one machine, that may either break down, or continue operating. For each round the machine operates, it gives cost $-1$ (so profit of $1$). ...
4
votes
1answer
47 views
Access LpVariable as input to another Keras sequential network
I want to use LpVariable as an input argument to a sequential CNN network layer, which is in Keras. When I tried to call the function I got the error as follows:
<...
4
votes
1answer
75 views
How would you linearize this scheduling problem? Or how would you solve this? It is variation of a set coverage problem for OpenSolver
So, it's been about 15 years since I took my OR class in college. I'm not versed in any programming language besides a little bit of VBA.
A client of mine is looking to solve the following problem. I ...
4
votes
1answer
227 views
PuLP Transport Problem - How to add outcomes of decision variables together
I am working on a rail scheduling problem that moves product from a production plant to a storage facility to satisfy demand. I am new to PuLP so finding this difficult to understand why this isn't ...
4
votes
3answers
166 views
Problem Clustering and Suggestions for Solving it (Job-Shop?)
I am trying to find the amount that an item may get produced.
To produce this item I need casting-molds. A casting-mold can be used multiple times after it becomes available again.
For the ...
4
votes
1answer
256 views
XOR constraint representation
In an scheduling optimization problem, for job $l$, $\xi_l$ is binary variable that $\xi_l=1$ shows job $l$ is selected. $t_{r,l}$ and $t_{e,l}$ are registration time and time that job is completed. ...
4
votes
1answer
256 views
Machine Allocation & optimal Utilization using python
Problem statement: Meet the demand which can be met across 2 facilities each having multiple machines where several components are made. The objective is to find the optimal solution to meet the ...
4
votes
0answers
77 views
Fast solvers for LASSO-type non-convex optimization problems
Given $y \in \mathbb{R}^{n \times 1}, X \in \mathbb{R}^{n \times p}$, $p > n$, assume a LASSO-type optimization problem in the form of
$$ \hat\beta=\underset{\beta}{\operatorname{argmin}}\frac{1}{2}...
4
votes
0answers
53 views
Identifying saddle point in constrained optimization
Suppose we are minimizing $f(x)$. The first order necessary condition of $x^*$ being local minmum is:
$$\nabla f(x^*)= \mathbf{0}.$$
For sufficiency, we check if also $\nabla^2f(x^*) \succ 0$, i.e., ...
4
votes
0answers
50 views
Confused in how to insert a slack variable in a constraint inequality
According to my understanding, we should put a slack variable to equate an inequality constraint by inserting the slack variable in the side that is less than the other side. For example, if we have $...
4
votes
0answers
50 views
Instructors optimized schedule task
I'm trying to solve one interesting math task.
Let’s imagine we have a number of instructors with different timespans during the day in which they work or they are available. We need to display to ...
4
votes
0answers
40 views
Help with constrained or regularized optimization problem involving variable matrices and powers of matrices (or perhaps matrix logarithms)
I am attempting to solve the following optimization problem:
$$
\small\min_{A,B,C} \| Y_A - AX_A \|_F + \| Y_B - BX_B \|_F + \| Y_C - CX_C \|_F + \lambda_1 \|B - A^2\|_F + \lambda_2 \|C - A^4\|_F
$$
...
4
votes
0answers
63 views
Continue on “Is there a known MILP to schedule routes after routes are made”
I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made).
I have derived the sets of the problem, which are:
1) Itineraries of vehicle: $i \in ...
4
votes
0answers
573 views
4
votes
0answers
191 views
How can I formulate this multi-objective optimization problem?
Now, for each system $X$ $(X=A,B,C,E)$, my objective is
$$\max\min\frac{s_{x_u}}{d_{x_u}}$$
here, $x=a$ for system A, $x=b$ for system B and follows...
and for the whole system, my objective is
$$\max\...
3
votes
3answers
640 views
Does adding constraint to an optimization model make it solve faster?
Some say adding constraints cuts the feasible region smaller hence the same solver terminates faster due to the less search effort. Others say it adds more complexity to the problem and it may take ...
3
votes
3answers
194 views
How to handle an equality constraint in metaheuristic algorithms (like GA, PSO)?
Metaheuristic algorithms are generally used to find the optimal solution to unconstrained optimization problems. I would like to maximize $x_1+3x_2-x_3\ge0$ while respecting the equality constraint $...
3
votes
2answers
682 views
Fast algorithm for Transportation Problem in Python?
The Transportation Problem can be solved with a simplex algorithm, but it's time-consuming.
I'm wondering if there exists a specific Python-implemented algorithm with low complexity.
3
votes
1answer
311 views
Simplex (GLPK) doesn't find a feasible solution on this simple assignment problem, but there is an obvious one
Problem
Assign 11 projects to 11 students, based on their preference.
For this example, each students chooses only one project, for simplicity shake (as shown below). Student 1 one chooses project 1, ...
3
votes
2answers
114 views
Minimizing a variable over the intersection of simplex and linear constraints
I am solving:
\begin{align}
\begin{array}{rll}
y^* = \min & y & \\
\mathrm{s.t.} & a_i^\top x \leq y, & i=1,\ldots,m \\
& x \succeq 0,\ \mathbf{1}^\top x = 1. &
\end{array}
\...
3
votes
2answers
223 views
Convexity of a function
I would like to show that this function
$$2x^2 + 8y^2$$
is convex or concave by using the definition
$$f(θx+(1−θ)y) \le θf(x)+(1−θ)f(y)$$
From my understanding, using the Hessian matrix, I believe ...
3
votes
1answer
113 views
How to write a LP/MIP to mark the items in a time-series list after a fixed delta?
I have a time series list like this.
...
3
votes
2answers
117 views
Summation of all links that contains nieghbors to certain node in Graph
I'm trying to model a constraint in Python using Pulp and networkX that is getting the sum of the edges that contain this node over all the nodes. The constraint can be like that:
$$\sum_{m\in\cal N}...
3
votes
1answer
160 views
Issue in solving a large scale MIQP problem
I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below.
\begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}...
3
votes
2answers
145 views
Decision variable transformation in Gurobi
I'm trying to find a way of setting the values of a binary MVar object (which is my decision variable) of size n to {-1,1}. Right now I have a vector that can either take values 0 or 1 (due to binary ...
3
votes
1answer
104 views
Find a particular optimal solution
After writing an integer linear program in AMPL, I solved it using CPLEX. Now, I have some variables that must necessarily be 1, others that must necessarily be 0 and finally it is possible that some ...
3
votes
3answers
260 views
SLSQP Optimisation loop takes several iterations to compute error function despite jacobian
I have an error function $f : w \rightarrow f(w)$ that I want to minimize, $w$ being a vector of length 211. There are some constraints on $w$.
I managed to compute the jacobian $J$ and even with it ...
3
votes
1answer
239 views
Iterative calculus with Excel
I have this model:
\begin{align}\max&\quad\small{(0.2(1.07)^{-1}+0.2(1.07)^{-2}+0.9(1.07)^{-3})x_A+0.4(1.07)^{-1}+0.5(1.07)^{-2}+0.3(1.07)^{-3})x_B}\\&\quad 0.2x_{A}+0.4x_{B}\geq300\,000
\\&...
3
votes
1answer
61 views
How to assign values to array in CPLEX with C++?
I am new to CPLEX. I am using CPLEX with Xcode in macOS.
I have three arrays (known parameters used in optimisation) which I define as
...
3
votes
1answer
148 views
How do I interpret the CPLEX Optimization Studio MIP gap output?
I'm having difficulties understanding my FlowControl output compared to what the Engine Log shows me.
My output from the FlowControl into the Scripting Log (yellow marks) is ...
3
votes
1answer
82 views
Which method to use to solve this multi-objective conflicting objectives
I have the following multiobjective problem.
I need to minimize the user-perceived latency while doing so aggressively minimizing user-perceived latency generates large switching cost (Reconfiguration ...
3
votes
2answers
185 views
Optimal way of connecting N sensor to M devices in polynomial time?
Let's say I have 3 type of sensors: A, B, C. These sensors can be connected to multiple devices at the same time: let's call them dA, dB and dC. Now, device dA can only accept connections of sensor of ...
3
votes
1answer
44 views
defining Mixed integer linear inequalities for a set of variables
The problem is described as follows:
considering $n$ variables which are continuous and bounded such that
$$L_i \le x_i \le U_i\quad \forall i=1,2,\dots,n.$$
How can i define a set of mixed integer ...
3
votes
1answer
91 views
What are the flow based formulations?
What are the flow-based formulations? For what optimization problems are they applied, and in which form? Which are the specificities of such a formulation?
Also, the same question for the time staged ...
3
votes
1answer
72 views
Sum of links neighbors in a graph
I'm trying to model this constraint in an optimization problem using Pulp and NetworkX. Here is a piece of code I'm using.
...
3
votes
1answer
183 views
How to optimize a utility function that contains step function?
I have an optimization problem with an uncommon utility: to find a $\beta$ that maximizes
$$
r^{T}\cdot H(X\cdot\beta)
$$
where $H()$ is a Heaviside step function as in wiki
$r$ is a vector of size ...
3
votes
2answers
135 views
Limit number of switches in employee scheduling problem
Here is a scheduling problem I need to solve. Given the demand for 2 positions in 1 week with 3 shifts per position, I need to allocate the employees accordingly with some extra operational ...
3
votes
1answer
130 views
Resource constraint with MIP model
My question is how to model a resource constraint with MIP model
(how should I modify it?)
A factory is making blocks. If there is space left at that time, the block can be assembled.
(If the factory ...
3
votes
1answer
96 views
Radial unboundedness vs convexity
We have a simple problem, namely minimizing:
$$f(x) = x_1^2 + x_2^2 - x_1.$$
The gradient is $$\nabla f(x) = \begin{bmatrix} 2x_1 - 1 \\ 2x_2 \end{bmatrix},$$
hence the unique stationary point is: $...
3
votes
1answer
100 views
Graphical illustration Excel
I have formulated a linear optimization model and solve it using the Excel Solver.
How can I illustrate the slacks vs usage?
3
votes
1answer
57 views
Iterative calculus with Excel - N° 2
In continuation with the previous post, I propose you another problem.
I have this model:
\begin{align}\min&\quad F\\\text{s.t.}&\quad
F-(1150x_{B_{1}}+1000x_{B_{2}}+1350x_{B_{3}}-S_{1})=430\...
