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
3
votes
2answers
94 views

Let $A\in\mathbb{R}^{m\times n},c\in\mathbb{R}^n$. Show that exactly one of the following two systems is feasible:

Let $A\in\mathbb{R}^{m\times n},c\in\mathbb{R}^n$. Show that exactly one of the following two systems is feasible: $Ax\geq0,x\geq0,c^Tx>0$ $A^Ty\geq c,y\leq0$ Assume that A is feasible meaning $...
3
votes
1answer
85 views

Bioinformatics / Genomics Optimization Problems?

I am a third year bioinformatics student and would like to apply my knowledge from an introductory course in Optimization Methods to some problems in the field of genomics or bioinformatics. Do you ...
3
votes
1answer
132 views

Multiple Knapsacks with splitting

I am trying to solve a problem that I believe is a variation of the multiple knapsacks. Like the classical multiple knapsacks problem, I have a set of items, each one with a weight and a value and I ...
3
votes
1answer
44 views

Feasible sets represented as point clouds

Does the situation in optimization ever occur in which you have a problem whose feasible set is not described in terms of explicit algebraic equations, but instead you have a large set of points that ...
3
votes
1answer
55 views

What is the difference between min- cut formulation and (bi) partitioning formulation?

I have a min-cut formulation and a bi-partitioning problem. The two problems focus on finding the minimal cut value separating the two partitions? So what are really the differences between the ...
3
votes
1answer
169 views

Pyomo add constraint error: Rule failed when generation expression for constraint

I am trying to solve a model with Pyomo and struggling with indexing. Below is a simple problem instance, where you can also see the error. The message is straightforward and self-explanatory but ...
3
votes
1answer
107 views

How to transform these conditional constraints to linear integer ones in a more efficient way?

The conditional constraints A and B can be transformed to a set of linear integer constraints as follows: A) $\text{if} \ x_1=0 \ \text{then} \ d_1=1 \ \text{else} \ d_1= 0\\ x_1\in {\rm I\!R}^{\geq ...
3
votes
1answer
185 views

Cplex : The cutting stock problem

The problem below aims to minimize the cutting leftovers from each cut : A company manufactures desks for kids gardens and primary schools, colleges and high schools. The leg of these deks all have ...
3
votes
1answer
98 views

Can Deep RL be used to find optimal division point in an application?

I need to optimise the end-to-end latency for a multi-service application while distributing it on multiple devices. The application is a series of services interconnected to each other. The goal is ...
3
votes
1answer
115 views

How to optimize with “if” constraints

The minimizing problem is the following : $$ \underset{w}{\operatorname{argmin}} \sum_{i=1}^{n}\left[w_{i}\times (\frac{Vw}{\sigma})_{i} - b_{i}\right]^{2}$$ with $V$ a $n\times n$ matrix (covariance ...
3
votes
1answer
44 views

Is Multidisciplinary Design Optimization / Collaborative Optimization used anywhere outside of the Mechanical Engineering context?

I recently stumbled across the concept of Multidisciplinary Design Optimization (MDO), sometimes referred to as Multi-Disciplinary Optimization or Multidisciplinary Systems Design Optimization (MSDO), ...
3
votes
1answer
96 views

What kind of scheduling problem is this?

I am trying to develop algorithm to solve following basic version of the problem. 1) I would like to know what this problem is called in literature so that I can look it up 2) What are efficient ...
3
votes
1answer
252 views

Linear programming sensitivity analysis using Matlab

I have a linear program in the MPS file format listing all the rows, columns, right-hand sides, etc. I can read that in Matlab and solve it using linprog. However, it seems there is no easy way to do ...
3
votes
0answers
30 views

PuLP Python: How to linearize an inequality involving an integer variable

I am working on a Copper payables problem where the objective function is to maximise the sum of copper payable over a time period, T. The total amount of payable tonnes i.e. what the customer will ...
3
votes
0answers
50 views

Where I can study some job shop scheduling by course (video )?

