Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
352
questions
8
votes
2answers
662 views
Linear optimization problem with user-defined cost function
I have a linear optimization problem for which I am looking for a suitable optimization solution that can fulfill my requirements. Here is an explanation of the optimization problem:
There are a ...
6
votes
0answers
63 views
Proof that the leaving variable cannot be selected as the entering one in the next round
Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
2
votes
0answers
61 views
Linear programming: extending problems yields non linearity
I had a linear programming problem with the following objective function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known. Let the term ...
1
vote
2answers
328 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 ...
5
votes
1answer
115 views
Physical Interpretation of a dual of an LP
I was recently asked to physically interpret a dual of an LP for an audience who does not know mathematics/OR (without LP, dual, bounds, etc.). Though I attempted it and was very close to what the ...
3
votes
1answer
136 views
Estimation of the number of optimum vertices
Consider any linear programming model of $n$ variables and $m$ constraints which has multiple optimum solutions. If it is possible, I'd like to know the lower and upper limits (in terms of $n$, $m$ ...
4
votes
3answers
695 views
Linear programming convexity
Is it possible for a linear programming model to be non-convex ? If it is, please, provide a simple 2 variables example and explain why it is non-convex.
EDIT 1:
I have been wondering, maybe the ...
2
votes
0answers
59 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 ...
3
votes
0answers
40 views
Public available MPS files with semi-continuous variables
Is there some MPS files with semi-continuous variables public available anywhere?
To me it seems MIPLIB does not contain any.
Erling
5
votes
0answers
64 views
Complexity of determining whether a LP or MIP is infeasible
What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
4
votes
0answers
115 views
Does anyone have the criss cross algorithm programming code to solve linear programming problems?
I have a project that requires programming code for the simplex algorithm and criss-cross algorithm. The purpose of this project is to compare the two methods. I've tried to find it, but the ...
1
vote
0answers
56 views
Linear programming with correction term based on decision vector
I had a linear programming problem where I am optimizing some function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known.
I now want to ...
4
votes
2answers
225 views
Suggest me good books to learn heuristics to solve Operations Research problems using python
Suggest me some good books with implementation of heuristics using python to solve operations research problems
2
votes
1answer
89 views
On dual-formulation of a given primal for a set-covering problem
I need to solve an LP-relaxation of an airline crew pairing optimization problem (CPOP). The problem formulation is a modified SCP and is as follows:
Primal of the CPOP:
\begin{align}\min&\quad\...
2
votes
1answer
86 views
Specific usecase of two-phase simplex algorithm
The problem below aims to find to most optimal way to transport the fuel :
A company Er must transport a type of fuel from its two refineries Ra and Rb to its two points of sale PV1 and PV2. The ...
2
votes
0answers
62 views
Dantzig decomposition and Column Generation for equality constraints
I was trying to apply Dantzig Decomposition followed by Column Generation. The following is how I was taught.
\begin{array}{l}
\text { Minimize }-10 x_1-2 x_{2}-4 x_{3} \\
\text { subject to: } x_{1}+...
4
votes
1answer
174 views
How to write quantity discount constraint?
In a simple transportation problem like below image, how to model a constraint for shipment discount e.g. if quantity transported from any origin to any destination is more than 100 unit then the ...
3
votes
0answers
127 views
On solving the Restricted Master Problem in Column Generation technique
I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
3
votes
0answers
39 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
1answer
340 views
How to set these constraints in a linear optimization problem (PuLP)?
I am trying to implement an employee (nurse) scheduling problem and seek some advice on how to implement a specific constraint.The problem is as follows: There is a set of employees and days (both ...
8
votes
3answers
387 views
LP dependent on the ordering of the data
This is a rather simple question. Can a solution to a linear programming problem be dependent on the order in which the data is read/presented/stored?
I know, that the time it takes to solve the ...
2
votes
1answer
106 views
Same values constraint and grouping of variables
In a linear program, I would like some variables to:
1. Take the same values
2. Group some variables i.e. some variables should take same values or lie within certain percentage.
3. All different ...
1
vote
1answer
244 views
How to enforce this specific constraint in PuLP?
I am trying to implement an employee (nurse) scheduling problem and seek some advice on how to implement a specific constraint.The problem is as follows: There is a set of employees and days (both ...
13
votes
1answer
94 views
Is the optimal objective of a linear program continuous in its right-hand-side?
Consider a linear program
$$f(b)=\min_{x}\{c^\top x: A x = b, x\geq 0\}$$
(assume it is feasible and bounded for all $b$). My understanding is that $f(b)$ is a convex piecewise linear function of $b$ ...
3
votes
1answer
125 views
Manually indicate initial basis for coin-or lp solver CLP
I have a set partitioning formulation with each constraint being an equality constraint to meet the given demand (right-hand side of the constraint).
For each constraint, I have a slack and a surplus ...
2
votes
1answer
110 views
Inequality Constraint Linearization of a product of an integer and a binary variable
I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable?
But the answers to that questions didn't help me find a solution for my ...
4
votes
1answer
288 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 ...
5
votes
3answers
86 views
Requiring exactly $n_j$ slots for job $j$ (if scheduled)
Let $x_{j}(t)=1$ iff job $j$ is scheduled at time $t$. I want to say that if the job is scheduled at all, then it is scheduled at $n_j$ slots. I wrote this as:
$$x_{j}(t)\sum_{s=1}^{T}x_{j}(s)=n_jx_{...
1
vote
0answers
97 views
Need help in formulating linear program
Edit: updated my solution for linear programming
Can anyone explain the following passage?
Both semiconductors and power generation industries also want to buy as many of the remaining units as ...
5
votes
3answers
450 views
How can I represent null or dashes in a cost matrix or incidence matrix in CPLEX?
In the image below, the cost matrix of customers and supplier has several dashes which indicates the impossibility of certain suppliers with certain customers. How can I represent these dashes in ...
0
votes
1answer
261 views
What is wrong with my linear programming model?
I tried solving this problem
Here is my cplex code
I have mentioned stored[month] as float+ but in the final result I get negative values. What is wrong with my model?
3
votes
1answer
188 views
Problem solving a linear program using Excel
The exercise is as follows:
ACI has decided to put an order for golf shoes twice every year and
expects to receive one shipment of $960$ pallets of shoes by the
beginning of January and another ...
5
votes
1answer
428 views
Where can I find resources to learn mathematical modelling for real life operation research problems like combinatorial optimization?
I find it hard to form math models for real life operations research problems, how can I learn this? Any books, tutorials available?
2
votes
1answer
135 views
How to formulate logical or constraint in cplex?
How to write the following constraint in cplex?
the cost for full truck load is $700
and the cost of fractional truck load is \$800 *fraction up to $700
7
votes
2answers
6k views
Solving a minimization problem using a Simplex method
There is a method of solving a minimization problem using the simplex method where you just need to multiply the objective function by -ve sign and then solve it using the simplex method. All you need ...
0
votes
1answer
172 views
How to form math model to solve this problem using cplex
Hiring company has the following requirement within a year;
week 1 to 5: 20
week 6 to 20: 40
week 21 to 40: 35
week 41 to 60: 55
week 61 to 80:75
week 81 to 100: 60
Training time for an ...
8
votes
2answers
169 views
Modeling Linear Program to decide if an inequality is facet
Suppose you have a set of points $v_1,\ldots,v_n$, which are the vertices of the polytope $P=\operatorname{conv}\{v_1,\ldots,v_n\}$ and a linear inequality $a^\top v \leq b$.
What would be a linear ...
4
votes
1answer
91 views
Analytically finding the maximizer of a trace optimization problem
$A \in \mathbb{R}^{m \times n}$ is an arbitrary data matrix. Moreover, $w \in \mathbb{R}^m$ is a data vector which is a probability vector, i.e., $w\succeq 0, \sum_{i=1}^m w_i = 1$.
I have a ...
5
votes
1answer
88 views
How to linearize difference of absolutes?
How to linearize difference of absolutes?
$$|a|\ge k|b|$$
where $a,b$ are variables and $k$ is a constant.
3
votes
1answer
125 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.
...
8
votes
2answers
103 views
how to penalize a shortfall of a sum of absolute values
I have a model where there is a constraint on the sum of absolute values, and I would like to add a penalty on the shortfall from the constraint. More specifically:
\begin{align*}
\text{maximize}\ &...
3
votes
1answer
95 views
Linear programming explanation in Algorithms by Sanjoy Dasgupta
I am reading about simplex algorithms in a textbook titled Algorithms by Dasgupta-Papadimitriou-Vairani.
On each iteration, simplex has two tasks:
Check whether the current vertex is optimal (and if ...
4
votes
1answer
301 views
Transforming a Quadratic constraint to SOCP
I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming ...
3
votes
2answers
115 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}
\...
5
votes
1answer
154 views
Propagate value through a graph
Here is my question where I am propagating distance through the graph, I was wondering if it is possible to do when the graph has cycles, i.e., traveling the same node multiple time then is it ...
2
votes
1answer
193 views
Controlling the constraint execution sequence in docplex
I have tried to implement my question asked here with the help of Github code link.
Below is the linearized version of the MTZ like constraint as per the answer given here. Constraints below assign ...
4
votes
1answer
180 views
TSP subtour elimination with multiple formulations
Referring to the question here.
Given a set $S$, which we need to travel following TSP rules.
I was wondering if this sub tour elimination method is good enough or not?
Let $b_{i,j}$ denote edge ...
9
votes
2answers
972 views
Is there a way to view added constraints in Gurobi (Python)?
I should note that I am very new to Gurobi so apologies if this is obvious. I am working on a project for a class to maximize profit on a theoretical flight network by deciding which routes to fly at ...
3
votes
1answer
152 views
How to set combined stop condition in AMPL/CPLEX?
I would like to set a stop condition combined of a timelimit and a relative MIP gap.
So I would like AMPL/CPLEX to look for the solution of my LP for an hour and if there isn't a solution stop if or ...
3
votes
1answer
339 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 ...
