Questions tagged [optimization]

For questions involving mathematical problems that aim to minimize or maximize some objective function, possibly subject to one or more constraints.

Filter by
Sorted by
Tagged with
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

cvxpy: Code that works for default solver doesn't work for cp.GLPK_MI

The following code works: ...
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
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\...

1
5
6
7 8 9