I am seeking the help to know where I can study the job shop scheduling Heuristics or using solver by some course/video as I see some of books and papers hard to understand . It is hoped that the ...
3
votes
0answers
64 views

“Rank 1” type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?

Suppose $X\in\mathbb{R}^{m\times n}$, $v\in\mathbb{R}^m$, $w\in\mathbb{R}^n$ are variables from an optimization problem, which also includes the constraints: $$0\le v\le a$$ $$0\le w\le 1$$ $$w_1+\...
3
votes
0answers
31 views

R ompr MILPModel array multiplication?

In R, I regularly ompr::MILPModel for optimization. I adapt the below snippet to enable multiplication of a decision variable with two dimensions (e.g., x[i,j] ) ...
3
votes
0answers
50 views

Flexible Job Shop with Preemption

I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
3
votes
0answers
49 views

What are the efficient ways to model this scheduling problem and ways to improve running time

There are $N - \{1 \ldots N\}$ jobs, each with processing time $p_j$, to be scheduled on $M - \{1 \ldots M\}$ machines over span of $D - \{1 \ldots D\}$ days and while working $T - \{1 \ldots E \ldots ...
3
votes
0answers
33 views

Constraint equivalence in PuLP

I'm working on an optimization problem in PuLP and I have to enforce a daily minimum of shifts and a daily maximum of assigned shifts. I have the following constraints to ensure each day has a minimum ...
3
votes
0answers
38 views

Best method to optimise the blending of different types of coal to ensure all quality parameters are met at the lowest possible price?

I am looking to optimise the blending of different types of coal for the coke making process of a steel plant. I want to take into account the statistical variation of each coal’s qualities, so for ...
3
votes
0answers
60 views

Integer variable optimization - decreasing execution time

I have a variable declared as follows in AMPL: ...
3
votes
0answers
46 views

Discrete optimization in transport economics

I was working on a problem in transport economics where the optimal number of trips in a given duration of time is to be found out. The profit is a function of the price vector $p$ and time cost $c$ ...
3
votes
0answers
67 views

How can I do this in GAMS?

I am mimicking a GAMS model that was introduced in Soler et al. (2013)1 to compare my new model with its results. In a nutshell, assume we have a variable $t$ that is supposed to only take certain ...
2
votes
2answers
230 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 ...
2
votes
3answers
332 views

Find the farthest point in hypercube to an exterior point

Let $\mathcal{U} = \{ [x_1, ..., x_n] \in \mathbb{R}^n : 0 \leq x_i \leq 1\}$ be the unit hypercube and $C \in \mathbb{R}^n\setminus\mathcal{U}$ fixed. Let us consider the following problem $$ \max_{X ...
2
votes
3answers
266 views

Why can quadratic functions over polyhedrons be minimized exactly in finite time?

I have heard it said that QP problems $$\min f(x) = \frac 12 x^TAx + b^T x$$ $$x \in P$$ where $A$ is a symmetric matrix and $P$ is a polyhedron can all be solved exactly and in finite time (or it can ...
2
votes
4answers
82 views

Linearity of an optimization problem which comprises the product of variables with constant values from a non-linear function

In a mathematical integer optimization problem, if the objective function is represented as $\sum x_k \cdot M_k$, where $M_k$ is a non-linear function whose value is known and just plugged in to the ...
2
votes
3answers
166 views

Are there any standard “tests” that determine if a model will not optimize / no solution?

As the title says, what are the tests for optimality or non-optimality I can build into my procedure and code to alert me that the model is going to be infeasible so I need to revise my constraints? ...
2
votes
1answer
419 views

How to learn Optimization?

I am a 2nd year PhD student in a (mostly) pure Mathematics department. I do not have any prior experience in applied mathematics, but I've recently had a change of heart and decided to study ...
2
votes
1answer
81 views

Looking for a similar optimization problem

I want to know if there is any already defined problem that could give me a hint on how should I approach the following task. There are N tasks that should be accomplished, each task requires ...
2
votes
1answer
114 views

Reduction of Unnecessary Parameters and Variables in an MIP

Let's observe an example constraint: $\sum \limits^E_{e\ \in \ A_a \ \cap \ B_b \ \cap \ C_c} x_{e,a,b,c} \geq n_{a,b,c} \; \; \; \forall a \in A,b \in B,c \in C$ with $e \in E$ an element and $A_a$ ...
2
votes
1answer
81 views

Converting evolutionary optimization problem from Excel to Python

I've set up and successfully executed an evolutionary optimization in Excel, and now have a need to convert the problem to Python. differential_evolution() in the ...
2
votes
1answer
106 views

How can I perform discrete optimisation of a variable over a data set

This question relates directly to a dataset I've generated for Fantasy Premier League, but I'm also curious how I can apply this to a more general case. Data I have a list of premier league players, ...
2
votes
2answers
135 views

Pyomo + Ipopt. Speed Issue

I am using Pyomo + Ipopt as solver to solve a NLP problem. The problem is not extremely complex in terms of dimensionality and ...
2
votes
1answer
307 views

Divisibility constraint in Integer programming

I have a simple question regarding the divisibility in integer programming suppose the objective function is $\text{max}\quad x_1 + x_2$ where the constraint is that the sum of $x_1$ and $x_2$ are ...
2
votes
1answer
105 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+...
2
votes
1answer
97 views

Defining and comparing utilization rates for delivery service

I'm currently working on a case for a food delivery service and wondered whether my notion of "driver utilization" makes any sense. My data set contains an hourly overview of the number of active ...
2
votes
1answer
68 views

Which is better to minimize w.r.t a lower bound or an upper bound of an objective function?

Suppose there is a optimization problem that aims at minimizing an objective function $X$ but we can't develop a mathematical model for minimizing $X$. However, there are two objective functions $Y$ ...
2
votes
1answer
40 views

Logical equivalencies to modeling an indicator decision variable in transportation problem

I am formulating a model that seeks to minimize the cost of shipping goods from factories to warehouses, where the cost of shipping is independent of the type or amount of goods being shipped (except ...
2
votes
1answer
74 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 <...
2
votes
1answer
51 views

Reformulating to locate the second largest decision variable of a set of decision variables

Consider a set of $A_{vn}$ decision variables such that $A_{v1},A_{v2},\cdots,A_{vn}<A$. While this is the standard formulation finding the maximum value of $A_{vn}$, I would also like to find the ...
2
votes
1answer
95 views

Problem with implementing squared terms in the objective function

I'm trying to implement either one of these objective functions, but I'm having a hard time with the squared terms. I'm attaching both so you can take a look at the structure and see if you can give ...
2
votes
1answer
146 views
2
votes
1answer
125 views

Representing Date Variables in Pulp

I am working on an optimisation problem that involves minimising shipping demurrage. I am struggling to model how to represent the difference, (x-y) between dates where the ship is ready to be loaded ...
2
votes
1answer
168 views

Does this problem fall into any common problem definition…Knapsack maybe?

I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My goal is to see if it ...
2
votes
1answer
70 views

What is the state of the art on the Weber problem?

I'm trying to get up to speed on the Weber problem. I'm very much not an expert, unfortunately. I would really appreciate recent literature recommendations / surveys / potted histories, however ...
2
votes
2answers
61 views

Parallel scheduling with precedence constraints and variable job length

I have $N$ jobs and $M$ machines and want to minimize the makespan, i.e. the total time to finish all jobs. Some jobs have precedence constraints and can only be started once other jobs are finished. ...
2
votes
1answer
56 views

How to build a GAMS model in python

I looked at the GAMS python API but the documentation only describing already predefined models (run .gms with some tweaking options). My question is now: Can I somehow build a gams model from scratch ...
2
votes
1answer
78 views

confusing results of two models with different complexity

i have two models that address the same problem. the first one is : the second one is: for different instances for the same size (n=30) i found the following results ( the first column on the left ...

1
5 6
7
8 9