Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
3
votes
0answers
25 views

Linear functions in Lenstra's algorithm

I had asked this question at MathOverflow and was pointed here. I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
5
votes
0answers
27 views

Min-cost flow with per-edge flow conservation

I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint. Instead of the summed outgoing flow equaling the summed ...
3
votes
2answers
79 views

Faster implementation of “or” constraints in ILP

I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...
0
votes
0answers
96 views

Resource constrained LP problem

I am working on Diet Allocation problem. Where we need to provide food piece for protein deficiency. The data is as below: ...
5
votes
1answer
96 views

Simplex Multiplier

I am reading through a book which provides an example of a linear program given by \begin{align}\min&\quad-24y_{1}-28y_{2}\\\text{s.t.}&\quad6y_{1}+10y_{2} \leq 2400\\&\quad8y_{1}+5y_{2} \...
1
vote
0answers
242 views

Canonical form of a linear program

I have a linear programming problem that I want to write in the canonical form: \begin{align}\min&\quad c^\top X\\\text{s.t.}&\quad A\cdot X\le b\end{align} The problem is given by \begin{...
5
votes
2answers
176 views

How to find all vertices of a polyhedron

I have a convex polyhedron given by a set of linear inequalities, for example: $$ x_1 \geq 0,~~ x_2 \geq 0, ~~x_3\geq 0 \\ x_1+x_2\leq 1,~~ x_2+x_3\leq 1,~~ x_3+x_1\leq 1 $$ I want to list all the ...
3
votes
1answer
65 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 ...
1
vote
0answers
37 views

Verifying the correctness of KKT conditions

I have a LP problem and derived the corresponding KKT conditions for the same. I simulated the LP and obtained the primal and dual values and manually checked if the KKT conditions hold. Is there any ...
2
votes
0answers
65 views

Finding Optimal Route using different Paths

I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths. $$Route1 = path1 + ...
6
votes
2answers
130 views

Linear objective function with non-linear constraints

I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type $$ \underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\ $$ subject to the ...
5
votes
2answers
124 views

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

Say that I have a binary IP $$z=\max_x \{c^\top x: Ax=b, x\in B^n\}$$ where $B^n$ is the set of $n$-dimensional $0-1$ vectors. Its LP relaxation will be $$z^{LP}=\max_x \{c^\top x: Ax=b, 0\leq x\leq 1\...
5
votes
1answer
96 views

Linearizing a constraint with square root of a variable

I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized. \begin{alignat}2\min &\...
6
votes
1answer
89 views

Can I replace the objective function $f$ with $g$ if $g \ge f$?

I am working on a project where the customer requested to change the current objective function $f$ to another function $g$ (both linear). It is easy to prove that $f \le g$ and as both are linear ...
2
votes
1answer
38 views

How to properly define an edge set with an uncommon condition

I am trying to define an edge set as follows: $\mathcal{E}=\{(i,j)|i,j\in\mathcal{V}\land T_{ij}\leq R \land \text{$i$ and $j$ are not jointly in $\mathcal{K}$\}}$, where $\mathcal{V}$ is the set of ...
1
vote
0answers
41 views

linearisation of if-then constraint [duplicate]

Is it possible to translate this if-then constraint in linear manner to be solved with a linear programming solver? If not, how can it be translated into a integer programming manner to be solved by ...
4
votes
2answers
182 views

Output of binary variable greater than one

I am working on a shipping demurrage problem that uses a binary variable to denote the date a specific vessel can be loaded (I have been kindly helped by Wesley on OR before with this). I am confident ...
1
vote
1answer
40 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 ...
5
votes
2answers
141 views

Polynomial algorithm for a special ILP problem

Given the following problem: \begin{align} & z=\min \sum_{ij} x_{ij}\\ \text{s.t.} & \quad \sum_i d_{ij} x_{ij} \ge s_j, \quad \forall j \tag1 \\ & \quad \sum_j x_{ij} \le 1, \quad \...
2
votes
1answer
142 views
2
votes
1answer
103 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 ...
1
vote
1answer
104 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
0answers
33 views

Linearize max function in a constraint [duplicate]

I have a constraint as follows: $ \sum_i {r_i} \geq \max \{g_j, B_j\} $ where, $r_i$, $g_j$ are variables and $B_j$ is a parameter. How do I linearize the constraint (I suppose using big-M method)?...
3
votes
1answer
60 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 ...
2
votes
4answers
76 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 ...
1
vote
1answer
66 views

Cplex giving different solutions for equivalent Linear problems

I'm trying to simplify a linear problem by removing "useless" variables and constraints. After simplifying my initial problem and solving both instances with Cplex, it seems like the results differ ...
10
votes
2answers
632 views

Can presolve reductions change the value of the linear programming relaxation?

For integer programs solvers (like Gurobi, Cplex, ...) report the value of the linear programming relaxation for integer programs, i.e. ...
7
votes
2answers
529 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
55 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
48 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
80 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 ...
4
votes
1answer
74 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
110 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
558 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
51 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
38 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
45 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
87 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
54 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
95 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
50 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: $min \left(\sum_{j=1}^{P} ...
2
votes
1answer
50 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
51 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
96 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
72 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
31 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 ...
4
votes
1answer
123 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 ...
7
votes
3answers
344 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
61 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 ...
2
votes
1answer
59 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 ...

1
2 3 4 5