Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
49
questions with no upvoted or accepted answers
9
votes
0answers
73 views
What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?
I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
9
votes
0answers
127 views
Ill-conditioned LP in Bender's decomposition
I have implemented a Bender's decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the slave dual LP. As you can see below, the coefficients seem ...
7
votes
0answers
77 views
Provide basic solution to CLP
I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many ...
7
votes
0answers
137 views
Modeling traffic in a city
I am trying to model traffic in a city, $(i,j)$ represents a road in a city.
There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
7
votes
0answers
77 views
Building the Scheurman's Model II constraints for a multi period linear program
Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
7
votes
0answers
69 views
Modelling a simple ordering problem to have balanced delivery days
Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
6
votes
0answers
56 views
Estimating multistop routing costs
In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints.
An example of this occurs in the classical facility location problem, where a warehouse can send out a ...
6
votes
0answers
123 views
Is this a valid strong polynomial algorithm for deciding LP feasibility?
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
6
votes
0answers
61 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?
6
votes
0answers
76 views
Benefits of removing slack variables during presolve
I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2):
Consider the equation $4x_1+...
5
votes
0answers
106 views
Obtaining the system of irredundant inequalities from a set of inequalities using CPLEX
Given a linear system of inequalities $Ax \geq b$, I would ideally like to compute the irredundant set for those set of inequalities. I know how to do so mathematically, but I was wondering if there ...
5
votes
0answers
59 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 ...
5
votes
0answers
33 views
In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples
Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion.
...
5
votes
0answers
93 views
Construct a direction of recession of the dual that is from growth to dual function
Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $ A \in \mathbb {R}^{ m × n}$ has rank $m$. Suppose ...
4
votes
0answers
108 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 ...
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
163 views
Publishing paper that uses LP solver to solve equation
I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results.
How valuable is this paper, and what is its quality? Can ...
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
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
58 views
Optimal Seat Allocation Problem
I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
3
votes
0answers
47 views
Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?
I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
3
votes
0answers
32 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 ...
3
votes
0answers
39 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
3
votes
0answers
108 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
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 ...
2
votes
0answers
45 views
Two binding constraints - Linear Programming
I'm having some troubles to continue solving my system, I'm used to solve such systems but with "one" binding constraint, if someone could give me some helpful hints so I can solve it I will ...
2
votes
0answers
67 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
69 views
How to linearize this multiplicative constraint?
I have a constraint in the form
$\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$
Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable).
$x$ and $\zeta$ are also optimization ...
2
votes
0answers
56 views
Determine set of “arbitrage-free” regional prices
I am seeking for a way how to determine set of "arbitrage-free" regional prices for a single commodity market.
There are $N>1$ production units with costs $C^{prod}_i, i=1,\dots,N$ and ...
2
votes
0answers
55 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
93 views
Condition for an integer program and its linear relaxation to have the same value
Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
2
votes
0answers
41 views
High-mix manufacturing capacity
I'm not an expert in OR but I would like to determine what is the maximum manufacturing capacity of a plant (or how much a plant can produce of mix products).
Each person in the plant has a known set ...
2
votes
0answers
67 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 + ...
2
votes
0answers
58 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 ...
2
votes
0answers
57 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
58 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}+...
1
vote
0answers
27 views
Unifying constraint matrices in sparse situations
$\DeclareMathOperator\Set{Set}$
Let
$Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$
where $A$ has $r=km$ rows and $k=O(1)$.
I am trying to write
$$
Set=\{x\in\...
1
vote
0answers
44 views
To estimate new sales from history
A fruit supplier sells 3 types of fruits. The company has 3 salespersons.
Here are the sales quantity of each person for each fruit. The total sales figure is available. (this is all the available ...
1
vote
0answers
64 views
Decomposition of Polyhedra
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
1
vote
0answers
61 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
32 views
Vertices of Polytope using Gurobi
Is there any way I can obtain all the vertices of a polytope using Gurobi?
If this isn't possible, can I log all the intermediate vertices that Simplex finds before it hits the optimal one?
1
vote
0answers
31 views
How can I see the engine log when solving a LP using pulp (python)?
I wonder which command should I use to see how the steps the pulp solver is doing when solving a linear program.
1
vote
0answers
81 views
Expansion heuristic using gurobi reduced cost / shadow price (LP)
Gurobi 9.0.0 // C++ // LP
Let us assume the following problem with three nodes: (1)-----(2)-----(3)
node (1) is producing ...
1
vote
0answers
297 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{...
1
vote
0answers
40 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 ...
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 ...
0
votes
0answers
113 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:
...
0
votes
0answers
95 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 ...
