Questions tagged [optimization]
For questions involving mathematical problems that aim to minimize or maximize some objective function, possibly subject to one or more constraints.
402
questions
2
votes
0answers
37 views
Solving transportation problem by the Network Simplex
I am trying to solve the following problem using Network Simplex method. But I have questions.
My attempt:
Basis Matrix$(B)$
Rows: 1, 2, 3, 4, 5
Column: (1,3) (1,4) (1,5) (2,3) (2,4) (2,5)
$$
\...
2
votes
0answers
47 views
CPU time on Linux with Gurobi
I am solving a MILP model in C++ using Gurobi 10.1.
I retrieve the CPU time of my C++ program under Linux via the following commands:
...
2
votes
0answers
86 views
Prove Non-Homogeneous Farkas' Lemma
Let $A\in\mathbb{R}^{m \times n}, c\in\mathbb{R}^{n}, b\in\mathbb{R}^{m}, d\in\mathbb{R}$. Suppose that there exists $y\geq0$ such that $A^Ty=c$.
Question: prove that exactly one of the following is ...
2
votes
0answers
55 views
Node ordering in Graph optimization
I'm solving a network optimization problem which is modeled as a graph $G=(V,E)$. Solving this problem using Pulp and NetworkX in Python and ordering the graph's nodes in a certain order (i.e. (1,2,3,...
2
votes
0answers
26 views
MILP formualtion for Two-level minimum dominating set (MDS) problem?
I'm working on an optimization problem which is kind of finding the minimum dominating set (MDS) or the minimum vertex set (MVS) in an undirected graph. given the MILP formulation for both problems, I ...
2
votes
0answers
53 views
Reading MPS file for linear programming and reconstructing the Optimization model
Are you aware of any tutorial that can help me learn on how to reconstruct the objective function and constraints from a MPS file once it's loaded in MATLAB. I can load the mps file given to me and ...
2
votes
0answers
25 views
MDP model for a unique system
Let's assume that we have a system where there are two exogenous factors, name $a$ and $b$, that can affect the system state. At each decision epoch either $a$ or $b$ occurs and it is not possible ...
2
votes
0answers
34 views
Interger programming using gray encoding
Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
2
votes
0answers
33 views
Optimization of strongly convex functions with approximate evaluations of gradient and Hessian
Suppose I want to find the minimum of a differentiable, strongly convex function $f:\mathbb{R}^n\to\mathbb{R}$ with constant $\mu>0$. That is, for all $x,y\in\mathbb{R}^n$, I have that:
$$f(y) \geq ...
2
votes
0answers
143 views
Operation hours optimization for circular schedule
Here is my problem. A store has X = 15 electical devices with the ability to work non-stop, fully charged, up to 8 hours. Their battery charge lasts 2 hours and the operating hours of the store differ ...
2
votes
0answers
42 views
Decision-making algorithm for dynamic load balancing
I'm researching a subject of balancing the load between two black-box systems (with some twists). I thought that I could record latest response time log from each of those systems and process such a ...
2
votes
0answers
62 views
Density Optimization by Fitting an Circle to a Field - Monte Carlo Method
Given: I have 2D non-parametric formula that provides instantaneous intensity at certain (x,y) location.
Required: I want to en-circle a region where the density is high via optimization. In other ...
2
votes
0answers
55 views
Weapon Target Assignment Problem + Time Windows
So I am very familiar with the WTAP it the static case. What I am wondering, is there a formulation that has "time windows" as well? Let's say you have some weapons and some targets, you know the ...
2
votes
0answers
61 views
How to solve an LPP with summation
Up until this point I have only solved simple LPP problems with maybe 2 to 3 variables that looked like this, using pen and paper.
I need to solve
This Problem using Simplex, Dual Simplex, Big M and ...
2
votes
0answers
60 views
Problem classification: optimal weights for Weighted Arithmetic Mean
I want to write an optimisation problem then solve it, to get optimised weights to compute a final score using a weighted arithmetic mean.
The problem is as follows. I have an entity (an input vector ...
2
votes
0answers
65 views
How to find minimum number of locomotives to cover maximum miles in a network?
I have a freight train dataset with details like locomotive type, substations it passes through, trip date, travel miles, etc. There are 5 locomotive types in the dataset, and each type has 20-30 ...
1
vote
2answers
193 views
Hard to soft constraint
What are all necessary changes to the below model so that constraint set $(2)$ becomes soft?
Give the new full model. $\alpha_{ij}$ are parameters. Eqn. $(1)$ refers to an already existing function of ...
1
vote
1answer
620 views
How to describe the traveling salesman problem with an integer programming model?
I'm trying to describe the travelling salesman problem as an integer programming model. I'm interested in the asymmetric version of the problem. The problem can be summarized as finding the optimal ...
1
vote
2answers
357 views
Solving a (Non-)Linear Programming Problem
Apologies for my basic question, but I am kinda new to optimization methods, and I am bumping into the optimization problem below:
$\min_{x} (c_1 \cdot u_1 + c_2 \cdot u_2)\\
\mbox{subject to:}\\
...
1
vote
1answer
212 views
How to allow multiple assignments for jobs in Hungarian Algorithm?
In the Hungarian Algorithm, the assignment for a bipartite graph considers the restriction of assigning a single job to a single person for example. Can this restriction be relaxed? I would like to ...
1
vote
1answer
36 views
Enforcing discontinuous range for a variable
I want to enforce the following ranges for a set of variables, where the ranges for each variable are discontinuous. For example, I have two sets of ranges for each variable,
\begin{align}\sf LB_1 &...
1
vote
1answer
81 views
How to prove this convex-optimization problem?
I am struggling with the following optimization problems.
Problem 1
\begin{align}\max_{\alpha, s_1, s_2}&\quad s_1 + s_2 - \gamma (s_1 (K_1 +c_1 + s_1) + s_2 (K_2+ c_2 + s_2) + 2\alpha K) +C\\\...
1
vote
1answer
90 views
How can I have minimum amount of resources wasted in this resource allocation problem?
I have a demand, $d$
I also have supply from 1000 sources. The supplies from those $N$ (for example, $N=1000$) sources are given by
$s_1,s_2,s_3,\cdots,s_N$. So,the total supply is : $s_1+s_2+\cdots+...
1
vote
1answer
104 views
How to balance the workload of teachers in OR-Tools (maximization of the minimum)
I am very new to optimization and OR-Tools. I am trying to solve a very simple question.
Let's assume that we have $n$ students. Each student needs to be assigned to only one teacher as a supervisor. ...
1
vote
2answers
202 views
Pulp: slack variable to identify & measure extent infeasible in supply problem
I am currently modelling a supply problem that attempts to optimise a rail schedule which moves products from a production plant, to a warehouse to satisfy sales.
The model is working fine (thanks in ...
1
vote
1answer
50 views
Formulating “more complicated” objectives in Python Gurobi
I am currently learning how to use Gurobi for Python using their official tutorial found here. In this example, they appear to formulate the objective by simply specifying a cost dictionary to the <...
1
vote
1answer
59 views
KKT for second order approximation of $f(x)$
Let $f: \mathbb{R}^n \rightarrow \mathbb{R}.$ Consider second order approximation $f(x) \approx f_0(x)$ where $$f_0(x) = f(x_0) + \nabla f(x_0)^T (x-x_0) + (\mathrm{H}f(x_0)(x - x_0))^T(x - x_0)$$ ...
1
vote
1answer
150 views
How do I solve this Optimization problem?
Optimization of a simple expansion problem
minimise:
$$
\sum_{t=1}^{5}\left[\sum_{i=1}^{2}x_{i,t}CC_i\left(\frac{1+EIC}{1+r}\right)^t+UE_t*C_{UE}\right]
$$
subject to:
$$
0 \leq x_{i,t} \leq 5 \\
...
1
vote
1answer
74 views
What kind of job shop scheduling problem is this and how do I solve it?
I have a production planning / scheduling problem, which I believe is a kind of job shop scheduling problem.
But I would like to get some input on what kind of job shop scheduling problem it is and ...
1
vote
1answer
125 views
Pulp Python: How to formulate a time-based variable for shipping demurrage
I am working on a shipping optimisation problem that aims to minimise demurrage charges as a result of low/insufficient inventory.
I have daily vessel requirement (sales) data in the format ...
1
vote
1answer
54 views
How to get detail about 'OptimizationStatus.ERROR' in MIP module in Python?
I am using MIP (Mixed Integer Programming) module in Python to solve one of my optimization problems. for some of the scenarios, model returns "ERROR" (OptimizationStatus.ERROR) status after ...
1
vote
0answers
31 views
How to start the Dantzig-Wolfe decomposition?
I have the following problem: \begin{align}\min&\quad3x_1+5x_2+3x_3-2x_4+3x_5\\\text{s.t.}&\quad x_1+x_2+x_3+x_4\geq3\\&\quad3x_1+x_2+5x_3+x_4-2x_5\geq6\\&\quad x_1+2x_3-x_4\geq2\\&...
1
vote
0answers
75 views
Linearization of constraints with square root
I am trying to solve an optimization programming model involving a non-linear constraint with a square root. It follows (in a simplified form): $X_i\ge\sqrt{A_i/B_i}$ where $X_i,A_i,B_i$ are positive ...
1
vote
0answers
93 views
How to develop a vehicle routing optimization package? [closed]
I would like to know how vehicle routing software optimizes routes? In demos of this software, they provide the optimal (or a good) route in just a few seconds or minutes with several nodes (maybe 50 ...
1
vote
0answers
44 views
$\nabla_y\nabla_vf(x^*)\geq0$ for any concave $f$ if and only if $y=-v$
$f:\mathbb R^3\to\mathbb R$ is an arbitrary concave function.
$H$ is a plane. $v$ is a given vector on $H$.
$x^*=\max_{x\in H} f(x)$
Prove that $\nabla_y\nabla_vf(x^*)\geq 0$ if and only if $y=-v$.
I ...
1
vote
0answers
38 views
Find minimum cost problem
The problem below aims to find the minimum cost for the network architecture:
We want to build a network where client terminals are connected to servers by cabling which is very expensive. The network ...
1
vote
0answers
80 views
Simplex - Network flow problem : Arc from 1 to P with infinite capacity
The Network - Maximum flow problem below aims to find the maximum flow using simplex method :
With the LP as follow :
LP : \begin{Bmatrix}
Z(Max) = \sum_{i=1}^{m} fi \\
Af =0
\end{Bmatrix}
...
1
vote
0answers
66 views
Ways to improve lower bounds while solving MIPs
What are the ways to improve lower bounds while solving a minimization problem (MILP)?
1
vote
0answers
85 views
How do I find the extreme rays and points for a stochastic programming problem
I have the following 2 stage Stochastic Programming program:
\begin{align}\min_x& \quad x+\sum_{s=1}^{3}p_sQ_s(x)\\\text{s.t.}&\quad x\in\Bbb R\\&\quad Q_s(x)=\min\left[\begin{pmatrix}1&...
1
vote
0answers
62 views
Combining Two Different Queues
I am trying to create an optimization model for a problem that involves two different types of queues. Given Poisson demand (for both), there is a queue with constant service time and another queue ...
1
vote
0answers
136 views
Optimal value exceeds actual value for a minimization problem [closed]
I am solving a nonlinear numerical optimization problem in Pyomo using Scip as a solver. The goal is to minimize a certain objective function. For certain input conditions, I notice that the solver ...
0
votes
2answers
197 views
How can I formulate this specific if-then constraint?
IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly)
AND
IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly)
$X$ and $Y$ are binary variables.
What I'm actually trying to do is to charge the ...
0
votes
1answer
74 views
How can I find the shortest path for all nodes in a graph from a source $s$?
This is the shortest path problem. I've used a model where we can find the shortest path between the source and a specified destination.
The idea behind this model is that we assign a flow of 1 for ...
0
votes
1answer
38 views
Adding slack nodes to min cost network flows
I have the following question. I want to clarify couple of points.
As you can see, total demand and total supply does not match, we do not have enough demand. What I want to ask is:
Do we need to ...
0
votes
1answer
47 views
How to deal with the sub-problem with zero reduced cost in D-W decomposition
The specific linear programme has an optimal solution as $x_1 = 0.66$, $x_2 = 1.33$, $x_3 = 12.2$,
$x_4 = 0.0$ and the objective value is $33.3$. While the problem is solved by D-W decomposition ...
0
votes
1answer
82 views
Does this objective function makes sense?
I am wondering if the objective function in the following problem makes sense. The question is posted in CrossValidated, stack exchange as well.
I know there is a physical system having an underlying ...
-2
votes
2answers
197 views
Some theories and laws of Operations Research? [closed]
Can I know some theories and laws of Operation Research which has being widely used nowadays?
-3
votes
1answer
86 views
Geometric interpretation of a Linear problem with bounded variables
I have a question of how to make a geometric interpretation of this problem
\begin{eqnarray}
\mbox{max} & z = 3x_1+x_3 \\
s.a: & \\
& \begin{array}{cc}
x_1+2x_2+x_3+x_4& =...
-4
votes
2answers
408 views
Are there NP hard problems solved in P time?
Does anyone know of a problem previously believed to be NP hard, to be solved nowadays in polynomial time optimally?
-4
votes
1answer
66 views
How to change a function from Min(F(x)) to -Max(-F(x))?
I have not a good knowledge in math field, I am working on multi objective functions, and I have two maximization functions, and one minimize function, where:
Max (X,Y) = X+Y
Max (L,M) = Sum (LC + MD)...
